Ford-Fulkerson und Min-Cut < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:42 Mi 02.04.2008 | | Autor: | Aeolus |
| Aufgabe | | Im Zusammenhang mit minimalen Schnitten in Graphen ist häufig vom Ford-Fulkerson die Rede. Mit diesem lässt sich der maximale Fluss bestimmen, dessen Wert dem des minimalen Schnittes entspricht. In einfachen Beispielen zum FF wird am Ende häufig der Min-Cut am Graph dargestellt. |
Was mir nicht so ganz klar ist: Woher weiß man, wie man die Knotenmenge für den Min-Cut aufteilen muss? Ergibt sich das aus dem FF oder muss man das mit einem anderen Algorithmus berechnen?
Vielen Dank schonmal!
Aeolus
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:12 Do 03.04.2008 | | Autor: | bazzzty |
> Im Zusammenhang mit minimalen Schnitten in Graphen ist
> häufig vom Ford-Fulkerson die Rede. Mit diesem lässt sich
> der maximale Fluss bestimmen, dessen Wert dem des minimalen
> Schnittes entspricht. In einfachen Beispielen zum FF wird
> am Ende häufig der Min-Cut am Graph dargestellt.
> Was mir nicht so ganz klar ist: Woher weiß man, wie man
> die Knotenmenge für den Min-Cut aufteilen muss? Ergibt sich
> das aus dem FF oder muss man das mit einem anderen
> Algorithmus berechnen?
Die kurze Antwort: Wenn man einen maximalen Fluß hat, dann kann man den minimalen Schnitt "ablesen". Das hat zu tun mit dem sogenannten "Max-Flow-Min-Cut-Theorem". Bevor ich dazu weiter aushole:
1) Mir ist nicht klar, was die Aufgabe ist. Im Aufgabentext steht nur eine Aussage. Sollt ihr zeigen oder beschreiben, wie man einen minimalen Schnitt findet?
2) Kennt ihr das Max-Flow-Min-Cut-Theorem schon?
Danach gebe ich gerne weiter Tipps. Mein Hinweis wäre: Wenn Dir Ford-Fulkerson bekannt ist: Wenn Du FF ausführst, dann ist der letzte Schritt, daß Du keinen erhöhenden Weg mehr findest. Wo scheitert diese Suche?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:42 So 06.04.2008 | | Autor: | Aeolus |
Danke fuer die Antwort. Das Min-Cut/Max-Flow Theorem haben wir nicht explizit besprochen. Wir sollen eigentlich nur den FF ausfuehren. In den Pruefungsaufgaben steht aber meistens noch, dass man den Min-Cut mit angeben soll. Da die Graphen in den Aufgaben entsprechend klein sind, ist es kein Problem, das auch mit scharfem Hinsehen zu erkennen, insbesondere wenn man schon den Wert des Max-Flows hat. Aber ich vermute mal, der Min-Cut ergibt sich aus der Knotenmenge, die man am Ende vom Startknoten s aus im Residualgraphen erreichen kann, zumindest hat das in Beispielen so funktioniert  .
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:47 Mo 07.04.2008 | | Autor: | bazzzty |
> Aber ich vermute mal, der Min-Cut ergibt sich aus der
> Knotenmenge, die man am Ende vom Startknoten s aus im
> Residualgraphen erreichen kann, zumindest hat das in
> Beispielen so funktioniert .
Ja, das stimmt auch. Das ist übrigens nur *ein* Min-Cut, und zwar der, der die Knotenmenge auf der s-Seite minimiert, wenn es mehrere gibt.
|
|
|
|
