[DSAL] MinCut finden ohne Fulkerson

[Progra] Programmierung
[DSAL] Datenstrukturen und Algorithmen
[SWT] Softwaretechnik
[DB] Datenbanken und Informationssysteme

MinCut finden ohne Fulkerson

Beitragvon Someguy » 03.08.13 01:29

Hallo,

in der Vorlesung über Schnitte in Flussnetzwerken, die mit Thomas Ströder als Verteter gehalten wurde, wurde erwähnt, dass man den maximalen Fluss auch ohne Ford Fulkerson berechnen kann. Dies würde so gehen, dass man bei gegebenem (am besten einfachen) Flussnetzwerk einfach Schnitte ausprobiert oder so ähnlich. Leider kann ich mich nicht mehr an die genauen Details erinnern aber es soll wohl gehen. Dies würde auch besonders praktisch bei schriftlichen Aufgaben sein, da man sich das Aufzeichnen der ganzen Netzwerke spart, falls nur nach dem maximalen Fluss gefragt ist.

Nun habe ich das aber mal versucht anhand einer Tutoraufgabe das mal zu testen.
Bild

Und entweder ich berechne oder setze die Schnitte falsch aber ich komme da einfach nicht auf den maixmalen Fluss, den ich mit Ford Fulkerson raushabe, welcher 11 ist.
Wenn ich bspw. als die S Menge {s,A,B} nehme und der Rest die T Menge bildet, dann rechne ich doch 3-6-5+9+11-9=3 oder nicht?
Someguy
 
Beiträge: 55
Registriert: 14.10.10 20:47
Studiengang: Informatik (B.Sc.)
Studiert seit: WS 10/11
Anwendungsfach: Philo

Re: MinCut finden ohne Fulkerson

Beitragvon SubZer0 » 03.08.13 06:53

Für die Kapazität eines Schnittes (S,T) sind nur die Kapazitäten der Kanten von S nach T relevant, siehe http://de.wikipedia.org/wiki/Max-Flow-Min-Cut-Theorem

In deinem Netzwerk wäre somit ({s,A,B,C,E},{D,t}) ein Schnitt mit Kapazität 11.
SubZer0
 
Beiträge: 34
Registriert: 12.12.10 19:58
Studiengang: Informatik (B.Sc.)
Studiert seit: WS 10/11

Re: MinCut finden ohne Fulkerson

Beitragvon Someguy » 03.08.13 10:36

Ah, bezieht man sich hier also auf die dritte Aussage "Für mindestens einen Schnitt (S,T) ist der Wert des Flusses gleich der Kapazität des Schnittes: |f| = c(S,T)" ? Weil ich dachte ja, ich muss den Fluss von S nach T ausrechnen und nicht die Kapazität.

Gut, aber dann wäre die nächste frage, wie ich beim "rumschneiden" rausfinde, ob ich nun bereits das Minimum gefunden habe oder nicht.
Someguy
 
Beiträge: 55
Registriert: 14.10.10 20:47
Studiengang: Informatik (B.Sc.)
Studiert seit: WS 10/11
Anwendungsfach: Philo

Re: MinCut finden ohne Fulkerson

Beitragvon SubZer0 » 03.08.13 11:30

Wenn du einen beliebigen Schnitt nimmst, stellt dessen Kapazität eine obere Schranke für die Werte aller Flüsse im Netzwerk dar.
Außerdem stellt ein beliebiger Fluss eine untere Schranke für die Kapazitäten aller Schnitte im Netzwerk dar.

D.h. wenn du einen Fluss dessen Wert gleich der Kapazität des Schnittes den du gefunden hast, angegeben kannst, handelt es sich dabei um einen minimalen Schnitt sowie einen maximalen Fluss.
SubZer0
 
Beiträge: 34
Registriert: 12.12.10 19:58
Studiengang: Informatik (B.Sc.)
Studiert seit: WS 10/11

Re: MinCut finden ohne Fulkerson

Beitragvon Someguy » 03.08.13 11:41

Warum stellt ein _beliebiger_ Fluss die untere Schranke für die Kapazitäten ALLLER Schnitte im Netzwerk dar? Ich könnte doch bspw. einen Fluss mit 1 finden und einen mit 5, dann wäre doch der mit 1 eher eine untere Schranke.

Und setzt du in deinem letzten Post nicht auch voraus, dass ich erstmal Flüsse finden muss? Weil ich meine eine Methode die gänzlich ohne Flüsse finden auskommt.
Someguy
 
Beiträge: 55
Registriert: 14.10.10 20:47
Studiengang: Informatik (B.Sc.)
Studiert seit: WS 10/11
Anwendungsfach: Philo

Re: MinCut finden ohne Fulkerson

Beitragvon SubZer0 » 03.08.13 17:40

Someguy hat geschrieben:Warum stellt ein _beliebiger_ Fluss die untere Schranke für die Kapazitäten ALLLER Schnitte im Netzwerk dar? Ich könnte doch bspw. einen Fluss mit 1 finden und einen mit 5, dann wäre doch der mit 1 eher eine untere Schranke.


Weil nach dem Theorem der maximale Fluss gerade mal (genau) so groß ist wie der minimale Schnitt. Heisst alle Flüsse die kleiner sind, sind kleiner als der minimale Schnitt und damit auch kleiner als jeder beliebige Schnitt. In deinem Beispiel ist 1 ja auch eine untere Schranke, nur 5 ist eine bessere :wink:


Mit der Methode kannst Du nur beweisen, dass ein von dir angegebener Fluss maximal ist (durch Angabe eines Schnittes mit selber Kapazität). Sollte in der Klausur aber schneller gehen als Ford-Fulkerson durchzuexerzieren, da man maximale Flüsse und minimale Schnitte meistens schnell durch scharfes Hinsehen finden kann.
SubZer0
 
Beiträge: 34
Registriert: 12.12.10 19:58
Studiengang: Informatik (B.Sc.)
Studiert seit: WS 10/11

Re: MinCut finden ohne Fulkerson

Beitragvon jypdtonga » 05.08.13 00:27

Hm, du hasst da eh ein residualnetzwerk und nicht unsere typische fluß darstellung als graph..

Es sollte doch für Max-flow min-cut eigentlich reichen einfach den Graph nur bestehend aus den Kapazitäten hinzumalen (bzw. sich möglicherweise vermerkte Fluß werte wegzudenken).

Dann in dem einfach "linien" durch den graph ziehen und gucken was "in die linien rein" an kapazitäten reinfließt. (wobei die "linien" hier nicht gerade seien müßen :D )

Das kleinste was man so finden kann ist der maximale fluß.

Außerdem gibt jeder so gefunden Wert auch eine obere Schranke für den maximalen Fluß.

Hab mal ein Beispiel zusammengewurschtelt:

Bild

Hier habe ich aber nicht alle möglichen Cuts gemacht wodurch ich also nicht bewiesen habe das der max flow = 3 ist sondern nur das max-flow <= 3
jypdtonga
 
Beiträge: 4
Registriert: 10.02.13 02:24
Studiengang: Informatik (B.Sc.)
Studiert seit: WS 10/11
Anwendungsfach: BWL


Zurück zu Praktische Informatik