Aussagen in Graphentheorie zu beweisen

Question

Hallo, kann jemand bitte mir bei dieser Aufgabe helfen? Es geht um Graphentheorie, ein ganz neues Thema für mich…:/

Zeigen Sie, dass die folgenden Aussagen äquivalent sind:

(a) G=(V,E) ist ein Baum(G ist ein Graph, V bezeichnet die Knoten und E die Kanten.)
(b) G ist maximal kreisfrei, d.h. G ist kreisfrei und für jedes e ∈ {{v1, v2}|v1, v2 ∈ V } \ E hat der Graph (V, E ∪ {e}) einen Kreis.
(c) G ist minimal zusammenhängend, d.h. G ist zusammenhängend und für jede Kante e ∈ E ist (V, E \ {e}) nicht zusammenhängend.

Ich wäre sehr dankbar

Answer 1

Hallo,

man kann einen Ringschluss versuchen. Ich mache Dir mal den Schluss von a) nach b) vor:

Also: Voraussetzung: G ist ein Baum, d.h. kreisfrei und zusammenhängend (habt Ihr doch nicht anders definiert?). Zu zeigen ist die angegebene Maximalitätseigenschaft: Jedes weitere Kante erzeugt einen Kreis.

Sei also \(e:=\{v,w\} \notin E\). Weil G zusammenhängend ist, existiert ein Weg \((v,x_1, \ldots x_n,w)\) in G, der also v und w verbindet. Dann ist \((v,x_1, \ldots x_n,w,v)\) ein Kreis in \((V,E \cup \{e\})\)

Gruß Mathhilf

Comments

Ich danke dir!!

---

Leider, die war die einzige Definition://

---

Kein Grund für "Leider". Das ist ja die übliche Definition von Baum, ich wollte nur sicher gehen, dass Ihr nicht irgendetwas exotisches gemacht habt.