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

Wersja z 12:33, 21 wrz 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 $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 $V_{1}$ i $V_{2}$ .

Ś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 p$ , czyli zamieniając na ścieżce krawędzie wolne na skojarzone i na odwrót. Możemy pokazać także 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 w ś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ć, 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

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array}{r@{}c@{}l} {E}_M &=& \{(v_1, v_2): v_1v_2 \in E, v_1 \in V_1, v_2 \in V_2\}\\ &\cup& \{(v_2, v_1): v_1v_2 \in M, v_1 \in V_1, v_2 \in V_2\}. \end{array} }

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  $N I L$  (nie ma ścieżki powiększającej)
 8  usuń cykle z  $p$  tak aby  $p$  była ścieżką prostą
 9  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. Z konstrukcj algorytmu wiemy, że 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$ (linia 8) 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 aby skonstruować pierwszy algorytmu znajdujący maksymalne skojarzenie 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$

Wyszukiwanie ścieżki powiększającej zobrazowane jest na poniższej animacji.

<flash>file=Zasd_Ilustr_d.swf |width=600|height=300</flash>

Poprawność tego algorytmu wynika z Lematu 2 oraz Twierdzenia Berge'a. 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 mało.

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 w każdej fazie konstruuować maksymalny zbiór 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ą

π_{1}

ze zbioru

P

inaczej mówilibyśmy powiększyć

P

o

π_{1}

. Pokażemy teraz, że

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

. Kolejne fazy tego dowodu zobrazowane są na animacji poniżej. <flash>file=Zasd_ilustr_o.swf

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 w dwóch aspektach. Po pierwsze prowadzi wyszukiwanie tylko do momentu znalezienia wierzchołka ze zbioru $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. Procedurę tą zastosujemy 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} 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 najkrótszych ś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}, E))$ 
 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$

<flash>file=Zasd_Ilustr_h.swf |width=600|height=300</flash>

Twierdzenie 7

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

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

.

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 135: / Linia 135: @@
 }}
-Procedura ta różni się od standardowej procedury DFS w dwóch aspektach. Po pierwsze prowadzi wyszukiwanie tylko do momentu znalezienia wierzchołka ze zbioru <math>T</math>. 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. Procedurę tą zastosujemy do grafu warstwowego <math>\overline{G}_M</math>skonstruowanego z grafu <math>{G}_M</math>. Niech <math>V_1'</math> oznacza zbiór wierzchołków wolnych w <math>V_1</math>. Oznaczmy przez <math>d:V \to \mathcal{N}</math> odległość <math>d(v)</math>wierzchołka <math>v</math> od wierzchołków z <math>V_1'</math>. Graf <math>\overline{G}_M = (V_1\cup V_2, \overline{E}_M)</math> ma następujący zbiór krawędzi:
+Procedura ta różni się od standardowej procedury DFS w dwóch aspektach. Po pierwsze prowadzi wyszukiwanie tylko do momentu znalezienia wierzchołka ze zbioru <math>T</math>. 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. Procedurę tą zastosujemy do grafu warstwowego <math>\overline{G}_M</math>skonstruowanego z grafu <math>{G}_M</math>. Niech <math>V_1'</math> oznacza zbiór wierzchołków wolnych w <math>V_1</math>. Oznaczmy przez <math>d:V \to \mathcal{N}</math> odległość <math>d(v)</math> wierzchołka <math>v</math> od wierzchołków z <math>V_1'</math>. Graf <math>\overline{G}_M = (V_1\cup V_2, \overline{E}_M)</math> ma następujący zbiór krawędzi:
 {{wzor2|1=
@@ Linia 154: / Linia 154: @@
 {{algorytm|znajdujący maksymalny zbiór wierzchołkowo rozłącznych najkrótszych ścieżek powiększających|algorytm_max_ścieżki|3=
-   MAKSYMALNY-ZBIÓR-NAJKRÓTSZYCH-ŚCIEŻEK(G = (V_1 \cup V_2,E),M)
+   MAKSYMALNY-ZBIÓR-NAJKRÓTSZYCH-ŚCIEŻEK<math>(G = (V_1 \cup V_2,E),M)</math>
   <math>P=\emptyset</math>
   skonstruuj graf <math>\overline{G}_M = (V_1\cup V_2,\overline{E}_M)</math>
@@ Linia 168: / Linia 168: @@
 {{lemat|6|lemat_6|3=
-Algorytm MAKSYMALNY-ZBIÓR-NAJKRÓTSZYCH-ŚCIEŻEK znajduje maksymalny zbiór wierzchołkowo rozłącznych ścieżek powiększających względem <math>M</math> w czasie <math>O(E)</math>.
+Algorytm [[#algorytm_max_ścieżki|MAKSYMALNY-ZBIÓR-NAJKRÓTSZYCH-ŚCIEŻEK]] znajduje maksymalny zbiór wierzchołkowo rozłącznych najkrótszych ścieżek powiększających względem <math>M</math> w czasie <math>O(|E|)</math>.
 }}
@@ Linia 180: / Linia 180: @@
 {{algorytm|Hopcrofta-Karpa|algorytm_hopcrofta-karpa|3=
-   HOPCROFT-KARP(G = (V_1 \cup V_2))
+   HOPCROFT-KARP<math>(G = (V_1 \cup V_2,E))</math>
   <math>M = \emptyset</math>
   '''repeat'''
@@ Linia 187: / Linia 187: @@
       <math>M = M \oplus P</math>
   '''until''' <math>P = NIL</math>
-  '''return''' M
+  '''return''' <math>M</math>
 }}
@@ Linia 193: / Linia 193: @@
 {{twierdzenie|7|twierdzenie_7|3=
-Algorytm Hopcrofta-Karpa znajduje maksymalne skojarzenie w grafie dwudzielnym w czasie <math>O(\sqrt{n}m)</math>.
+Algorytm Hopcrofta-Karpa znajduje maksymalne skojarzenie w grafie dwudzielnym w czasie <math>O(\sqrt{|V|}|E|)</math>.
 }}
@@ Linia 199: / Linia 199: @@
 Poprawność algorytmu wynika z [[#twierdzenie_1|Twierdzenia Berge'a]] ponieważ, jeżeli graf zawiera ścieżkę powiększającą, to zbiór <math>P</math> nie będzie pusty.
-[[#lemat_4|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 <math>\sqrt{|V|}</math> krokach wynosić będzie ona co najmniej <math>\sqrt{|V|}</math>. Z [[#lemat_3|Lematu 3]] wiemy, że w takim wypadku pozostało nam jeszcze nie więcej niż <math>\sqrt{|V|}</math> ścieżek do znalezienia i zostanie jeszcze wykonanych co najwyżej <math>\sqrt{|V|}</math> obrotów pętli. W sumie pętla wykonana  będzie nie więcej niż <math>2\sqrt{|V|}</math> razy. Każde wykonanie pętli zajmuje czas <math>O(|E|)</math> ([[#lemat_6|Lemat 6]], a więc całkowity czas działania algorytmu wynosi <math>O(\sqrt{|V|}|E|)</math>.
+[[#lemat_4|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 <math>\sqrt{|V|}</math> krokach wynosić będzie ona co najmniej <math>\sqrt{|V|}</math>. Z [[#lemat_3|Lematu 3]] wiemy, że w takim wypadku pozostało nam jeszcze nie więcej niż <math>\sqrt{|V|}</math> ścieżek do znalezienia i zostanie jeszcze wykonanych co najwyżej <math>\sqrt{|V|}</math> obrotów pętli. W sumie pętla wykonana  będzie nie więcej niż <math>2\sqrt{|V|}</math> razy. Każde wykonanie pętli zajmuje czas <math>O(|E|)</math> ([[#lemat_6|Lemat 6]]), a więc całkowity czas działania algorytmu wynosi <math>O(\sqrt{|V|}|E|)</math>.
 }}

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

Wersja z 12:33, 21 wrz 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