OR1 Tutorium 13.pdf

Assignments
Uploaded by Ramona Müller 6835 at 2017-10-20
Description:

Lösungen zum dreizehnten Tutorium

 +7
223
2
Download
Hey, könntest du mir kurz erklären, wie man hierauf kommt? Danke
Das sind die allgemeinen NB von einem Max-Flow-Problem (Siehe oben) auf diesen konkreten Graphen angewandt. In jedem Knoten (der nicht die Quelle oder Senke ist), muss die Summe der eingehenden Flüsse gleich der ausgehenden Flüsse sein (Flusserhaltung) (2) definiert den Fluss w als "das, was aus der Quelle herauskommt" und (3) sorgt dafür, dass dieser Fluss am Ende auch wieder bei der Senke ankommt (wobei das auch durch die Flusserhaltungsgleichungen und (2) impliziert wird)
Vielen Dank für die Erklärung
Müsste hier nicht noch -10 hin wegen dem Pfeil von 3 nach2? Oder werden "Rückflüsse"ausgelassen?
Nein, siehe VL Graphentheorie Teil 3 Folie 19. Man nimmt nur die Pfeile, die aus W kommen und nach W- (W mit Überstrich) gehen.