Maksymalny niezależny zestaw wykresu dwudzielnego

19

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)UVUUVVE

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 .UV{s,t}(u,v)EuvuUsuvVvt

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)sStTU=USV=VTUV|UU|+|VV|=|U|+|V||UV|

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:

stABCDEFs00101010t00010101A1000000B01000C1000000D0100000E10000F0100000

Tutaj utknąłem, najmniejsze ograniczone ograniczenie pojemności, jakie widzę, jest banalne: o pojemności 3.(S.,T.)=({s},{t,ZA,b,do,re,mi,fa})

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

U=US.={}
V.=V.T.={b,re,fa}
UV.={b,re,fa}

Podczas gdy spodziewaliśmy się ? Czy ktoś może dostrzec, gdzie popełniłem błąd w moim rozumowaniu / pracy?UV.={ZA,do,re,fa}

Andrew Tomazos
źródło
(S, T) = ({s, A, B, C}, {t, D, E, F}) ma pojemność 2
1
@ Brian istnieje nieskończona granica pojemności od B do E w poprzek cięcia, więc jest to nieskończona pojemność.
Andrew Tomazos,
jeśli dobrze to rozumiem, w oparciu o rozwiązanie brutalnej siły, potrzebujesz cięcia, w którym S zawiera A i C, a T zawiera D i F, co sprawia, że ​​twoje cięcie to {s, A, C}, {t, D, F} . Jak zbudujesz cięcie?
njzk2
wygląda to również jak Ford-Fulkerson, w którym krawędzie mają pojemność jednego.
njzk2
Wyszukaj algorytm węgierski.
Patrik Vörös,

Odpowiedzi:

14

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 .

Jukka Suomela
źródło
2
To (może) rozwiązuje problem, ale nie odpowiada na pytanie.
Raphael
2
@Raphael: Zgadzam się, jeśli usuniesz słowo „może”. :)
Jukka Suomela
1
Och, jestem pewien, że to rozwiązuje ten problem, ale nie jestem pewien, czy to pomaga Andrew rozwiązać jego problem.
Raphael
3
Rozwiązałem go tak, jak sugerujesz: HopcroftKarp -> maksymalne dopasowanie -> Konigs Thereom -> Minimalna pokrywa wierzchołków -> Uzupełnienie -> Maksymalny niezależny zestaw. Nadal chciałbym wiedzieć, dlaczego metoda przepływu opisana w moim pytaniu wydaje się nie działać.
Andrew Tomazos,
5

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:

Wykres

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.

Jewgienij Siergiejew
źródło
2

S.T.S.

yu25x
źródło
1
Zgadzam się z tobą, ale czy mógłbyś dodać więcej szczegółów, na przykład pełny dowód poprawności algorytmu przepływu i jak ten algorytm stosuje się na przykładzie PO?
xskxzr
Uwaga w tym zawiera krótki dowód poprawności. cs.washington.edu/education/courses/cse521/01sp/flownotes.pdf Na przykład, jeśli spojrzysz na postać Evgenija Sergeeva powyżej, wszystkie krawędzie powinny być skierowane w dół. Wtedy jedyne dwie krawędzie poza S to (s, e) i (b, t), pogrubiona czerwona krawędź przechodzi w S i nie powinna być liczona w wartości cięcia.
yu25x
0

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.

Talmon
źródło
1
Jesteś pewny? Cięcia zwykle dotyczą pojemności i w każdym razie wiemy już, że minimalne cięcie jest skończone, więc cięcia nieskończone nie wydają się stanowić problemu.
David Richerby
0

UV.

sol{ZA,do,re,fa}

Ajit Kumar
źródło