| 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: 893
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?
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
|
|
