FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Praktische Informatik

AD Spannbäume

AD Spannbäume 2009-01-06 15:50
Anonymer User
Hallo zusammen,

ich versteh bei Spannbäumen nicht so ganz, wie die Gewichte der Kanten zustande kommen, könnte mir das nochmal einer erklären?
Ich weiß das der Grad eines Knoten durch die abgehenden Kanten bestimmt ist…. aber das Gewicht einer Kante wird irgendwie anders bestimmt.

Danke für jede Antwort. Gruß Jojo

RE: AD Spannbäume 2009-01-06 16:42
Anonymer User
das Gewicht einer Kante ist immer Bestandteil der Aufgabe. Die Kantengewichte können auf verschiedene Art und Weise interpretiert werden. Angenommen du hast z. B. einen Straßenplan, dann könnten die Gewichte Die Entfernungen angeben oder die Anzahl der Tankstellen auf der Strecke oder die minimale Breite der Straße oder sowas. Die Gewichte werden also nicht aus den Kanten/Knoten berechnet, sondern werden bei der Aufgabenstellung einfach mit angegeben.

RE: AD Spannbäume 2009-01-06 16:42
Anonymer User
Der Grad eines Knotens hat nichts mit dem Gewicht einer Kante zu tun.
Für das Gewicht zwischen zwei Kanten gibt es in einem Graphen eine Gewichtsfunktion: E -> IN (positive Gewichte) oder E -> IZ(auch negative Gewichte), die jeder Kante einen Wert zuweist. Ein Spannbaum, der sich ja aus einem Graphen entwickeln lässt, verwendet für seine Kanten die selben Gewichte wie der zugehörige Graph.

Der Grad eines Knotens gibt nur die Anzahl der ein- und ausgehenden Kanten an.