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 Gimage. Beweisen Sie, dass die Werte von maximalen q-s-Flüssen auf G und Gimage übereinstimmen.

*2. Es sei λ > 0 die reelle Zahl, für die λ2 + λ − 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 ...

Get Algorithmische Graphentheorie, 4th Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.