Znalezienie minimalnego cięcia niekierowanego wykresu

25

Oto pytanie z poprzedniego egzaminu, który próbuję rozwiązać:

Dla niekierowanego wykresu z dodatnimi wagami w ( e ) ≥ 0 staram się znaleźć minimalne cięcie. Nie znam innych sposobów na zrobienie tego poza wykorzystaniem twierdzenia o maksymalnym przepływie min-cut. Ale wykres nie jest przekierowany, więc jak mam go pokierować? Myślałem o kierowaniu krawędzi na obu końcach, ale który wierzchołek byłby źródłem, a który wierzchołek byłby zlewem? Czy istnieje inny sposób na znalezienie minimalnego cięcia?solw(mi)≥0

algorithms graph-theory Józef
źródło
1
Jeśli nie masz źródła i celu na oryginalnym wykresie, myślę, że będziesz musiał spróbować wielu opcji. (Dla dowolnych danych i t minimalne cięcie nie może ich rozdzielić.)st
Raphael
Czy próbujesz znaleźć min-cut dla danego źródła i węzłów sink lub min-cut na wykresie?
Peter
@Peter: Min. Cięcie wykresu.
Józef

Odpowiedzi:

13

Istnieje wiele algorytmów służących do znalezienia minimalnego wycięcia niekierowanego wykresu. Algorytm Kargera to prosty, ale skuteczny algorytm randomizowany.

Krótko mówiąc, algorytm działa poprzez wybieranie losowo równomiernie krawędzi i kurczenie ich przy usuniętych pętlach własnych. Proces zatrzymuje się, gdy pozostały dwa węzły, a dwa węzły reprezentują cięcie. Aby zwiększyć prawdopodobieństwo sukcesu, algorytm randomizowany jest uruchamiany kilka razy. Podczas wykonywania biegów śledzi się najmniejsze znalezione dotąd cięcie.

Zobacz wpis Wikipedii, aby uzyskać więcej informacji. Być może dla lepszego wprowadzenia zapoznaj się z pierwszym rozdziałem Prawdopodobieństwo i obliczenia: algorytmy randomizowane i analiza probabilistyczna autorstwa Michaela Mitzenmachera i Eli Upfala.

Juho
źródło
Czy to algorytm aproksymacyjny?
Strin,
@Strin Jest to randomizowany algorytm, który znajduje minimalne cięcie z dużym prawdopodobieństwem.
Juho,
1
Nie sądzę, aby Karger był odpowiedni do znalezienia cięcia o minimalnej wadze. Wyznaczenie prawdopodobieństwa znalezienia cięcia minimalnego zależy od znalezienia cięcia minimalnej liczności; Jest mało prawdopodobne, aby Karger znalazł minimalne cięcie z wieloma lekkimi krawędziami.
Sumudu Fernando
8

(u,v,wmijasolht)(u,v,wmijasolht)(v,u,wmijasolht)

... ale który wierzchołek byłby źródłem, a który wierzchołek byłby zlewem?

Nie ma znaczenia

Pratik Deoghare
źródło
1
Dlaczego to nie ma znaczenia?
The Coding Wombat
1

Algorytm Forda-Fulkersona powinien działać dla Ciebie. Możesz utworzyć dwa fałszywe wierzchołki. źródło i zlew.

Zobacz także algorytm Edmondsa-Karpa . Istnieją dwie odmiany:

  1. Jedna wersja wybiera najkrótszą ścieżkę
  2. Inni wybierają ścieżkę o maksymalnej pojemności

, w przeciwieństwie do Forda Fulkersona, który obiera dowolną ścieżkę.

To dobry zasób.

ajmartin
źródło
Witamy w cs.stackexchange! Może to pomóc OP, jeśli możesz dalej wyjaśnić, w jaki sposób fałszywe wierzchołki są połączone z istniejącym wykresem. A jakie będą ciężary nowych krawędzi.
Paresh