O posibilă soluție a problemei este: (1,4), (2,1), (3,3), (4,2).
Examinarea problemei poate fi reprezentată grafic printr-un grafic bipartit. Pentru a formula cu exactitate problema de nunti in ceea ce priveste teoria grafurilor, introducem un concept.
O potrivire (sau un set independent de margini) este setul de muchii, în care nu două adiacente. Potrivirea este maximă, în cazul în care nici unul dintre superset ei nu este independentă. potrivire perfectă a V1 V2 în grafic bipartit G (V1 ÇV2. E) este o corespondență unu-la-unu între nodurile V1 și submulțimea nodurilor V2. având proprietatea că nodurile conectate de margine. - Echivalent: potrivirea care acoperă vârful V1.
Acum problema nuntilor poate fi formulată după cum urmează: Dacă G (V1 ÇV2. E) - un grafic bipartit, condițiile în care G are o potrivire perfectă?
Folosind terminologia „matrimoniale“, putem formula următoarea condiție necesară pentru existența unor soluții la problema nunti: toți băieții k ar trebui să fie familiarizați (în total) pentru fete cel puțin k, unde 1 £ k £ m. - În cazul în care condiția nu este îndeplinită, este imposibil să se căsătorească are acești băieți k, nu mai vorbim de restul.
Este surprinzător faptul că această condiție necesară evidentă este în același timp și suficient. Aceasta este
Teorema lui Hall despre nunti. Fie A (| A | = m) - o pluralitate de băieți și B (| B | = n) - o pluralitate de fete, băieți și că fiecare dintre semn cu mai multe fete. Problema de nunti are o soluție dacă și numai dacă orice k băieții ar trebui să fie familiarizați (colectiv), cu cel puțin fete k, unde 1 £ k £ m.
Să - graf bipartit. Există potrivire perfectă dacă și numai dacă „AÍV1 | A | £ | T (A) |.
Fie S = 1 .... Sm> - familie la sfârșitul subseturi de subseturi E. Sk nu sunt neapărat diferite și se pot suprapune. Sistem de reprezentanți distincte (sau transversal) este un subset de C = 1. .... cm> m pluralității elementelor E astfel încât ck ÎSk. În unele cazuri, există o transversală?
Notă. C - subset -, prin urmare, toate ck diferite.