Grafi e matching, Ricerca operativa

StudentiDia Forum - Roma Tre [Fornito da Invision Power Board] http://forum.studentidia.org/index.php?act=Print&client=printer&f=105&...

Versione Stampabile della Discussione

Clicca qui per visualizzare questa discussione nel suo formato originale

StudentiDia Forum - Roma Tre _ Ricerca Operativa II _ Teorema di Hall

Inviato da: beatjay il Jul 1 2010, 09:12

Avevo scritto questo post a gennaio, prima del crash del forum.

Grazie a Marco Di Bartolomeo che l'ha prontamente recuperato prima che sparisse dalla cache di Google

Definizioni preliminari.

Sia un grafo e sia .

Chiamiamo vicinato di l'insieme di tutti i nodi che non appartengono a tali che esista un arco per

qualche :

In altre parole, il vicinato di un certo sottoinsieme di nodi Q è l'insieme dei nodi adiacenti ai nodi di Q.

Enunciato del teorema di Hall.

Un grafo bipartito ammette un matching M, X-perfetto se e solo se vale la seguente condizione:

(condizione di Hall)

Dimostrazione.

(Se)

Supponiamo di avere un matching X-perfetto che chiamiamo M. Sia n una funzione che associa ad ogni nodo di X il suo

compagno secondo il matching M:

t.c.

Preso un qualsiasi , sia l'insieme dei nodi di Y che sono accoppiati a qualche nodo di Q. Per definizione

di matching, si ha che

Inoltre, certamente è valida l'osservazione che , perché per un nodo di Y non può essere accoppiato ad

un nodo di Q se non è perlomeno nel suo vicinato.

Questo implica

(Solo se)

Supponiamo di aver costruito una rete di flusso a partire dal grafo bipartito G, come indicato nella dimostrazione del

teorema di Konig.

Supponiamo di avere individuato un taglio s-t di capacità minima , dove indica l'insieme dei nodi

raggiungibili da s nella rete incrementale.

Siano (l'insieme dei nodi della partizione X raggiungibili da s)

(l'insieme dei nodi della partizione Y raggiungibili da s).

Osservazioni.

1 di 2 09/09/2010 20.35

StudentiDia Forum - Roma Tre [Fornito da Invision Power Board] http://forum.studentidia.org/index.php?act=Print&client=printer&f=105&...

Gli archi di un qualsiasi taglio (definizione di insieme di taglio: possono essere

solo di tre tipi:

archi che vanno da a nodi di (di capacità 1)

archi che vanno da nodi di a nodi di (di capacità infinita)

archi che vanno da a (di capacità 1)

Poiché qualsiasi flusso ha valore finito, anche il taglio minimo avrà capacità finita: quindi gli archi di tipo 2, avendo

capacità infinita, non possono far parte del taglio di capacità minima.

Gli archi di tipo 1 e 3, gli unici che possono far parte del taglio di capacità minima, hanno capacità unitaria: quindi la

capacità del taglio minimo sarà pari alla sua cardinalità. Per quanto appena detto tale cardinalità è pari a

Veniamo alla dimostrazione vera e propria: supponiamo per assurdo che M non sia X-perfetto, ovvero .

Per i teoremi di Konig e di Ford e Fulkerson, (C sta per cover) = |min cut|. Abbiamo

individuato nel passo precedente la cardinalità del taglio minimo. Possiamo allora scrivere:

Poiché non esistono archi nel matching che vanno da a , il vicinato di deve trovarsi nei restanti

nodi di Y:

Questo implica:

che viola la condizione di Hall, portando ad un assurdo. Quindi M dev'essere X-perfetto, e questo conclude la

dimostrazione.

(Nota: la dimostrazione non è mia. Si tratta della trascrizione delle registrazioni delle lezioni. Di mio c'è solo

l'interpretazione di alcuni passaggi a volte oscuri o inintellegibili, ma l'ho vista e rivista a fondo e mi sembra che non faccia

una piega. Fatemi sapere )

Fornito da Invision Power Board (http://www.invisionboard.com)

© Invision Power Services (http://www.invisionpower.com)

2 di 2 09/09/2010 20.35

E' la stessa dimostrazione

delle pagine precedenti,

solo scritta in maniera un

pochino meno ordinata ;)