TU Wien Diskussion:Algebra und Diskrete Mathematik UE (diverse)/Übungen WS18/Beispiel 320

Aus VoWi
Wechseln zu: Navigation, Suche

Diskussion zu einer älteren Version[Bearbeiten]

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



Entfernungsbaum schrittweise erstellen[Bearbeiten]

Erster Schritt[Bearbeiten]

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


Bsp212 2.png


Zweiter Schritt[Bearbeiten]

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


Bsp212 3.png


Dritter Schritt[Bearbeiten]

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


Bsp212 4.png


Vierter Schritt[Bearbeiten]

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


Bsp212 5.png




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)