L’Accoppiamento
su un grafo Bipartito
Il problema dell’Accoppiamento per
un grafo bipartito è un caso speciale discusso nel precedente capitolo
utilizzando il metodo sulla ricerca del cammino aumentante. La ricerca
di un percorso aumentante deve cominciare costruendo un percorso alternante
dai vertici scoperti. Poiché un percorso aumentante deve avere un
estremo in V e l’altro in U, senza perdere di generalità,
si inizia con percorsi alternanti solo da vertici scoperti di V (
per esempio v2 ) e ricercare tutti i possibili percorsi alternanti da v2
simultaneamente. Iniziando da v2 , si possono cercare percorsi alternanti
considerando tutti i vertici adiacenti a v2. Nel nostro caso chiamati
u2 e u6. Finora si ha che v2 risulta scoperto, tutti i corrispondenti margini
adiacenti risultano liberi. Dalla definizione di un percorso alternante,
noi dobbiamo vedere gli archi accoppiati ad u2 e u6 . Questo è
un passo iniziale, fino adesso tutti i nodi hanno al più un nodo
accoppiato. Naturalmente, se u2 o u6 fossero scoperti il nostro compito
sarebbe quello di scoprire un percorso aumentante. Comunque, continuando
con il caso preso in esame, addizioniamo il nodo v3 e v5 al nostro insieme
composto dai nodi formanti i percorsi alternati. Per costruzione, v3 e
v5 sono vertici esterni. Continuiamo, quindi, a sviluppare percorsi alternanti
da v3 e v5 . Osserviamo che il nodo u3 è raggiunto da v3 , prima
di analizzare v5 , omettiamo l’arco. Scopriamo che i nuovi vertici
esterni sono v4 , v1 e v6. Adesso finalmente si osserva che il vertice
esterno v1 è adiacente al vertice esterno u1. Noi abbiamo così
scoperto un percorso aumentante e quindi si può aumentare M
usando questo. L’idea della procedura di ricerca dei percorsi aumentanti
è pensare ad una ricerca in ampiezza. Comunque, guardando indietro
alla costruzione dei percorsi alternanti si può notare che questa
prima ricerca in ampiezza ha una speciale struttura. Le ricerche dai livelli
dispari sono di poca importanza perché solo il vertice successivo
è quello accoppiato. E’ possibile così semplificare questa
tecnica di ricerca ignorando i livelli dispari e andando direttamente dai
vertici esterni ai nuovi vertici esterni. Nel nostro esempio, l’ideale
è ricercare un procedimento come mostrato nella figura mobile
dell' esempio.
Ovviamente, questo corrisponde
a ricercare un diagramma (V,A) dove (v1,v2) appartengono
ad A se e solo se v2 può essere il vertice esterno prossimo
di v1 in un percorso aumentante; v1 è adiacente all’accoppiato
di v2 . L’insieme dei nodi di questo diagramma ausiliare è V, naturalmente
soltanto i vertici di V possono diventare vertici esterni in percorsi alternanti
avviati da V.
La ricerca per percorsi aumentanti
può facilmente essere vista come una prima ricerca in ampiezza del
grafo ausiliare avviato dal nodo v2 .
Il nostro potenziale algoritmo
di ricerca dell’accoppiamento su un grafo assegnato bipartito si basa su
due termini : accoppiato e scoperto. A fianco di questi si introduce il
termine etichetta che serve poi per la ricerca. Il termine accoppiato ha
entrate e l’intenzione è quella di rappresentare l’accoppiamento
corrente . Per , è un nodo di U che è scoperto
ed è adiacente a v ; se tale nodo non esiste allora scoperto[v]=0.
Ovviamente, se un nodo con è incontrato
nella nostra ricerca, noi abbiamo scoperto un percorso aumentante. La procedura
aumentante è ricorsiva.
Teorema1
L’algoritmo in questione risolve
il problema dell’Accoppiamento per un grafo bipartito B=(V,U,E)
in O(min(|V|,|U|)|E|) tempo.
Il problema dell’Accoppiamento
bipartito e il flusso di reti
Nel paragrafo precedente si è
visto come un algoritmo può risolvere il problema dell’Accoppiamento
per un grafo bipartito in un tempo O(min(/V/,/U/)/E/) . E’ intenzione,
in questa sezione, di migliorare la velocità. Per arrivare a questo
fine conviene ridursi al problema del massimo flusso per semplici
reti. Di conseguenza, si può far vedere come risolvere il problema
dell’accoppiamento bipartito in modo efficiente usando un algoritmo che
risolve altrettanto efficientemente il problema del massimo flusso.
Lemma1 :
La cardinalità del massimo
accoppiamento in un grafo bipartito B è uguale al valore del massimo
(s,t)-flusso in N(B).
La dimostrazione del lemma 1 è
di tipo costruttivo e permette di trovare il massimo accoppiamento di B
da un flusso massimo in N(B) con un tempo O(/V/) .
Teorema2 :
E’ possibile risolvere il problema
dell’accoppiamento per un grafo bipartito in un tempo O[sqrt(/V/) /E/]
.
Questo metodo è asintoticamente
il più veloce algoritmo conosciuto per la risoluzione del problema
dell’accoppiamento bipartito.
Dato M un accoppiamento in un grafo
G=(V,E) e sia T=(V’,E’) un albero alternante rispetto a M. Un albero fiorito
si ottiene aggiungendo a T un arco, che non appartiene a M, tra due nodi
marcati. I nodi e gli archi facenti parte del ciclo sono in numero dispari
e costituiscono il fiore dell’albero. L’unico nodo del fiore lasciato scoperto
dagli archi del fiore stesso viene detto gambo del fiore.
Se un grafo non è fiorito
rispetto al corrente accoppiamento, allora vuol dire che esso è
effettivamente bipartito. Analogamente anche quando il grafo ammette circuiti
disaccoppiati non fioriti come in figura 9 può essere effettuata
una ricerca dei percorsi aumentanti come nel caso bipartito. Di conseguenza
la modifica del nostro algoritmo si basa sulla presenza di un albero fiorito
e quindi la ricerca di validi cammini aumentanti. Per mantenere semplice
l’algoritmo, è sufficiente cercare percorsi aumentanti che partono
da un vertice scoperto alla volta come l’opposto a tutti i vertici scoperti
simultaneamente. Verificare l’esistenza della fioritura non è particolarmente
complicato. Una fioritura diventa rilevante per il nostro algoritmo se
prima viene individuata. Un caso, quest’ultimo, che avviene quando tutti
i suoi vertici sono entrambi esterni o accoppiati di vertici esterni. Questa
situazione è evidenziata in figura 11 per il grafo fiorito della
figura 10.
Accoppiamento in un grafo non
bipartito
Dato M un accoppiamento in un grafo
G=(V,E) e sia T=(V’,E’) un albero alternante rispetto a M. Un albero fiorito
si ottiene aggiungendo a T un arco, che non appartiene a M, tra due nodi
marcati. I nodi e gli archi facenti parte del ciclo sono in numero dispari
e costituiscono il fiore dell’albero. L’unico nodo del fiore lasciato scoperto
dagli archi del fiore stesso viene detto gambo del fiore.
Se un grafo non è fiorito
rispetto al corrente accoppiamento, allora vuol dire che esso è
effettivamente bipartito. Analogamente anche quando il grafo ammette circuiti
disaccoppiati non fioriti come in figura 9 può essere effettuata
una ricerca dei percorsi aumentanti come nel caso bipartito. Di conseguenza
la modifica del nostro algoritmo si basa sulla presenza di un albero fiorito
e quindi la ricerca di validi cammini aumentanti. Per mantenere semplice
l’algoritmo, è sufficiente cercare percorsi aumentanti che partono
da un vertice scoperto alla volta come l’opposto a tutti i vertici scoperti
simultaneamente. Verificare l’esistenza della fioritura non è particolarmente
complicato. Una fioritura diventa rilevante per il nostro algoritmo se
prima viene individuata. Un caso, quest’ultimo, che avviene quando tutti
i suoi vertici sono entrambi esterni o accoppiati di vertici esterni.
L’algoritmo da costruire è
una caratterizzazione del caso bipartito affrontato con il metodo dell’albero
fiorito. Come al solito, l’avvio per la ricerca dell’accoppiamento è
la soluzione vuota e successivamente si ricorre, più volte, alla
ricerca di un percorso aumentante a partire da ogni vertice scoperto. La
differenza sostanziale con il caso bipartito è nella ricerca di
un cammino aumentante. In questa variante il percorso aumentante è
cercato su un vertice scoperto alla volta e non da tutti insieme come fatto
nel caso bipartito. Se da un nodo scoperto u il cammino aumentante non
viene trovato, questo nodo non può più essere d’aiuto per
un’idonea rappresentazione.
Teorema 5:
L’algoritmo in questo caso
trova l’accoppiamento massimo in un grafo G=(V,E) in un tempo O(/V/**4)
.
|
Introduzione
/ Indice