Mit Hilfe dieses Satzes können wir nun eine zum Satz von Menger analoge Aussage für Kanten beweisen.

Satz. Es seien a, b Ecken eines ungerichteten Graphen. Dann gilt

W k(a, b) = Zk(a, b).

Beweis. Liegen a und b in verschiedenen Zusammenhangskomponenten von G, so ist die Aussage trivialerweise erfüllt. Somit kann man annehmen, dass G zusammenhängend ist. Nach dem Satz von Ford-Fulkerson und dem obigen Lemma gibt es einen a-b-Schnitt images. Da alle Kanten die Kapazität 1 haben, ist images ist eine trennende Kantenmenge für a, b. Somit gilt . Es sei nun S eine ...

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.