Teorema dei matrimoni

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica wikitesto]

La seguente esemplificazione giustifica il nome del teorema.

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

|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 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}|\geq k qualunque sia k\in\left\{ 1,...,n\right\} .

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[modifica | modifica wikitesto]

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=\left(V_{1}\cup V_{2};E\right) esiste un accoppiamento completo di V_{1} in V_{2} se e solo se \forall A\subseteq V_{1} risulta

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

Bibliografia[modifica | modifica wikitesto]

  • (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