Teorema căsătoriei

Teorema căsătoriei este un rezultat fundamental al combinatoriei . Această teoremă a fost dovedită de matematicianul englez Philip Hall în 1935 și este cunoscută și sub numele de teorema reprezentanților diferiți sau teorema lui Hall .

Declarație și exemple

Următorul exemplu justifică numele teoremei.

Să presupunem că avem două seturi unul ${\scriptstyle D}$ ${\ displaystyle {\ scriptstyle D}}$ ${\ displaystyle {\ scriptstyle D}}$ de femei și una ${\scriptstyle U}$ ${\ displaystyle {\ scriptstyle U}}$ ${\ displaystyle {\ scriptstyle U}}$ de oameni și să presupunem că nu există poligamie ; Să presupunem, în plus, că fiecare femeie are propria sa listă de bărbați cu care ar dori să se căsătorească. Spus ${\textstyle {\scriptstyle D'}}$ ${\ displaystyle {\ textstyle {\ scriptstyle D '}}}$ ${\ displaystyle {\ textstyle {\ scriptstyle D '}}}$ orice subset de ${\scriptstyle D}$ ${\ displaystyle {\ scriptstyle D}}$ ${\ displaystyle {\ scriptstyle D}}$ si a zis ${\scriptstyle U'}$ ${\ displaystyle {\ scriptstyle U '}}$ ${\ displaystyle {\ scriptstyle U '}}$ subsetul de ${\scriptstyle U}$ ${\ displaystyle {\ scriptstyle U}}$ ${\ displaystyle {\ scriptstyle U}}$ format din membri ai listelor de femei ale ${\scriptstyle D'}$ ${\ displaystyle {\ scriptstyle D '}}$ ${\ displaystyle {\ scriptstyle D '}}$ , următoarea condiție este necesară pentru ca fiecare femeie să se poată căsători cu un bărbat dorit de ea:

$|D'|\leq |U'|$ ${\ displaystyle | D '| \ leq | U' |}$ ${\ displaystyle | D '| \ leq | U' |}$

Teorema căsătoriei afirmă că și această condiție este suficientă.

Pentru a introduce formularea setată a teoremei este necesar să se definească ce se înțelege prin sistem de reprezentanți diferiți.

Dat fiind n mulțimi finite $S_{1},.......,S_{n}$ ${\ displaystyle S_ {1}, ......., S_ {n}}$ ${\ displaystyle S_ {1}, ......., S_ {n}}$ un sistem de reprezentanți distincti (SRD) pentru seturile considerate este o succesiune de elemente distincte $s_{1},.....,s_{n}$ ${\ displaystyle s_ {1}, ....., s_ {n}}$ ${\ displaystyle s_ {1}, ....., s_ {n}}$ cu $s_{i}\in S_{i}$ ${\ displaystyle s_ {i} \ în S_ {i}}$ ${\ displaystyle s_ {i} \ în S_ {i}}$ .

Teorema ia apoi următoarea formă: date n seturi $S_{1},.......,S_{n}$ ${\ displaystyle S_ {1}, ......., S_ {n}}$ ${\ displaystyle S_ {1}, ......., S_ {n}}$ este posibil să se determine un sistem de reprezentanți distincti dacă și numai dacă este îndeplinită următoarea condiție:

$|S_{i1}\cup .....\cup S_{ik}|\geq k$ ${\ displaystyle | S_ {i1} \ cup ..... \ cup S_ {ik} | \ geq k}$ ${\ displaystyle | S_ {i1} \ cup ..... \ cup S_ {ik} | \ geq k}$ orice ar fi $k\in \left\{1,...,n\right\}$ ${\ displaystyle k \ in \ left \ {1, ..., n \ right \}}$ ${\ displaystyle k \ in \ left \ {1, ..., n \ right \}}$ .

Un exemplu este următorul:

sunt $S_{1}=\{a,b,c\}$ ${\ displaystyle S_ {1} = \ {a, b, c \}}$ ${\ displaystyle S_ {1} = \ {a, b, c \}}$ , $S_{2}=\{a,b\}$ ${\ displaystyle S_ {2} = \ {a, b \}}$ ${\ displaystyle S_ {2} = \ {a, b \}}$ , $S_{3}=\{a,c,d,e,f\}$ ${\ displaystyle S_ {3} = \ {a, c, d, e, f \}}$ ${\ displaystyle S_ {3} = \ {a, c, d, e, f \}}$ , $S_{4}=\{c,d,e\}$ ${\ displaystyle S_ {4} = \ {c, d, e \}}$ ${\ displaystyle S_ {4} = \ {c, d, e \}}$ , $S_{5}=\{c,d,e,f\}$ ${\ displaystyle S_ {5} = \ {c, d, e, f \}}$ ${\ displaystyle S_ {5} = \ {c, d, e, f \}}$ .

Atunci $\{a,b,c,d,e\}$ ${\ displaystyle \ {a, b, c, d, e \}}$ ${\ displaystyle \ {a, b, c, d, e \}}$ este un SRD, dar nu este singurul, de exemplu este și el $\{c,b,d,e,f\}$ ${\ displaystyle \ {c, b, d, e, f \}}$ ${\ displaystyle \ {c, b, d, e, f \}}$ .

Explicat în Teoria graficelor

Teorema este adesea formulată în termeni de grafic bipartit , adică un grafic nedirecționat astfel încât mulțimea vârfurilor sale poate fi partiționată în două subseturi astfel încât fiecare vârf al uneia dintre aceste două părți să fie conectat doar la vârfurile celeilalte.

Având în vedere un grafic bipartit cu subseturi $V_{1}$ ${\ displaystyle V_ {1}}$ ${\ displaystyle V_ {1}}$ Și $V_{2}$ ${\ displaystyle V_ {2}}$ ${\ displaystyle V_ {2}}$ , se spune cuplarea completă a $V_{1}$ ${\ displaystyle V_ {1}}$ ${\ displaystyle V_ {1}}$ în $V_{2}$ ${\ displaystyle V_ {2}}$ ${\ displaystyle V_ {2}}$ un set de arce fără extreme în comun, având caracteristica de a conecta fiecare element de $V_{1}$ ${\ displaystyle V_ {1}}$ ${\ displaystyle V_ {1}}$ cu un element de $V_{2}$ ${\ displaystyle V_ {2}}$ ${\ displaystyle V_ {2}}$ .

Teorema lui Hall poate fi formulată după cum urmează:

Într-un grafic bipartit $G=\left(V_{1}\cup V_{2};E\right)$ ${\ displaystyle G = \ left (V_ {1} \ cup V_ {2}; E \ right)}$ ${\ displaystyle G = \ left (V_ {1} \ cup V_ {2}; E \ right)}$ există o cuplare completă a $V_{1}$ ${\ displaystyle V_ {1}}$ ${\ displaystyle V_ {1}}$ în $V_{2}$ ${\ displaystyle V_ {2}}$ ${\ displaystyle V_ {2}}$ dacă și numai dacă $\forall A\subseteq V_{1}$ ${\ displaystyle \ forall A \ subseteq V_ {1}}$ ${\ displaystyle \ forall A \ subseteq V_ {1}}$ se dovedește

$|A|\leq |R(A)|$ ${\ displaystyle | A | \ leq | R (A) |}$ ${\ displaystyle | A | \ leq | R (A) |}$ unde este $R(A)\subseteq V_{2}$ ${\ displaystyle R (A) \ subseteq V_ {2}}$ ${\ displaystyle R (A) \ subseteq V_ {2}}$ constă din vârfurile adiacente elementelor de $LA$ ${\ displaystyle A}$ $LA$ .

Bibliografie

( EN ) P. Hall (1935): „Despre reprezentanții subseturilor” J. London Math. Soc. Vol. 10
( EN ) JH Van Lint, RM Wilson (1992): „A Course in Combinatorics” Cambridge University Press

linkuri externe

( EN ) Teorema căsătoriei , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.