Kapitel 10Olympiade27 Min.
Spannbäume durch Reduktion
Spannbäume, Zyklen und Kantentausch · Abschnitt 37 von 64
Gelöstes Beispiel
Zykluskante ist redundant
Der Restzyklus erhält die Verbindung.
Gelöstes Beispiel
Eine Kante hinein, eine hinaus
Eine neue Baumkante erzeugt genau einen Austauschzyklus.
Gelöstes Beispiel
Leichteste Schnittkante
Eine schwerere Baumkante über denselben Schnitt kann ausgetauscht werden.