Teorema de Hall

La teorema del matrimoni de Hall, o simplement Teorema de Hall, és una teorema en dos formulació equivalents:

• La formulació per matemàtica combinatòria tracta d'una colecció de conjunts finitos. Dona una condició necessària i suficient per a poder seleccionar un element distint de cada conjunt.
• La formulació per teoria de grafos tracta d'un grafo bipartito. Dona una condició necessària i suficient per a trobar una emparejamiento que cobrix per lo manco un costat del grafo.

Formulació Combinatòria

Siga S una família de conjunts finitos, a on la família pot contindre un número infinit de conjunts i els conjunts individuals poden repetir-se vàries voltes.

Una travessera per a S és un conjunt T i una biyección f des de T a S tal que para tot t en T, t és membre de f(t). Un terme alternatiu per a transversal és sistema de representants distints.

La colecció S satisfà la condició de matrimoni si i solament si per a cada sub colecció $W\subseteq S$, tenim

$|W|\le \left|\bigcup _{A\in W}A\right|.$

En atres paraules, el número de conjunts en cada sub colecció W és menor o igual que el número d'elements distints en l'unió sobre la sub colecció W.

La teorema de Hall indica que S té una transversal si i només si S satisfà la condició de matrimoni.

Eixemples

eixemple

Eixemple 1: Considere S = {A₁, A₂, A₃} en

A₁ = {1, 2, 3}

A₂ = {1, 4, 5}

A₃ = {3, 5}.

Una transversal vàlida seria (1, 4, 5). (Tinga en conte que açò no és únic: (2, 1, 3 funciona igualment be, per eixemple.)

eixemple 2

Eixemple 2: Considere S = {A₁, A₂, A₃, A₄} en

A₁ = {2, 3, 4, 5}

A₂ = {4, 5}

A₃ = {5}

A₄ = {4}.

No existix cap transversal vàlida. La condició de matrimoni és violada com ho demostra la sub colecció {A₂, A₃, A₄}.

Eixemple 3: Considere S= {A₁, A₂, A₃, A₄} en

A₁ = {a, b, c}

A₂ = {b, d}

A₃ = {a, b, d}

A₄ = {b, d}.

Les úniques transversal vàlides són (c, b, a, d) i (c, d, a, b).

Aplicacions

L'eixemple estàndar d'una aplicació de la teorema del matrimoni és imaginar dos grups; un de n hòmens, i un de n dònes. Per cada dòna hi ha un subconjunt dels hòmens, qualsevol dels quals es casaria feliçment; i qualsevol home estaria feliç de casar-se en una dòna que vol casar-se en ell. Considere si és possible fer parella (en el matrimoni) als hòmens i dònes per a que cada persona siga feliç.

Si deixem que A_i siga el conjunt d'hòmens que la dòna i-th seria feliç de casar-se, llavors la teorema del matrimoni establix que cada dòna pot casar-se feliçment en un home si i només si la colecció de conjunts {A_i} complix en la condició de matrimoni.

Tinga en conte que la condició de matrimoni és que, per a qualsevol subconjunt $I$ de les dònes, el número d'hòmens que a lo manco una de les dònes estaria feliç de casar-se, $|\bigcup _{i\in I}{A}_i|$, ser a lo manco tan gran com el número de dònes en eixe subconjunt, $|I|$. És obvi que esta condició és necessària, com si no se sostinga, no hi ha suficients hòmens per a compartir entre les $I$ dònes. Lo interessant és que també és una condició suficient .

Formulació de teoria de grafos

emparejamiento

Siga G un grafo bipartito finito en conjunts bipartitos X i I (G:= (X + I, I)). Per a un conjunt W de vèrtiços en X, siga $N_G(W)$ que denota veïnat de W en G, i.i. el conjunt de tots els vèrtiços en I adjacents a algun element de W. La teorema del matrimoni en esta formulació establix que hi ha un emparejamiento que comprén completament X si i solament si per a cada subconjunt W de X:

$|W|\le |N_G(W)|.$

En atres paraules cada subconjunt W de X té suficients vèrtiços adjacents en I.

Donat un grafo bipartito finito G:= (X + I, I), en conjunts bipartitos X i I d'igual tamany, la teorema del matrimoni proporciona condicions necessàries i suficients per a l'existència d'un emparejamiento perfecte en el grafo.

Una generalisació per a grafos en general (no necessàriament bipartitos) és proporcionada pel Teorema de Tutte.

Demostració de la versió per Teoria de Grafos

Un X- emparejamiento saturat és un emparejamiento que cobrix cada vèrtiç en X.

Primer vàrem demostrar: Si un grafo bipartito G = (X + I, I) = G(X, I) té un X-emparejamiento saturat, llavors |N_G(W)| ≥ |W| per a tot W ⊆ X.

Supongam que M és un emparejamiento que satura cada vèrtiç de X. Siga el conjunt de tots els vèrtiços I emparellat per M en un W denotat com a M(W). Per lo tant, |M(W)|=|W|, per la definició de emparejamiento. Pero M(W) ⊆ N_G(W), ya que tots els elements de M(W) són veïns de W. Aixina, |N_G(W)| ≥ |M(W)| i per lo tant, |N_G(W)| ≥ |W|.

Ara provem: Si |N_G(W)| ≥ |W| per a tot W ⊆ X, llavors G(X,I)té un emparejamiento que satura cada vèrtiç en X.

Supongam que G(X,I) és un grafo bipartito que no té un emparejamiento que satura tot els vèrtiços de X. Siga M un emparejamiento màxim, i o un vèrtiç no saturat per M. Considere tots els camins alternatius (és dir, camins en G que alterna entre arestes cap a fòra i cap a dins en M) començant des de o. Siga T el conjunt de tots els punts de I conectats a o per estos camins alternatius, i W el conjunt de tots els punts en X conectats a o per estos camins alternatius (incloent o). Un camí alternatiu no maximal pot terminar en un vèrtiç en I, per a que no siga un camí aumentativo, per a que poguérem aumentar M a un emparejamiento estrictament major. Aixina cada vèrtiç en T és emparellat per M en un vèrtiç en W {o}. Pel contrari, cada vèrtiç v en W {o} és emparellat per M a un vèrtiç en T (és dir, el vèrtiç precedent v en un camí alternatiu que termina en v). Per lo tant, M proporciona una biyección de W {o} i T, lo que implica que |W| = |T| + 1. Per una atra part, N_G(W) ⊆ T: deixe v en I es conecte a un vèrtiç w in W. Si l'aresta (w,v) està en M, llavors v esta en T per la part anterior de la demostració, per una atra part podem prendre un camí alternatiu que acaba en w i estendre-ho en v, obtenint un camí aumentativo i mostrant que v esta en T. Per lo tant, |N_G(W)| = |T| = |W| − 1, una contradicció.

Equivalència de la formulació combinatòria i la formulació per teoria de grafos

Siga S = (A₁, A₂,..., A_n) a on els A_i són conjunts finitos no necessàriament distints. Siga el conjunt X = {A₁, A₂,..., A_n} (que és, el conjunt de noms dels elements S) i el conjunt I siga l'unió de tots els elements en tots els A_i.

Formem un grafo bipartito finito G:= (X + I, I en conjunts bipartitos X i I unint qualsevol element en I a cada A_i del que és membre. Una transversal de S és un X- emparejamiento saturat un emparejamiento que cobrix cada vèrtiç en X) d'un grafo bipartito G. Aixina un problema en formulació combinatòria pot ser fàcilment traduït a un problema en una formulació basada en teoria de grafos.

Referències

• (2010).«Introductory Combinatorics».Prentice-Hall/Pearson.
• (1994).«Combinatorics: Topics, Techniques, Algorithms».Cambridge University Press.
• (2010).«Hall's Marriage Theorem».The Archive of Formal Proofs.ISSN 2150-914X.Consultat el 11 de giner de 2017.
• (1986).«Combinatorial Theory».John Wiley &Sons.
• (1935).«On Representatives of Subsets».J. London Math. Soc..10(1)

26–30.doi:10.1112/jlms/s1-10.37.26.

• Halmos, Paul R. and Vaughan, Herbert E. "The marriage problem". American Journal of Mathematics 72, (1950). 214–215.
• (1984).«The Equivalence of Some Combinatorial Matching Theorems».Polygonal Publishing House.
• (2009).«Applied Combinatorics».CRC Press.
• (1992).«A Course in Combinatorics».Cambridge University Press.