Și nunta de potrivire
Rezultatele acestui capitol sunt mai mult decât combinatorie rezultatele capitolele anterioare, chiar dacă acestea sunt strâns legate de grafic teorie. Discutați bine-cunoscut „teorema despre nunți“, aparținând lui Philip Hall, iar unele aplicații ale acestei teoreme, de exemplu, construcția de pătrate latine.
Teorema lui Hall despre nunti
Teorema despre nunti, Philip Hall sa dovedit în 1935 răspunde la următoarea întrebare, cunoscut sub numele de problema de nunti. ia în considerare un set finit de băieți, fiecare dintre care este familiarizat cu mai multe fete; Eu întreb, pot căsători tânărul în orice condiții, astfel încât fiecare dintre ei sa căsătorit cu prietena lui. (. Presupunem că poligamia nu este permis) De exemplu, în cazul în care există patru băieți și cinci fete, și relația de dragoste dintre ele sunt prezentate în tabelul 1, este posibil ca următoarea decizie: se căsătorească - pe - și - pe.
Fata, cu care semnul tânăr