Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Beweisaufgabe; Thema: minimaler Spannbaum

Beweisaufgabe; Thema: minimaler Spannbaum

Universität / Fachhochschule

Tags: Beweis, minimaler Spannbaum

8mileproof aktiv_icon

13:52 Uhr, 24.06.2012

hallo,

ich muss folgendes beweisen:

jeder ungerichtete, gewichtete und zusammenhängender Graph, bei dem keine 2 Kanten gleich gewichtet sind, hat einen eindeutigen minimalen spannbaum.

wie kann ich das zeigen?

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Zu diesem Thema passende Musteraufgaben einblenden

hagman aktiv_icon

14:51 Uhr, 24.06.2012

Dass es überhaupt mindestens einen Spannbaum gibt, ist bekannt?

Betrachte zwei Spannbäume

T_{1} \neq T_{2}

mit

w (T_{1}) = w (T_{2}) = min

Wegen

T_{1} \neq T_{2}

gibt es Kanten, die in genau einem der beiden Bäume auftreten.
Sei

a b

unter diesen Kanten die (eindeutige) mit geringstem Gewicht.
OBdA. taucht

a b

bei

T_{1}

auf, nicht jedoch bei

T_{2}

T_{2} + a b

enthält dann einen Kreis.
Dieser Kreis gehört gewiss nicht gänzlich zu

T_{1}, d . h

. es gibt eine Kante

c d

in diesem Kreis, die nicht zu

T_{1}

gehört.
Nach Wahl von

a b

gilt

w (c d) > w (a b)

.
Aber nach Streichen von

c d

erhält man einen Baum

T_{3}

mit

w (T_{3}) = w (T_{2}) + w (a b) - w (c d) < w (T_{2})

. Widerspruch!

8mileproof aktiv_icon

15:24 Uhr, 24.06.2012

ja, das ist mir bekannt. nun muss ich doch die eindeutigkeit beweisen.

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1013938

1013903

	Status: nicht eingeloggt	Noch nicht registriert?