Graphentheorie: Definitionen von Bäumen |
20.02.2021, 20:15 | MaPalui | Auf diesen Beitrag antworten » | ||
Graphentheorie: Definitionen von Bäumen ich brauche eure Hilfe bei Bäumen. Ich habe die Definition eines Baumes
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 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. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|