Teorema dell'accoppiamento di Hall

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
MindFlyer

Teorema dell'accoppiamento di Hall

Messaggio da MindFlyer »

Teorema dell'accoppiamento di Hall (o lemma del matrimonio)
Siano dati un insieme di uomini e un insieme di donne. Alcune coppie (uomo, donna) sono "compatibili", ovvero si piacciono reciprocamente e non disdegnerebbero sposarsi. Un uomo può essere compatibile con più donne o con nessuna donna, e viceversa. Vorremmo poter organizzare dei matrimoni tra persone compatibili, in modo che ogni uomo risulti sposato (e ovviamente che ogni donna sia sposata con al più un uomo). Questo è possibile se e solo se, preso un qualunque insieme di n uomini, le donne compatibili con almeno uno di essi sono almeno n.

Dimostrare...
piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever »

Ma scusa una cosa, se n donne sono compatibili con lo stesso uomo come si fa a fare tutti matrimoni fra persone compatibili? Fai conto che se il numero di una donna è uguale a quello dell'uomo, sono compatibili. Come si fa a accoppiare D1, D1 e D1 con U1,U2 e U3 (U sta per uomo e D per donna)? Per forza 2 uomini rimarrannò scapoli eppure ho rispettato i presupposti del teorema (ci sono n donne compatibili con un uomo).
"Sei la Barbara della situazione!" (Tap)
MindFlyer

Messaggio da MindFlyer »

Non riesco a capire l'obiezione e non so come aiutarti. Mi descriveresti completamente e chiaramente un grafo che secondo te contraddice il teorema?
piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Re: Teorema dell'accoppiamento di Hall

Messaggio da piever »

MindFlyer ha scritto:Siano dati un insieme di uomini e un insieme di donne. Alcune coppie (uomo, donna) sono "compatibili", ovvero si piacciono reciprocamente e non disdegnerebbero sposarsi. Un uomo può essere compatibile con più donne o con nessuna donna, e viceversa. Vorremmo poter organizzare dei matrimoni tra persone compatibili, in modo che ogni uomo risulti sposato (e ovviamente che ogni donna sia sposata con al più un uomo). Questo è possibile se e solo se, preso un qualunque insieme di n uomini, le donne compatibili con almeno uno di essi sono almeno n.
Non sto provando a confutare il problema, però mi sembra di non riuscire a interpretare il testo correttamente. I matrimoni possono avvenire solo tra coppie compatibili, ma se ci sono n uomini e n donne (in questo caso ipotizziamo n=3) a ciascuna delle quali piace soltanto un uomo (lo stesso uomo per tutte e tre le donne), come potranno mai sposarsi gli altri 2 uomini che non piacciono a nessuna donna? Ovvero, provando a descrivere un grafo (scusa eventuali errori per quanto riguarda i grafi, ho appreso da 10 minuti la loro esistenza e li ho studiati nel topic-spiegazione di Marco), diciamo che le donne sono i vertici A,B,C di colore rosa e gli uomini sono i vertici D,E,F di colore azzurro. Dovremmo ottenere (così ho capito) un grafo bipartito in cui da ogni vertice parte uno e un solo arco.
I vertici A, B, C sono collegati con il vertice D, quindi esistono 3 archi con vertici rispettivamente AD, BD, CD. A questo punto sembra che i vertici E,F non siano collegati a nessun vertice rosa.
Potresti chiarirmi un altro dubbio: le donne devono essere tutte sposate e gli uomini tutti monogami? Dal testo mi sembrava d'aver capito così, ma ora non ne sono sicuro perché non riesco a capire se
ogni donna sia sposata con al più un uomo
indica che tutte le donne siano sposate con uno e un solo uomo o che nessuna donna possa avere più di un marito. Inoltre
ogni uomo risulti sposato
non indica con quante donne.

Scusa se ti rompo così tanto le scatole.

ciao
"Sei la Barbara della situazione!" (Tap)
MindFlyer

Re: Teorema dell'accoppiamento di Hall

Messaggio da MindFlyer »

piever ha scritto:I vertici A, B, C sono collegati con il vertice D, quindi esistono 3 archi con vertici rispettivamente AD, BD, CD. A questo punto sembra che i vertici E,F non siano collegati a nessun vertice rosa.
Esattamente, quindi in questo caso non è possibile organizzare i matrimoni come si vorrebbe. Dove sta il problema?
Potresti chiarirmi un altro dubbio: le donne devono essere tutte sposate e gli uomini tutti monogami?
Tutti (uomini e donne) devono essere monogami oppure non sposati. Inoltre, vogliamo che ogni uomo sia sposato, ma non è necessario che ogni donna lo sia.
piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Re: Teorema dell'accoppiamento di Hall

Messaggio da piever »

MindFlyer ha scritto:
piever ha scritto:I vertici A, B, C sono collegati con il vertice D, quindi esistono 3 archi con vertici rispettivamente AD, BD, CD. A questo punto sembra che i vertici E,F non siano collegati a nessun vertice rosa.
Esattamente, quindi in questo caso non è possibile organizzare i matrimoni come si vorrebbe. Dove sta il problema?
Son d'accordo che non è possibile ma il teorema dice che
Questo è possibile se e solo se, preso un qualunque insieme di n uomini, le donne compatibili con almeno uno di essi sono almeno n.
Visto che nel mio esempio ci sono n donne compatibili con un uomo, il teorema dovrebbe realizzarsi. E' per questo che credo di aver capito male il testo, o forse hai sbagliato a digitarlo.
"Sei la Barbara della situazione!" (Tap)
EvaristeG
Site Admin
Messaggi: 4896
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG »

piever ... attento :
MindFlyer ha scritto:Questo è possibile se e solo se, preso un qualunque insieme di n uomini, le donne compatibili con almeno uno di essi sono almeno n.
Se nel tuo esempio metti n=2 e prendi come uomini E,F, l'ipotesi non è soddisfatta, in quanto non esistono due donne per questo insieme ... l'ipotesi in particolare implica che per ogni uomo c'è almeno una donna compatibile...
piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever »

Ahhh, ora ho capito, pensavo che l'insieme n dovesse comprendere tutti gli uomini... :roll:
Grazie per la spiegazione EvaristeG
"Sei la Barbara della situazione!" (Tap)
piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever »

Tranquilli, non è un'altra obiezione al teorema :roll: , sto solo postando una dimostrazione...

Definiamo covering un sottoinsieme di vertici di un grafo tale che ogni arco del grafo tocca almeno un vertice appartenente ad esso.

Definiamo matching un sottoinsieme di archi di un grafo a 2 a 2 disgiunti.

Dimostriamo che il minor covering possibile e il maggior matching possibile hanno la stessa cardinalità (teorema di Konig).

Supponiamo per assurdo che esista un matching con più elementi di un covering. E' impossibile in quanto almeno un arco del matching non toccherebbe nessun vertice del covering.

Ora dimostriamo che il maggior matching possibile sia un covering. Prendiamo tutti gli archi che non appartengono al matching. Per ciascuno di essi stabiliamo che appartiene al covering il vertice toccato da un arco del matching che esso tocca. A questo punto poniamo che l'altro vertice non appartenga al covering e procediamo per passaggi obbligati, finché ce ne sono. In nessun arco abbiamo colorato i 2 vertici, perché se così fosse stato, allora sarebbe esistito un percorso che parte da un punto esterno al matching, poi passa per un arco esterno al matching ed uno interno alternativamente (può passare da un arco all'altro se e solo se hanno un vertice in comune) e finisce in un punto esterno al matching, ma ciò è impossibile visto che abbiamo scelto il matching più grande possibile. A questo punto scegliamo un colore e per ogni arco appartenente al matching di cui ancora nessun vertice appartiene al covering, poniamo che ciascun vertice che esso tocca e di quel colore appartenga al covering. Il covering che abbiamo ottenuto ha la stessa cardinalità del maggior matching possibile, è dunque il minimo covering possibile.

Per ottenere il lemma dei matrimoni, resta da dimostrare che non esistono covering di $ n-1 $ vertici. Supponiamo per assurdo che esista: abbiamo che $ k $ uomini e $ n-k-1 $ donne appartengono al covering. Ma sceglieno gli $ n-k $ uomini non appartenenti al covering abbiamo che $ n-k $ donne sono collegate con almeno uno di loro, per cui almeno un arco non ha nessun vertice appartenente al covering e ciò contraddice la definizione.

Il "solo se" del lemma di Hall è banale.
Ultima modifica di piever il 22 ott 2006, 23:03, modificato 1 volta in totale.
"Sei la Barbara della situazione!" (Tap)
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Teorema dell'accoppiamento di Hall

Messaggio da fph »

MindFlyer ha scritto:Vorremmo poter organizzare dei matrimoni tra persone compatibili, in modo che ogni uomo risulti sposato (e ovviamente che ogni donna sia sposata con al più un uomo).
Invece un uomo può essere sposato con piu' donne?
Simpatico questo Hall...
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Re: Teorema dell'accoppiamento di Hall

Messaggio da SkZ »

MindFlyer ha scritto:Tutti (uomini e donne) devono essere monogami oppure non sposati. Inoltre, vogliamo che ogni uomo sia sposato, ma non è necessario che ogni donna lo sia.
a quanto pare Hall non e' per la poligamia, ma non chiude la porta all'adulterio maschile :wink:
Dovrebbe essere possibile negli stati russi ove ci sono piu' donne che uomini.
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
MindFlyer

Messaggio da MindFlyer »

In realtà quello che interessa è un matching massimale di un grafo bipartito, ma si vede facilmente che questo è equivalente a ciò che dice il testo (sia permettendo adulterio maschile, sia proibendolo).
dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: Teorema dell'accoppiamento di Hall

Messaggio da dario2994 »

Bon... piazzo una dimostrazione che mi è venuta in pochissimo tempo, forse per miracolo, forse perchè è segata, e che mi pare del tutto diversa da quella di piever. (faccio solo una freccia, l'altra è banale)

Definisco:
$M$ l'insieme dei ragazzi, $F$ quello delle ragazze
$f:\mathcal{P}(M)\to \mathcal{P}(F)$ una funzione tale che dato $X\subseteq M$ allora $f(X)$ è l'insieme delle ragazze che complessivamente sono compatibili con i ragazzi in $X$.
un sottinsieme bello dei ragazzi è un $X\subseteq M$ tale che $|X|=|f(X)|$
Il testo, tradotto in questi termini, mi dice che $\forall X\subseteq M:\ |f(X)|\ge |X|$ e che $\forall X,Y\subseteq M:\ f(X\cup Y)=f(X)\cup f(Y)$
Ed ora il punto clue della dimostrazione:

Lemma del sogno b: Se $I,J\subseteq M$ sono sottoinsiemi belli allora anche $I\cup J$ è bello.
Prima di tutto vale banalmente $\displaystyle f(I\cap J)\subseteq f(I)\cap f(J)$ e quindi $|f(I\cap J)|\le |f(I)\cap f(J)|$
E ora la dimostrazione del lemma:
$\displaystyle |I\cup J|\le |f(I\cup J)|=|f(I)\cup f(J)|=|f(I)|+|f(J)|-|f(I)\cap f(J)|\le |I|+|J|-|f(I\cap J)|\le$
$\le |I|+|J|-|I\cap J|=|I\cup J|$
perciò $|I\cup J|=|f(I\cup J)$ e perciò $I\cup J$ per definizione è bello

Ora forte del lemma dimostro il lemma dei matrimoni per induzione sul numero di ragazzi:
Passo base: Un ragazzo... più che credibile
Passo induttivo: Scelgo un ragazzo $r\in M$.
Se esiste una ragazza $g\in f(\{r\})$ tale che dato $X\subseteq M\backslash\{r\}$ allora $g\in f(X)$ implica che $X$ non è bello. In questo caso faccio sposare $r,g$ ed è chiaro che le ipotesi del teorema continuano a valere con $M\backslash\{r\}$ e $F\backslash\{g\}$ e inoltre il numero dei ragazzi è diminuito di 1, quindi per ipotesi induttiva è dimostrato.
Se per assurdo tale ragazza non esiste allora definisco $f(\{r\})=\{g_1,g_2,\dots g_k\}$. Chiamo $X_i\subseteq M\backslash\{r\}$ il sottoinsieme bello tale che $g_i\in f(X_i)$. Chiamo $\displaystyle S=\bigcup_{i=1}^k X_i$.
Per il lemma del sogno b $S$ è bello. Inoltre per definizione vale $f(\{r\})\subseteq f(S)$ e $r\notin S$.
Perciò risulta $|S|+1=|S\cup\{r\}|\le|f(S\cup\{r\})|=|f(I)\cup f(\{r\}))|=|f(S)|=|S|$ che mostra l'assurdo :D
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Rispondi