September 2015
Intermediate to advanced
415 pages
12h 24m
German
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 λ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 ...