Algorithmische Graphentheorie, 4th Edition

8.9 Aufgaben

1.  Es sei G ein gerichteter kantenbewerteter Graph und q, s Ecken von G. Ferner sei H die Menge der Kanten von G mit Anfangsecke s oder Endecke q. Entfernen Sie aus G die Kanten, welche in H liegen, und bezeichnen Sie diesen Graphen mit G. Beweisen Sie, dass die Werte von maximalen q-s-Flüssen auf G und G übereinstimmen.

*2. Es sei λ > 0 die reelle Zahl, für die λ² + λ − 1 = 0 gilt. Betrachten Sie das folgende Netzwerk G. Alle unmarkierten Kanten haben die Kapazität λ + 2. Zeigen Sie, dass es einen Fluss mit Wert 2 gibt und dass dieser ...