Maksymalny niezależny zestaw wykresu dwudzielnego

Próbuję znaleźć maksymalny niezależny zestaw wykresu biparytu.

W niektórych notatkach „13 maja 1998 r. - University of Washington - CSE 521 - Zastosowania przepływu sieci” znalazłem :

Problem:

Biorąc pod uwagę dwudzielny wykres , znalezienie niezależnego zestawu , który jest tak duży, jak to tylko możliwe, w którym i . Zestaw jest niezależny, jeśli nie ma krawędzi między elementami zestawu.$G = (U,V,E)$$U' \cup V'$$U' \subseteq U$$V' \subseteq V$$E$

Rozwiązanie:

Zbuduj wykres przepływu na wierzchołkach . Dla każdej krawędzi istnieje nieskończona krawędź pojemności od do . Dla każdego istnieje krawędź pojemności jednostki od do , a dla każdego istnieje krawędź pojemności jednostki od do .$U \cup V \cup \{s,t\}$$(u,v) \in E$$u$$v$$u \in U$$s$$u$$v \in V$$v$$t$

Głębokość cięcia znajduje się skończone , z i . Niech i . Zestaw jest niezależny, ponieważ nie ma nieskończonych krawędzi pojemności przecinających cięcie. Rozmiar nacięcia to. Dzięki temu, aby niezależny zestaw był tak duży, jak to możliwe, tworzymy cięcie tak małe, jak to możliwe.$(S,T)$$s \in S$$t \in T$$U' = U \cap S$$V' = V \cap T$$U' \cup V'$$|U - U'| + |V - V'| = |U| + |V| - |U' \cup V'|$

Weźmy to jako wykres:

A - B - C
    |
D - E - F

Możemy podzielić to na dwuczęściowy wykres w następujący sposób $(U,V)=(\{A,C,E\},\{B,D,F\})$

Widzimy przez poszukiwaniu brute force, że jedynym Maksymalna niezależnego zestawu jest . Spróbujmy rozwiązać powyższe rozwiązanie:$A,C,D,F$

Tak więc zbudowana macierz przyległości sieci przepływowej byłaby:

$$\begin{matrix} & s & t & A & B & C & D & E & F \\ s & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ t & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ A & 1 & 0 & 0 & \infty & 0 & 0 & 0 & 0 \\ B & 0 & 1 & \infty & 0 & \infty & 0 & \infty & 0 \\ C & 1 & 0 & 0 & \infty & 0 & 0 & 0 & 0 \\ D & 0 & 1 & 0 & 0 & 0 & 0 & \infty & 0 \\ E & 1 & 0 & 0 & \infty & 0 & \infty & 0 & \infty \\ F & 0 & 1 & 0 & 0 & 0 & 0 & \infty & 0 \\ \end{matrix}$$

Tutaj utknąłem, najmniejsze ograniczone ograniczenie pojemności, jakie widzę, jest banalne: o pojemności 3.$(S,T) =(\{s\},\{t,A,B,C,D,E,F\})$

Zastosowanie tego cięcia prowadzi do nieprawidłowego rozwiązania:

$$U' = U \cap S = \{\}$$ $$V' = V \cap T = \{B,D,F\}$$ $$U' \cup V' = \{B,D,F\}$$

Podczas gdy spodziewaliśmy się ? Czy ktoś może dostrzec, gdzie popełniłem błąd w moim rozumowaniu / pracy?$U' \cup V' = \{A,C,D,F\}$

Uzupełnieniem maksymalnego niezależnego zestawu jest minimalna osłona wierzchołków.

Aby znaleźć minimalną osłonę wierzchołków na wykresie dwustronnym, zobacz twierdzenie Königa .

Podane rozwiązanie jest wyraźnie niepoprawne, jak wykazano w kontrprzykładzie. Zauważ, że wykres U + V jest składnikiem połączonym przez krawędzie o nieskończonej pojemności. Dlatego każde prawidłowe cięcie będzie musiało zawierać wszystkie A, B, C, D, E, F po tej samej stronie.

Próbując prześledzić, skąd pochodzi rozwiązanie: http://www.cs.washington.edu/education/courses/cse521/01sp/flownotes.pdf cytuje Network Flows autorstwa Ahuji, Magnanti i Orlina w przypadku niektórych problemów. Ta książka nie jest objęta prawami autorskimi i można ją pobrać ze strony http://archive.org/details/networkflows00ahuj, ale wydaje się, że nie zawiera tego problemu i rozwiązania (szukanie każdego wystąpienia „dwustronnego”).

Zauważ, że paragraf wyjaśnienia rozwiązania nie pokazuje, że najmniejsze cięcie wykresu, który tworzy, odpowiada maksymalnemu niezależnemu zestawowi. To tylko pokazuje sposób, aby dostać się niezależny zestaw.

A jednak możesz zobaczyć, co algorytm próbuje zrobić. Oto, co odpowiada rzeczywistemu maksymalnemu niezależnemu zestawowi pod względem jego s, t cięcia:

Podkreślono krawędź nieskończonej pojemności, która łamie algorytm.

Nie jestem pewien, jak naprawić algorytm zgodnie z przeznaczeniem. Może koszt nieskończonej krawędzi powinien wynosić zero, jeśli idzie wstecz (tzn. Gdzie przechodzi od S do T, ale przecina stronę T do strony S)? Ale czy przy tej nieliniowości nadal łatwo jest znaleźć minimalny / maksymalny przepływ? Myśląc o sposobie pomostu z rozwiązania @Jukka Suomela do algorytmu z pytania, trudno jest przejść od maksymalnego dopasowania do minimalnej osłony wierzchołków: znalezienie maksymalnego dopasowania może być wykonane przez przepływ maksymalny podobny do algorytmu, w jaki sposób odzyskujesz z niego minimalną osłonę wierzchołków za pomocą algorytmu podobnego do przepływu? Jak opisano tutaj, po znalezieniu maksymalnego dopasowania krawędzie między U i V zostają skierowane w celu znalezienia minimalnej osłony wierzchołków. Ponownie, to nie pokazuje, że wystarczy proste zastosowanie minimalnego / maksymalnego przepływu, aby rozwiązać ten problem.

$S$$T$$S$

Cięcie powinno odbywać się na rzeczywistym przepływie, a nie na wydajnościach. Ponieważ przepływ z s jest skończony, każde cięcie {S, T} będzie skończone. Reszta jest wyjaśniona powyżej.

$U$$V$

$G'$$\{A,C,D,F\}$