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

Aus VoWi
Zur Navigation springen Zur Suche springen

Diskussion zu einer älteren Version[Quelltext bearbeiten]

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



Entfernungsbaum schrittweise erstellen[Quelltext bearbeiten]

Erster Schritt[Quelltext bearbeiten]

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



Zweiter Schritt[Quelltext bearbeiten]

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



Dritter Schritt[Quelltext bearbeiten]

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



Vierter Schritt[Quelltext bearbeiten]

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





Die kürzeste Verbindung von zu führt doch über : . Der Weg in dem angegebenen Entfernungsbaum ist . -- 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)