Ich verstehe den Fehler nicht. bzw Warum ist der Graph falsch?
Ich hab dem Lehrer eine Email geschrieben und er meinte: "Der Graph des Netzwerkes fehlt. Wie sieht es aus mit allen Kanten und deren Werte? Sie haben die Lösung als Graph abgebildet. Welches schön ist, aber der Grundgraph fehlte."
Ist es nicht der Grundgraph?
1 Antwort
Nein, das ist nicht der Grundgraph, sondern des minimale Spannbaum.
Ersichtlich daran, dass allein in der ersten Spalte bereits 4 Werte eingetragen sind, folglich A als einziger Knoten in der Ausgangsmenge entsprechend Kanten zu 4 anderen Knoten hat.
Die Kanten zu den weiteren Knoten kannst du auch jeweils aus der Tabelle herauslesen.(Allerdings nicht zwingend alle)
Alle Zeilen, in denen sich der Wert im Vergleich zur vorherigen Spalte verändert, haben eine Kante zum neu hinzugefügten Knoten. Der Wert dieser Kante ergibt sich aus der Differenz des Weges des Ursprungsknoten zum neuen Knoten und dem Wert in der Tabelle.
Was du allerdings nicht erhälst sind Kanten, bei denen der Pfad über den neuen Knoten genauso lang/länger als der der vorherige Pfad ist.
Am Beispiel ergäben sich für die ersten beiden Spalten folgende Kanten:
1.) (A, B 24), (A, C, 64), (A, D, 47), (A, F, 28)
2.) (B, C, 17)
...