[informatik-bonn] AW: Blatt14

  • From: "Andreas Wedel" <andreas@xxxxxxxxxxxxxxxxxxxx>
  • To: <informatik-bonn@xxxxxxxxxxxxx>
  • Date: Mon, 3 Feb 2003 22:23:07 +0100

Du schreibst:

- 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

Nein, wichtig ist, dass alle von den von S ausgehenden Kanten und von
den nach t gehenden Kanten niemals an die volle Kapazität gelangen und
nur die "modifizierten" Kanten den Fluss "drücken" können. Damit muss
man was konstruieren können, versuche es gerade mal..... (1/(1-sigma))
ist die größte Vorkommende Zahl im Netzwerk, alle anderen Kapazitäten
sind <1, das ist die wichtigste Aussage, womit dann auch z.b. (sigma)^n
kleiner als 1 ist!



Other related posts:

  • » [informatik-bonn] AW: Blatt14