Wie Durchmesser eines Graphen bestimmen?
Also der Durchmesser eines Graphen ist ja definiert als die Anzahl der Kanten des kürzesten Wegs zwischen den am weitesten entfernten Knoten.
Könnte man da einfach mittels Breitensuche den Spannbaum bestimmen und nimmt dann quasi die Länge des längsten Pfades? Das müsste dann ja die kürzestmögliche Distanz zwischen den zwei am weitesten entfernten Knoten sein, oder? Danke
1 Antwort
"Der" Spannbaum eines Graphen ist im Allgemeinen gar nicht definiert, es kann ja viele Spannbäume geben. Das müsstest du schon mal präzisieren. Und dann wirst du feststellen, dass auch das nicht hilft. Durch die Beschränkung auf einen Spannbaum hast du insgesamt ja weniger mögliche Wege, die kürzeste Verbindung zwischen zwei Knoten kann also nur LÄNGER werden, und das hilft dir ja nicht weiter.
Wenn du dir z. B. https://de.wikipedia.org/wiki/Spannbaum#/media/Datei:Spanning_Trees_qtl1.svg anschaust, dann sind das alles Spannbäume ein und desselben Graphen (nämlich des vollständigen Graphen mit vier Knoten). Wenn du jetzt den Spannbaum oben links und den Spannbaum unten rechts vergleichst, dann siehst du, dass einmal der längste Weg die Länge 2 und einmal die Länge 3 hat, das hilft offenbar nicht weiter, denn der Durchmesser des vollständigen Graphen ist trivialerweise immer 1, da je zwei Knoten immer direkt verbunden sind.
Es reicht schon, wenn du dir das mit dem vollständigen Graphen mit drei Knoten vorstellst: Auch da ist der Durchmesser offenbar 1, aber jeder Spannbaum hat als längsten Weg einen Weg mit der Länge 2.