Ermitteln des Mindestschnitts eines ungerichteten Diagramms

25

Hier ist eine Frage aus einer früheren Prüfung, die ich zu lösen versuche:

Für einen ungerichteten Graphen mit positiven Gewichten versuche ich, den Minimalschnitt zu finden. Ich kenne keine anderen Möglichkeiten, um das zu tun, als den Max-Flow-Min-Cut-Satz. Das Diagramm ist jedoch ungerichtet. Wie soll ich es steuern? Ich dachte daran, Kanten an beiden Enden auszurichten, aber welcher Scheitelpunkt wäre dann die Quelle und welcher Scheitelpunkt die Senke? Oder gibt es einen anderen Weg, um den Mindestschnitt zu finden?w ( e ) ≥ 0Gw(e)≥0

algorithms graph-theory Jozef
quelle
1
Wenn Sie in der Originalgrafik keine Quelle und kein Ziel haben, müssen Sie vermutlich mehrere Möglichkeiten ausprobieren. (Für jedes gegebene und t kann der minimale Schnitt die beiden nicht trennen.)st
Raphael
Versuchen Sie, den Min-Cut für bestimmte Quellen- und Senken-Knoten oder den Min-Cut des Graphen zu finden?
Peter
@ Peter: Der minimale Schnitt des Graphen.
Jozef,

Antworten:

13

Es gibt viele Algorithmen, um den minimalen Schnitt eines ungerichteten Graphen zu finden. Kargers Algorithmus ist ein einfacher, aber effektiver Zufallsalgorithmus.

Kurz gesagt, der Algorithmus wählt Kanten gleichmäßig nach dem Zufallsprinzip aus und zieht sie mit entfernten Self-Loops zusammen. Der Prozess wird angehalten, wenn zwei Knoten übrig sind und die beiden Knoten einen Schnitt darstellen. Um die Erfolgswahrscheinlichkeit zu erhöhen, wird der randomisierte Algorithmus mehrmals ausgeführt. Während der Läufe verfolgt man den kleinsten bisher gefundenen Schnitt.

Weitere Informationen finden Sie im Wikipedia-Eintrag. Für eine vielleicht bessere Einführung lesen Sie das erste Kapitel von Wahrscheinlichkeitsrechnung und Computing: Randomisierte Algorithmen und probabilistische Analyse von Michael Mitzenmacher und Eli Upfal.

Juho
quelle
Ist das ein Näherungsalgorithmus?
Strin
@Strin Es ist ein zufälliger Algorithmus, der mit hoher Wahrscheinlichkeit den minimalen Schnitt findet.
Juho
1
Ich halte Karger's nicht für angebracht, um ein Minimum an Gewicht zu erreichen. Die Ableitung der Wahrscheinlichkeit, dass es einen Minimalschnitt findet, hängt davon ab, dass es einen Minimalkardinalitätsschnitt findet; Es ist sehr unwahrscheinlich, dass Karger's einen minimalen Schnitt mit vielen leichten Kanten findet.
Sumudu Fernando
8

Für jede ungerichtete Kante (u,v,weight)(u,v,weight)(v,u,weight)

... aber welcher Scheitelpunkt wäre dann die Quelle und welcher Scheitelpunkt wäre die Senke?

Spielt keine rolle

Pratik Deoghare
quelle
1
Warum ist das nicht wichtig?
The Coding Wombat
1

Der Ford-Fulkerson- Algorithmus sollte für Sie funktionieren. Sie können zwei falsche Scheitelpunkte erstellen. die Quelle und Senke.

Schauen Sie sich auch den Edmonds-Karp-Algorithmus an . Es gibt zwei Variationen davon:

  1. Eine Version wählt den kürzesten Weg
  2. Andere wählen einen Pfad mit der maximalen Kapazität

Im Gegensatz zu Ford-Fulkerson, der einen willkürlichen Weg einschlägt.

Dies ist eine gute Ressource.

Ajmartin
quelle
Willkommen bei cs.stackexchange! Es könnte dem OP helfen, wenn Sie näher erläutern könnten, wie die gefälschten Eckpunkte mit dem vorhandenen Graphen verbunden sind. Und was werden die Kantengewichte der neuen Kanten sein.
Paresh