舞會問題(problem of dance)亦稱婚姻問題或工作安排問題，是一類組合問題。設有n個男子和n個女子，每個男子與n個女子中的若干個互相認識，問這些男子和女子能否結成n對夫婦，使每對夫婦都是已經相互認識的。
基本介紹
- 中文名：舞會問題
- 外文名：problem of dance
- 所屬學科：數學（組合學）
- 別稱：婚姻問題或工作安排問題
基本介紹,荷爾的婚姻定理,舞會問題的解答,
基本介紹
舞會問題 設在一個學校里，每個男生認識k個女生，每個女生認識k個男生，問在一次舞會上，是否可使相識的男女共同起舞？
這個古典問題可以由荷爾的婚姻定理解決，下面先介紹婚姻定理。
荷爾的婚姻定理
在圖論中有這樣一個“二部圖的完美匹配充要條件定理”：
①
；
②對
，有
這個定理是1935年由荷爾(M.Hall)證明的，因此，又稱荷爾定理。
沒有學過圖論的讀者，對此定理的理解似乎是困難的，但是，有趣的是換一種說法，就容易理解多了。
荷爾定理又稱婚姻定理，它解決了著名的婚姻問題：在一個由有限個小伙子所組成的集合中，如果每個小伙子認識幾個姑娘，問在什麼條件下可以使每個小伙子和他所認識的一個姑娘結婚？如果每個小伙子都與姑娘結婚，則稱該問題有解，婚姻定理給出了婚姻問題有解的充分必要條件。
婚姻定理可以這樣敘述：“婚姻問題有解的充分必要條件是：任意k個小伙子一共認識至少k個姑娘，這裡1≤k≤m，m表示小伙子的總數。”
舞會問題的解答
將男生作為點集X，女生作為點集Y，凡相識男女生之間均畫一連線，於是得二部圖G=(X，Y；E)。
易見，
根據荷爾定理，相識的男女共同起舞是可能的。
