TU Wien Diskussion:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 325

Diskussion zu einer älteren Version

Die folgende Diskussion bezieht sich auf folgende, nun aus dem Artikel entfernte Stelle:

---

Entfernungsbaum schrittweise erstellen

Erster Schritt

Im ersten Schritt nehmen wir vom vorgegebenen Startpunkt den kürzesten Weg und zeichnen die erste Strecke des Entfernungsbaumes.

Zweiter Schritt

Wiederum wählen wir als Fortsetzung die Kante mit dem geringsten Gewicht und ergänzen den Entfernungsbaum.

Dritter Schritt

Der nächste Weg ist klar (andernfalls würde sich ein Kreis schliessen).

Vierter Schritt

Nun sucht man die kürzesten Wege zu den zwei verbleibenden Punkten ... Voila!

---

Die kürzeste Verbindung von $v_{0}$ zu $v_{3}$ führt doch über $v_{1}$: $l(v_{0},v_{1})+l(v_{1},v_{3})=1+7=8$. Der Weg in dem angegebenen Entfernungsbaum ist $l(v_{0},v_{1})+l(v_{1},v_{5})+l(v_{5},v_{4})+l(v_{4},v_{3})=1+1+2+5=9$. -- Jens 00:00, 13. Dez 2005 (CET)

http://michael.riedeselstrasse.de/la/files/graphentheorie3.pdf

http://www.math2.rwth-aachen.de/~uebung/GT/vorl_gt.pdf S.25ff.

Es scheint mehrere kürzeste Wege zu geben. Der Entfernungsbaum ist nicht eindeutig. --Mnemetz 05:47, 13. Dez 2005 (CET)

Ich habe nun die tabellarische Lösung ins Wiki eingetragen. --Mnemetz 12:37, 13. Dez 2005 (CET)