minimal aufspannender Baum in Graph

Neue Frage »

Leonl Auf diesen Beitrag antworten »
minimal aufspannender Baum in Graph
Meine Frage:
Sei G ein ungerichteter, gewichteter, zusammenhängender Graph ohne Mehrfachkanten und ohne Schlingen. G habe endlich viele Knoten. Die gewichte der Kanten seien alle paarweise verschieden.
Zu zeigen: Es gibt genau einen minimal aufspannenden Baum G' von G.

Meine Ideen:
Wenn G kreisfrei ist, dann ist die Aussage klar, denn es kann eh kein weiterer Knoten entfernt werden (in kreisfreien Graphen gibt es ja immer nur eine Möglichkeit, von einem Knoten zum nächsten zu kommen, und die fällt ja nun für die beiden Knoten weg, die die Kante verbunden haben, die man herausnimmt).
Hat G genau einen Kreis, dann ist die Sache auch klar: Egal welche Kante aus G man entfernt, es bleibt ein aufspannender Baum übrig (das hab ich bereits eingesehen und ich kann es auch ausformulieren). Minimal wird der aufspannende Baum also dann, wenn man einfach die Kante aus dem Kreis entfernt, die maximales Gewicht hat. Da die gewichte paarweise verschieden sind, ist das eine eindeutige Operation.

Ich bin aber ratlos, was Graphen angeht, die Kreise haben, die sich in einer oder mehreren Kanten überschneiden. Hier ist das Problem (das sich wohl auflösen soll), dass es ja sein könnte, dass das entfernen zweier Kanten mit 1 und 4 bzw. zweier Kanten mit Gewicht 2 und 3 jeweils die gleiche Summe ergibt. Ich schaff es auch nicht, diesen Fall auf die anderen Fälle zurückzuführen.
Abakus Auf diesen Beitrag antworten »
RE: minimal aufspannender Baum in Graph
Hallo,

hast du schon an eine Vollständige Induktion gedacht?

Abakus smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »