Graph, Kreis, zusammenhängend < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:15 Mi 24.10.2012 | | Autor: | Lu- |
| Aufgabe | | Zeige dass ein Graph G(V,E) mit |V(G)| >= 3 zweifach zusammenhängend ist, wenn es für je zwei Knoten v,w aus V einen Kreis (das ist eine geschlossene Wanderung [mm] v_0, v_1 [/mm] , [mm] ..v_n [/mm] in G, wobei [mm] v_i \not= v_j [/mm] für alle i [mm] \not=j [/mm] mit der einzigen ausnahme [mm] v_0 =v_n) [/mm] gibt , der v und w enthält. |
Hallo
Wenn es für je zwei Knoten v,w aus V einen Kreis gibt, der v und w enthält, So liegt jede Kante auf einem Kreis. Es gibt zwischen je zwei Knoten zwei Wege. Durch das Entfernen eines beliebigen Knotens aus G bleibt immer noch ein Weg erhalten.
=> G zweifach zusammenhängend
Ich glaub die Argumentation ist etwas undurchsichtig, könnte mir vlt. wer helfen das zu präzesieren?
Liebe Grüße
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:57 Mi 24.10.2012 | | Autor: | tobit09 |
Hallo Lu,
wie habt ihr "zweifach zusammenhängend" definiert?
"Zwischen je zwei Knoten gibt es zwei disjunkte Wege"?
> Wenn es für je zwei Knoten v,w aus V einen Kreis gibt, der
> v und w enthält, So liegt jede Kante auf einem Kreis.
Warum?
> Es
> gibt zwischen je zwei Knoten zwei Wege.
Warum?
Seien v,w Knoten. Nach Voraussetzung existiert ein Kreis, auf dem v und w liegen. Der Kreis "enthält" zwei disjunkte Wege zwischen v und w.
Ich weiß leider nicht, ob das genau genug ist.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:01 Mi 24.10.2012 | | Autor: | Lu- |
Hallo,
danke für den Post.
Ein Graph G heißt d-fach zusammenhängend (für d [mm] \in \IN) [/mm] wenn
|V(G)| > d
und für jede Teilmenge T [mm] \subseteq [/mm] V(G) mit |T| < d der durch V(G) ohne T induzierte Teilgraph zusammenhägend ist.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:26 Mi 24.10.2012 | | Autor: | tobit09 |
Deine und meine Argumentation zusammen, noch ein wenig formaler aufgeschrieben:
Sei [mm] $T\subseteq [/mm] V(G)$ einelementig mit Element t und H der durch [mm] $V(G)\setminus [/mm] T$ induzierte Teilgraph von G.
Seien [mm] $v,w\in [/mm] H$. Insbesondere [mm] $v,w\in [/mm] G$. Nach Voraussetzung existiert ein Kreis in G, auf dem v und w liegen. Der Kreis beschreibt zwei disjunkte Wege in G zwischen v und w. Höchstens einer dieser Wege kann t enthalten. Der andere der beiden Wege ist auch ein Weg in H zwischen v und w.
Keine Ahnung, ob das genau genug ist. Habe selbst nie eine Vorlesung in Graphentheorie gehört...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:00 Do 25.10.2012 | | Autor: | Lu- |
dankeschön.
|
|
|
|
