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 ${\displaystyle {\scriptstyle D}}$ di donne e uno ${\displaystyle {\scriptstyle 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 ${\displaystyle {\textstyle {\scriptstyle D'}}}$ un qualsiasi sottoinsieme di ${\displaystyle {\scriptstyle D}}$ e detto ${\displaystyle {\scriptstyle U'}}$ il sottoinsieme di ${\displaystyle {\scriptstyle U}}$ formato dagli appartenenti alle liste delle donne di ${\displaystyle {\scriptstyle D'}}$, la seguente condizione risulta necessaria affinché ciascuna donna possa sposarsi con un uomo dei suoi desideri:

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

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 ${\displaystyle S_{1},.......,S_{n}}$ un sistema di rappresentanti distinti (SRD) per gli insiemi considerati è una sequenza di elementi distinti ${\displaystyle s_{1},.....,s_{n}}$ con ${\displaystyle s_{i}\in S_{i}}$.

Il teorema assume allora la seguente forma: dati n insiemi ${\displaystyle S_{1},.......,S_{n}}$ è possibile determinare un sistema di rappresentanti distinti se e solo se è verificata la seguente condizione:

${\displaystyle |S_{i1}\cup .....\cup S_{ik}|\geq k}$ qualunque sia ${\displaystyle k\in \left\{1,...,n\right\}}$.

Un esempio è il seguente:

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

Allora ${\displaystyle \{a,b,c,d,e\}}$ è un SRD, ma non è l'unico, ad esempio lo è anche ${\displaystyle \{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 ${\displaystyle V_{1}}$ e ${\displaystyle V_{2}}$, si dice accoppiamento completo di ${\displaystyle V_{1}}$ in ${\displaystyle V_{2}}$ un insieme di archi senza estremi in comune, aventi la caratteristica di collegare ciascun elemento di ${\displaystyle V_{1}}$ con un elemento di ${\displaystyle V_{2}}$.

Il teorema di Hall si può formulare così:

In un grafo bipartito ${\displaystyle G=\left(V_{1}\cup V_{2};E\right)}$ esiste un accoppiamento completo di ${\displaystyle V_{1}}$ in ${\displaystyle V_{2}}$ se e solo se ${\displaystyle \forall A\subseteq V_{1}}$ risulta

${\displaystyle |A|\leq |R(A)|}$ dove ${\displaystyle R(A)\subseteq V_{2}}$ è costituito dai vertici adiacenti a elementi di ${\displaystyle A}$.

Bibliografia

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

Collegamenti esterni

• (EN) Hall’s theorem, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Teorema dei matrimoni, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica