Zaawansowane algorytmy i struktury danych/Wykład 7: Różnice pomiędzy wersjami

Wersja z 08:42, 24 lip 2006

Abstrakt

W wykładzie tym skoncentrujemy się na problemie znajdowania najliczniejszych skojarzeń w grafach dwudzielnych. Zaczniemy od przedstawienia idei ścieżek powiększających, a następie użyjemy jej do konstrukcji algorytmu znajdującego maksymalne skojarzenie w grafie $G = (V, E)$ w czasie $O (| V | | E |)$ . Następnie przedstawimy algorytm Hopcrofta-Karpa, który działać będzie w czasie czasie $O (\sqrt{| V |} | E |)$ .

Problem maksymalnego skojarzenia w grafie dwudzielnym

Niech $G = (V, E)$ będzie grafem nieskierowanym. Skojarzeniem w grafie $G$ nazywamy każdy podzbiór krawędzi $M \subseteq E$ taki, w którym co najwyżej jedna krawędź z $M$ jest incydentna z każdym wierzchołkiem w $V$ . O wierzchołku $v$ incydentnym do pewniej krawędzi z $M$ mówimy, że jest skojarzony, w przeciwnym przypadku $v$ nazywamy wolnym. Podobnie jeżeli krawędź $e$ należy do skojarzenia to mówimy, że jest ona skojarzona a w przeciwnym wypadku mówimy, że jest to krawędź wolna. Skojarzenie $M$ nazywamy maksymalnym gdy ma ono największą liczność spośród skojarzeń w $G$ . W trakcie tego wykładu zajmiemy się tylko problemem znajdowania skojarzeń w grafach dwudzielnych czyli takich w których zbiór wierzchołków można podzielić na $V = V_{1} \cup V_{2}$ gdzie $V_{1}$ i $V_{2}$ są rozłączne, a wszystkie krawędzie z $E$ prowadzą pomiędzy $L$ i $R$ .

Ścieżki powiększające

Ścieżką powiększającą nazwiemy ścieżkę prostą $p$ taką, że jej krawędzie są na przemian skojarzone i wolne, a końce są wolne. Łatwo zauważyć, że jeżeli istnieje ścieżka powiększająca $p$ względem $M$ to $M$ nie jest skojarzeniem maksymalnym. Używając wtedy ścieżki $p$ możemy skonstruować skojarzenie większe biorąc $M = M \oplus E (p)$ , czyli zamieniając na ścieżce krawędzie wolne na skojarzone i na odwrót. Możemy pokazać także pokazać przeciwne wynikanie:

Twierdzenie 1 [Twierdzenie Berge'a]

Skojarzenie

M

jest maksymalne gdy nie istnieje względem niego żadna ścieżka powiększająca.

Dowód

Załóżmy przeciwnie, że istnieje skojarzenie

M^{'}

liczniejsze niż

M

. Rozważmy graf

G^{'} = (V, M \oplus M^{'})

. Zauważmy, że w

G^{'}

każdy wierzchołek ma stopień co najwyżej

2

, w związku z tym

G^{'}

składa się z rozłącznych ścieżek i cykli. Na każdym cyklu występuje tyle samo krawędzi z

M

co

M^{'}

. Natomiast na ścieżkach może występować co najwyżej o jedną krawędź więcej z któregoś skojarzenia. W grafie

G^{'}

jest więcej krawędzi z

M^{'}

niż z

M

, a zatem musi też istnieć ścieżka na której jest więcej krawędzi z

M^{'}

. Musi to być oczywiście ścieżka powiększająca.

Algorytm wykorzystujący ścieżki powiększające

Zastanówmy się teraz jak efektywnie sprawdzić sprawdzić, czy w grafie dwudzielnym nie ma ścieżki powiększającej, bądź jeżeli jest to ją znaleźć. Dla grafu dwudzielnego $G = (V_{1} \cup V_{2}, E)$ oraz skojarzenia $M$ zdefiniujmy skierowany graf $G_{M} = (v_{1} \cup V_{2}, E_{M})$ jako

E = {(v_{1}, v_{2}) : v_{1} v_{2} \in E, v_{1} \in V_{1}, v_{2} \in V_{2}} \cup {(v_{2}, v_{1}) : \in M, v_{1} \in V_{1}, v_{2} \in V_{2}} .

Algorytm znajdowania ścieżki powiększającej

 ZNAJDŹ-ŚCIEŻKĘ-POWIĘKSZAJĄCĄ(G = (V_1 \cup V_2,E),M)
 1   ${V_{1}}^{'} =$  zbiór wierzchołków wolnych w  $V_{1}$ 
 2   ${V_{2}}^{'} =$  zbiór wierzchołków wolnych w  $V_{2}$ 
 3  skonstruuj graf skierowany  $G_{M} = (V_{1} \cup V_{2}, E_{M})$ 
 5  znajdź ścieżkę  $p$  z  ${V_{1}}^{'}$  do  ${V_{2}}^{'}$  w  $G_{M}$ 
 6  if  $p$  nie istnieje then
 7    return NIL (nie ma ścieżki powiększającej)
 8  return  $p$  ( $p$  to ścieżka powiększająca w  $G$ )

Lemat 2

Powyższy algorytm znajduje ścieżkę

p

wtedy i tylko wtedy gdy w

G

istnieje ścieżka powiększająca względem

M

. Co więcej znaleziona ścieżka jest ścieżką powiększającą.

Dowód

Załóżmy, że ścieżka

p

istnieje jest to ścieżka, która

zaczyna się w wierzchołku wolnym,
z $V_{1}$ do $V_{2}$ idzie krawędzią wolną,
z $V_{2}$ do $V_{1}$ wraca krawędzią skojarzoną,
kończy się w $V_{2}$ krawędzią wolną.

Ścieżka $p$ spełnia wszystkie warunki dla ścieżki powiększającej oprócz bycia ścieżką prostą. Jeżeli $p$ przechodzi dwa razy przez ten sam wierzchołek $v \in V_{1}$ , to wchodzi do niego dwa razy krawędzią skojarzoną, a wychodzi krawędzią nieskojarzoną. Jeżeli teraz usuniemy kawałek ścieżki pomiędzy tymi dwoma wejściami do $v$ to powyższe cztery warunki nadal będą zachodzić. Możemy więc zachowując je zamienić ścieżkę $p$ na ścieżkę prostą.

Natomiast jeżeli w grafie

G

jest ścieżka powiększająca względem

M

to możemy ją wprost przetłumaczyć na ścieżkę w gafie

{G_{M}}^{'}

.

Jesteśmy już gotowi na konstrukcję pierwszego algorytmu znajdującego maksymalne skojarzenia w grafie dwudzielnym.

Algorytm znajdujący maksymalne skojarzenie w grafie dwudzielnym

 MAKSYMALNE-SKOJARZENIE(G = (V_1 \cup V_2,E))
 1   $M = \emptyset$ 
 1  repeat
 2     $p =$ ZNAJDŹ-ŚCIEŻKĘ-POWIĘKSZAJĄCĄ $(G, M)$ 
 3    if  $p \neq N I L$  then
 4       $M = M \oplus p$ 
 6  until  $p = N I L$ 
 5  return  $M$

Poprawność tego algorytmu wynika z Lematu 2 oraz Twierdzenia Bergea. Ponieważ $\frac{| V |}{2}$ jest ograniczeniem górnym na rozmiar maksymalnego skojarzenia, a w każdym kroku pętli rozmiar skojarzenia rośnie o $1$ , to pętla ta zostanie wykonana co najwyżej $O (| V |)$ razy. Wyszukanie jednej ścieżki powiększającej zajmuje czas $O (| E |)$ , a więc całkowity czas działania algorytmu to $O (| V | | E |)$ .

Algorytm Hopcrofta-Karpa

Algorytm Hopcrofta-Karpa także wykorzystuje technikę ścieżek powiększających. Jednak w celu przyśpieszenia działania tej metody, zamiast wyszukiwać ścieżki pojedynczo, będziemy szukać wielu ścieżek na raz. Będziemy to robić jednak w taki sposób aby długości tych ścieżek systematycznie rosły, będziemy mogli skorzystać wtedy z następującego lematu, który mówi, że długich ścieżek jest.

Lemat 3

Niech

M^{*}

będzie skojarzeniem maksymalnym, a

M

pewnym dowolnym skojarzeniem w

G

. Jeżeli długość najkrótszej ścieżki powiększającej względem

M

wynosi

k

, to

| M^{*} | - | M | \leq \frac{| V |}{k}

.

Dowód

Podobnie jak w dowodzie Twierdzenia Berge'a rozważmy graf

G^{'} = (V, M \oplus M^{'})

. Graf ten zawiera co najwyżej

| M^{*} | - | M |

ścieżek powiększających względem

M

, długość każdej z tych ścieżek musi być co najmniej

k

. Sumaryczna długość tych ścieżek nie przekracza

| V |

, a wiec nie może ich być więcej niż

\frac{| V |}{k}

.

Maksymalny zbiór rozłącznych wierzchołkowy ścieżek powiększających

W celu zagwarantowania wzrostu długości ścieżek po każdej fazie będziemy wyszukiwać maksymalnego zbioru rozłącznych wierzchołkowo najkrótszych ścieżek powiększających $P$ . Pokażemy teraz, że po powiększeniu skojarzenia przy pomocy wszystkich tych ścieżek długość najkrótszej ścieżki rośnie. Oznaczmy przez $M \oplus P = M \oplus ⨁_{p \in P} p$ .

Lemat 4

Niech

P

będzie maksymalnym rozłącznym wierzchołkowo zbiorem najkrótszych ścieżek powiększających względem

M

, wtedy długość najkrótszej ścieżki powiększającej względem

M \oplus P

jest większa niż długość najkrótszej ścieżki powiększającej względem

M

.

Dowód

Weźmy najkrótszą ścieżkę powiększająca

π^{'}

względem

M \oplus P

. Ścieżka ta musi przecinać się ze pewną ścieżką

π

ze zbioru

P

inaczej mówilibyśmy powiększyć

P

o

π

. Pokażemy teraz, że

| π^{'} | \geq | π | + 1

.

Niech $u_{1}$ i $u_{2}$ będą odpowiednio pierwszym i ostatnim wierzchołkiem wspólnym dla ścieżek $π$ i $π^{'}$ . Natomiast niech $v_{1}$ będzie początkiem ścieżki $π$ , a $v_{2}$ jej końcem. Podobnie niech ${v_{1}}^{'}$ i ${v_{2}}^{'}$ będą początkiem i końcem ścieżki $π^{'}$ . Z ścieżek $π$ i $π^{'}$ możemy skonstruować dwie nowe ścieżki $R_{1}$ i $R_{2}$ . Niech $R_{i}$ idzie kawałkiem ścieżki $π$ z $v_{i}$ do $u_{i}$ , a następnie kawałkiem ścieżki $π^{'}$ z $u_{i}$ do ${v_{i}}^{'}$ . Sumaryczna długość ścieżek $R_{1}$ i $R_{2}$ jest mniejsza o co najmniej $1$ od długości ścieżek $π$ i $π^{'}$ , możemy wiec zapisać:

| R_{1} | + | R_{2} | + 1 \leq | π | + | π^{'} | .

Zauważmy, że ścieżki te są ścieżkami powiększającymi względem $M$ . Ich długości muszą być co najmniej takie jak długość ścieżki $π$ i:

1 \leq - | π | + | π^{'} |,

co kończy dowód lematu.

Zajmijmy się teraz algorytmem konstrukcji zbioru ścieżek $P$ . W konstrukcji tej użyjemy trochę zmodyfikowanej procedury DFS.

Algorytm częściowego DFS

 CZĘŚCIOWE-DFS $(G, v, T)$ 
 1  uruchom DFS(G,v) aż do momentu znalezienia pierwszego wierzchołka ze zbioru  $T$ 
 2  usuń wszystkie odwiedzone wierzchołki w procedurze DFS z grafu  $G$ 
 2  if istnieje ścieżka  $p$  z  $v$  do  $T$  then
 4    return p
 5  else
 6    return NIL

Procedura ta różni się od standardowej procedury DFS dwoma rzeczami. Po pierwsze prowadzi wyszukiwanie tylko do momentu znalezienia wierzchołka z $T$ . Po drugie po zakończonym wyszukiwaniu usuwa wszystkie odwiedzone wierzchołki, tak aby każda następna znaleziona ścieżka przez nie nie przechodziła. Procedure tą wykorzystamy w do grafu warstwowego ${\overline{G}}_{M}$ skonstruowanego z grafu $G_{M}$ . Niech ${V_{1}}^{'}$ oznacza zbiór wierzchołków wolnych w $V_{1}$ . Oznaczmy przez $d : V \to 𝒩$ odległość $d (v)$ wierzchołka $v$ od wierzchołków z ${V_{1}}^{'}$ . Graf ${\overline{G}}_{M} = (V_{1} \cup V_{2}, {\overline{E}}_{M})$ ma następujący zbiór krawędzi:

\overline{E}_M = \{(u,v): (u,v) \in E_M \mbox{ i } d(u) + 1 = d(v)\}.

Lemat 5

Każda ścieżka w grafie

{\overline{G}}_{M}

zaczynająca się w

{V_{1}}^{'}

jest najkrótszą ścieżką w grafie

G_{M}

.

Dowód

Lemat ten wynika wprost z definicji najkrótszej ścieżki, tzn. ścieżka jest najkrótsza jeżeli jej długość jest równa odległości z jej początku do jej końca.

Lemat ten pozwala nam na konstrukcję następującego algorytmu wyszukującego maksymalny zbiór wierzchołkowo rozłącznych najkrótszych ścieżek powiększających.

Algorytm znajdujący maksymalny zbiór wierzchołkowo rozłącznych najkrótszych ścieżek powiększających

 MAKSYMALNY-ZBIÓR-NAJKRÓTSZYCH-ŚCIEŻEK(G = (V_1 \cup V_2,E),M)
 1   $P = \emptyset$ 
 2  skonstruuj graf  ${\overline{G}}_{M} = (V_{1} \cup V_{2}, {\overline{E}}_{M})$ 
 3  niech  ${V_{1}}^{'}$  będzie zbiorem wierzchołków wolnych w  $V_{1}$ 
 4  for  $v \in {V_{1}}^{'}$  do
 5  begin
 6     $p =$ CZĘŚCIOWE-DFS $(G, v, T)$ 
 7    if  $p \neq N I L$  then
 8       $P = P \cup p$  
 9  end
 10 return  $P$

Lemat 6

Algorytm MAKSYMALNY-ZBIÓR-NAJKRÓTSZYCH-ŚCIEŻEK znajduje maksymalny zbiór wierzchołkowo rozłącznych ścieżek powiększających względem

M

w czasie

O (E)

.

Dowód

Zauważmy, że czas działania

O (| E |)

algorytmu wynika z konstrukcji CZĘŚCIOWE-DFS, która rozpatruje każdy wierzchołek tylko raz, a zatem także każda krawędź rozpatrywana jest tylko raz. Co więcej usuwanie przejrzanych wierzchołków gwarantuje, że

P

zawiera ścieżki wierzchołkowo rozłączne. To, że są to ścieżki najkrótsze wynika natomiast z Lematu 5.

Algorytm

Zapiszmy teraz algorytm Hopcrofta-Karpa.

Algorytm Hopcrofta-Karpa

 HOPCROFT-KARP(G = (V_1 \cup V_2))
 1   $M = \emptyset$ 
 2  repeat
 3     $P =$ MAKSYMALNY-ZBIÓR-NAJKRÓTSZYCH-ŚCIEŻEK $(G = (V_{1} \cup V_{2}, E), M)$ 
 4    if  $P \neq N I L$  then
 5       $M = M \oplus P$ 
 6  until  $P = N I L$ 
 7  return M

Twierdzenie 7

Algorytm Hopcrofta-Karpa znajduje maksymalne skojarzenie w grafie dwudzielnym w czasie

O (\sqrt{(} n) m)

.

Dowód

Poprawność algorytmu wynika z Twierdzenia Berge'a ponieważ, jeżeli graf zawiera ścieżkę powiększającą, to zbiór

P

nie będzie pusty. Lemat 4 mówi, że po każdym wykonaniu głównej pętli algorytmu długość najkrótszej ścieżki powiększającej jest większa o co najmniej 1. Dlatego po

\sqrt{| V |}

krokach wynosić będzie ona co najmniej

\sqrt{| V |}

. Z Lematu 3 wiemy, że w takim wypadku pozostało nam jeszcze nie więcej niż

\sqrt{| V |}

ścieżek do znalezienia i zostanie jeszcze wykonanych co najwyżej

\sqrt{| V |}

obrotów pętli. W sumie pętla wykonana będzie nie więcej niż

2 \sqrt{| V |}

razy. Każde wykonanie pętli zajmuje czas

O (| E |)

(Lemat 6, a więc całkowity czas działania algorytmu wynosi

O (\sqrt{| V |} | E |)

.

@@ Linia 5: / Linia 5: @@
 == Problem maksymalnego skojarzenia w grafie dwudzielnym ==
-Niech <math>G=(V,E)</math> będzie grafem nieskierowanym. {{kotwica|skojarzenie|'''Skojarzeniem'''}} w grafie <math>G</math> nazywamy każdy podzbiór krawędzi <math>M\subseteq E</math> taki, w którym co najwyżej jedna krawędź z <math>M</math> jest incydentna z każdym wierzchołkiem w <math>V</math>. O wierzchołku <math>v</math> incydentnym do pewniej krawędzi z <math>M</math> mówimy, że jest '''skojarzony''', w przeciwnym przypadku <math>v</math> nazywamy '''wolnym'''. Podobnie jeżeli krawędź <math>e</math> należy do skojarzenia to mówimy, że jest ona '''skojarzona''' a w przeciwnym wypadku mówimy, że jest to krawędź '''wolna'''. Skojarzenie <math>M</math> nazywamy {{kotwica|maksymalne_skojarzenie|'''maksymalnym'''}} gdy ma ono największą liczność spośród skojarzeń w <math>G</math>. Na trakcie tego wykładu zajmiemy się tylko problemem znajdowania skojarzeń w {{kotwica|graf_dwudzielny|'''grafach dwudzielnych'''}} czyli takich w których zbiór wierzchołków można podzielić na <math>V = V_1\cup V_2</math> gdzie <math>V_1</math> i <math>V_2</math> są rozłączne, a wszystkie krawędzie z <math>E</math> prowadzą pomiędzy <math>L</math> i <math>R</math>.
+Niech <math>G=(V,E)</math> będzie grafem nieskierowanym. {{kotwica|skojarzenie|'''Skojarzeniem'''}} w grafie <math>G</math> nazywamy każdy podzbiór krawędzi <math>M\subseteq E</math> taki, w którym co najwyżej jedna krawędź z <math>M</math> jest incydentna z każdym wierzchołkiem w <math>V</math>. O wierzchołku <math>v</math> incydentnym do pewniej krawędzi z <math>M</math> mówimy, że jest '''skojarzony''', w przeciwnym przypadku <math>v</math> nazywamy '''wolnym'''. Podobnie jeżeli krawędź <math>e</math> należy do skojarzenia to mówimy, że jest ona '''skojarzona''' a w przeciwnym wypadku mówimy, że jest to krawędź '''wolna'''. Skojarzenie <math>M</math> nazywamy {{kotwica|maksymalne_skojarzenie|'''maksymalnym'''}} gdy ma ono największą liczność spośród skojarzeń w <math>G</math>. W trakcie tego wykładu zajmiemy się tylko problemem znajdowania skojarzeń w {{kotwica|graf_dwudzielny|'''grafach dwudzielnych'''}} czyli takich w których zbiór wierzchołków można podzielić na <math>V = V_1\cup V_2</math> gdzie <math>V_1</math> i <math>V_2</math> są rozłączne, a wszystkie krawędzie z <math>E</math> prowadzą pomiędzy <math>L</math> i <math>R</math>.
 == Ścieżki powiększające ==

Zaawansowane algorytmy i struktury danych/Wykład 7: Różnice pomiędzy wersjami

Wersja z 08:42, 24 lip 2006

Spis treści

Abstrakt

Problem maksymalnego skojarzenia w grafie dwudzielnym

Ścieżki powiększające

Algorytm wykorzystujący ścieżki powiększające

Algorytm Hopcrofta-Karpa

Maksymalny zbiór rozłącznych wierzchołkowy ścieżek powiększających

Algorytm

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia