Grafi e matching, Ricerca operativa

StudentiDia Forum - Roma Tre

Fornito da Invision Power Board Clicca qui per visualizzare questa discussione nel suo formato originale.

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 Q. Chiamiamo vicinato di Q l'insieme di tutti i nodi che non appartengono a Q tali che esista un arco per qualche q: (q, y). 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 Q, sia l'insieme dei nodi di Y che sono accoppiati a qualche nodo di Q. Per definizione di matching, si ha che n(Q) = |Q|. Inoltre, certamente è valida l'osservazione che n(Q) ≥ |Q|, perché un nodo di Y non può essere accoppiato ad un nodo di Q se non è perlomeno nel suo vicinato. Questo implica |N(Q)| ≥ |Q|.

(Solo se)

Supponiamo di aver costruito una rete di flusso a partire dal grafo bipartito G, come indicato nella dimostrazione del teorema di König. Supponiamo di avere individuato un taglio s-t di capacità minima c, dove c indica l'insieme dei nodi raggiungibili da s nella rete incrementale. Siano X_s (l'insieme dei nodi della partizione X raggiungibili da s) e Y_s (l'insieme dei nodi della partizione Y raggiungibili da s).

Osservazioni

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

• Archi che vanno da X_s a nodi di Y (di capacità 1)
• Archi che vanno da nodi di Y a nodi di X_s (di capacità infinita)
• Archi che vanno da Y_s a t (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à...