[informatik-bonn] Blatt14

  • From: Sebastian Bothe <sbothe@xxxxxx>
  • To: info <informatik-bonn@xxxxxxxxxxxxx>
  • Date: Sun, 2 Feb 2003 17:35:38 +0100

Hallo zusammen,

  verzweifele langsam über der Aufgabe2.. Glaub zwar das ich (endlich) so 
halbwegs verstehe, wie der Ford Fulkerson funktionieren soll, aber wie kriege 
ich es hin zu zeigen, daß der auf dem Graph nicht terminiert?
  Man müßte hierfür doch irgendwie zeigen, daß es einen Fortschritt gibt, der 
aber von einem dem nächsten Aufruf aber wieder genau aufgehoben wird, oder? 
Dann würde der Algo da in einem Deadlock landen..
  Ein paar Dinge die mir so aufgefallen sind.. Vielleicht hilft es 
irgendjemanden weiter..
 - Die Zahl 1-\sqrt(5) ist der "goldene Schnitt" wenn ich mich nicht irre
 - der minimale Schnitt scheint genau der zu sein, der entweder s und alle 
anderen Knoten trennt oder jener, der t von allen anderen trennt. Wenn ich 
den Schnitt "schief" lege, also einen der inneren Knoten mit zu s oder t in 
die Menge nehmen bekommen ich auf alle Fälle in der Summe einen größere 
Kapazität der Kanten die zwichen den Mengen des Schnittes liegen

Hat jemand mal versucht den "Orginal Beweis" von Ford/Fulkerson zu finden? Der 
Blum schreibt doch das die beiden selbst mit einem Beispiel (wahrscheinlich 
genau das hier) gezeigt haben das der Algo für irrationale Zahlen nicht 
terminiert?

Gruß
        Sebastian
 

Other related posts: