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

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 un sistema di rappresentanti distinti (SRD) per gli insiemi considerati è una sequenza di elementi distinti con .

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

qualunque sia .

Un esempio è il seguente:

siano , , , , .

Allora è un SRD, ma non è l'unico, ad esempio lo è anche .

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 e , si dice accoppiamento completo di in un insieme di archi senza estremi in comune, aventi la caratteristica di collegare ciascun elemento di con un elemento di .

Il teorema di Hall si può formulare così:

In un grafo bipartito esiste un accoppiamento completo di in se e solo se risulta

dove è costituito dai vertici adiacenti a elementi di .

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