Forum:  Graphentheorie
Thema: Beweis bzgl. Baumeigenschaften
Themen-Übersicht
SophiaS
Aktiv
Dabei seit: 04.06.2019
Mitteilungen: 37
Themenstart: 2020-10-20 13:41

Hallo,
ich habe folgende Übungsaufgabe:

Zeige die Äquivalenz der folgenden Aussagen.
(i) G ist ein Baum (zusammenhängend und kreisfrei)
(ii) G ist kreisfrei und wenn man eine Kante hinzufugt enthält G einen Kreis
(iii) G hat einen eindeutigen Pfad zwischen zwei beliebigen Konten $u, v \in V$ mit $u \neq v$
Hinweis: Zeigen Sie z.B. i => ii => iii => i

Leider habe ich etwas Probleme dies zu beweisen, Beweise fallen mir immer ziemlich schwer. Hier einmal mein versuch:

"i => ii"
Sei $G$ ein  Baum, somit zusammenhängend und kreisfrei.
Da $G$ zusammenhängend existiert ein Pfad zwischen je zwei beliebigen Knoten in $G$
Wähle nun zwei beliebige Knoten $u,v \in V$ mit $u \neq v$ und $E \cap \{u,v\} = \emptyset$. Füge die Kante $\{u,v\}$ zu $G$ hinzu, dann existieren nun zwei verschiedene Pfade zwischen $u$ und $v$, somit enthält $G$ nach dem hinzufügen der Kante $\{u,v\}$ einen Kreis.

"ii => iii"

Sei $G$ ein maximal kreisfreier Graph also zusammenhängend.
Da G zusammenhängend ist existiert ein Pfad zwischen je zwei beliebigen Knoten $u,v \in V$. [Ist dies so korrekt? Fühlt sich nicht gut an.]
Angenommen $G$ enthält zwei Pfade $P_1$ und $P_2$ zwischen zwei beliebigen Knoten $u,v \in V$. Entferne nun eine beliebige Kante von $P_1$, dann existiert aber immer noch der Pfad $P_2$ von $u$ nach $v$, also ist $G$ nach  entfernen einer Kante noch zusammenhängend, dies ist ein Widerspruch dazu das $G$ maximal kreisfrei ist.


"iii => i"
Sei $G$ ein Graph, der zwischen zwei beliebigen Knoten einen eindeutigen Pfad besitzt, insbesondere ist $G$ dadurch zusammenhängend
Angenommen $G$ besitzt einen Kreis $C$, dann existieren zwei Pfad zwischen zwei Knoten $u,v \in V(C)$. Dies ist ein Widerspruch dazu, dass $G$ nur einen eindeutigen Pfad zwischen je zwei Knoten besitzt. $G$ ist somit kreisfrei.



Ehrlich gesagt, glaube ich dies ist alles falscher als falsch, könnte mir bitte Jemand helfen, dies irgendwie sinnvoll hinzubekommen?

LG

Sophia


SophiaS
Aktiv
Dabei seit: 04.06.2019
Mitteilungen: 37
Beitrag No.1, vom Themenstarter, eingetragen 2020-10-21 06:16

Ich habe nun noch einmal eine Nacht darüber nachgedacht und so falsch schaut es für mich nun doch nicht mehr aus, oder?

LG

Sophia


thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 895
Herkunft: Kiel, Deutschland
Beitrag No.2, eingetragen 2020-10-21 08:27
\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)
Hallo Sophia,

2020-10-21 06:16 - SophiaS in Beitrag No. 1 schreibt:
Ich habe nun noch einmal eine Nacht darüber nachgedacht und so falsch schaut es für mich nun doch nicht mehr aus, oder?
\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)

die Richtungen \((\mathrm i)\implies (\mathrm  {ii})\) und \((\mathrm {iii})\implies (\mathrm  {i})\) sehen ziemlich gut aus.

Bei der verbleibenden Richtung müsstest du noch ein paar Worte dazu verlieren, warum ein maximal kreisfreier Graph zusammenhängend ist.

mfg
thureduehrsen
\(\endgroup\)

SophiaS
Aktiv
Dabei seit: 04.06.2019
Mitteilungen: 37
Beitrag No.3, vom Themenstarter, eingetragen 2020-10-21 08:40

Dankeschön




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=249907=7080
Druckdatum: 2021-04-10 20:17