Teorema dei matrimoni

Il teorema dei matrimoni è un risultato fondamentale della combinatoria. Tale teorema è stato dimostrato dal matematico inglese Philip Hall nel 1935 ed è noto anche come teorema dei rappresentanti distinti o come teorema di Hall.

Enunciato ed esempi

La seguente esemplificazione giustifica il nome del teorema.

Supponiamo di avere due insiemi uno $D$ di donne e uno $U$ di uomini e supponiamo non vi sia poligamia; supponiamo, inoltre, che ciascuna donna abbia una propria lista di uomini con i quali desidererebbe sposarsi. Detto $D^{\prime }$ un qualsiasi sottoinsieme di $D$ e detto $U^{\prime }$ il sottoinsieme di $U$ formato dagli appartenenti alle liste delle donne di $D^{\prime }$, la seguente condizione risulta necessaria affinché ciascuna donna possa sposarsi con un uomo dei suoi desideri:

$|D^{\prime }|\le |U^{\prime }|$

Il teorema dei matrimoni afferma che tale condizione è anche sufficiente.

Per introdurre la formulazione insiemistica del teorema si deve definire cosa si intende per sistema di rappresentanti distinti.

Dati n insiemi finiti $S_1,.......,S_n$ un sistema di rappresentanti distinti (SRD) per gli insiemi considerati è una sequenza di elementi distinti $s_1,.....,s_n$ con $s_i\in S_i$.

Il teorema assume allora la seguente forma: dati n insiemi $S_1,.......,S_n$ è possibile determinare un sistema di rappresentanti distinti se e solo se è verificata la seguente condizione:

$|S_{i1}\cup .....\cup S_{ik}|\ge k$ qualunque sia $k\in \{1,...,n\}$.

Un esempio è il seguente:

siano $S_1=\{a,b,c\}$, $S_2=\{a,b\}$, $S_3=\{a,c,d,e,f\}$, $S_4=\{c,d,e\}$, $S_5=\{c,d,e,f\}$.

Allora $\{a,b,c,d,e\}$ è un SRD, ma non è l'unico, ad esempio lo è anche $\{c,b,d,e,f\}$.

Enunciato nella Teoria dei Grafi

Il teorema è spesso formulato in termini di grafo bipartito, cioè un grafo non orientato tale che l'insieme dei suoi vertici si può partizionare in due sottoinsiemi tali che ogni vertice di una di queste due parti è collegato solo a vertici dell'altra.

Dato un grafo bipartito con sottoinsiemi $V_1$ e $V_2$, si dice accoppiamento completo di $V_1$ in $V_2$ un insieme di archi senza estremi in comune, aventi la caratteristica di collegare ciascun elemento di $V_1$ con un elemento di $V_2$.

Il teorema di Hall si può formulare così:

In un grafo bipartito $G=(V_1\cup V_2;E)$ esiste un accoppiamento completo di $V_1$ in $V_2$ se e solo se $\mathrm{\forall }A\subseteq V_1$ risulta

$|A|\le |R(A)|$ dove $R(A)\subseteq V_2$ è costituito dai vertici adiacenti a elementi di $A$.

Bibliografia

• Template:En P. Hall (1935): “On Representatives of Subsets” J. London Math. Soc. vol. 10
• Template:En J. H. Van Lint, R. M. Wilson (1992): “A Course in Combinatorics” Cambridge University Press

Collegamenti esterni

• Template:Collegamenti esterni