Graphentheorie: Definitionen von Bäumen

Neue Frage »

MaPalui Auf diesen Beitrag antworten »
Graphentheorie: Definitionen von Bäumen
Hallo ihr Lieben,

ich brauche eure Hilfe bei Bäumen. Ich habe die Definition eines Baumes
Zitat:
ist ein Baum G ist zusammenhängend und hat keine Kreise
.

Nun soll ich zeigen, dass folgende Definitionen äquivalent sind:

A) Zwischen zwei Ecken in G gibt es genau einen Pfad
B) Jede Kante in G ist eine Brücke
C) G ist zusammenhängend und |V| - 1 Kanten
D) G hat keine Kreise und |V| - 1 Kanten
E) Wenn wir eine beliebige Kante an G hinzufügen, gibt es genau einen Kreis.

Womit ich nun wirklich Probleme habe ist die Reihenfolge.
Darf ich den Beweis folgendermaßen führen:
G ist Baum => A => B => C => D => E => G ist Baum ?
Ich bin mir gerade wirklich nicht sicher verwirrt

Jedenfalls habe ich nun zumindest mal folgendes:
G ist Baum <=> (A)

"=>"
G ist Baum => G ist zusammenhängend => Es gibt mindestens einen Pfad von u nach v.
Angenommen es gibt zwei Pfade . Dann ist deren Vereinigung ein Kreis.

"<="
Kontraposition:
Ist G nicht zusammenhängend gibt es zwei Knoten u und v, für die es keinen Pfad gibt.
ist G nicht kreisfrei gibt es zu je zwei Punkten u und v auf diesem Kreis zwei Pfade von u nach v.
Neue Frage »
Antworten »



Verwandte Themen

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