Bipartiter Graph < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Zeige: Ein Graph G ist genau dann bipartit, wenn jede geschlossene Wanderung in G gerade Länge hat. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Die eine Richtung ist klar:
Sei G bipartit. Dann können wir die Knoten des Graphen so einfärben, dass jede Kante einen roten mit einem blauen Knoten verbindet. Eine geschlossene Wanderung durchläuft dann abwechselnd einen roten und einen blauen Knoten. Damit Anfangs- und End- Knoten (wie für geschlossene Wanderung notwendig) die selbe Farbe haben, muss die Länge der Wanderung also Vielfaches von 2 sein.
Allerdings weiß ich nicht, wie ich zeige, dass ein Graph in dem alle geschlossene Wanderungen gerade Läge haben, bipartit ist. Kann mir da jemand helfen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:29 So 15.01.2012 | | Autor: | hippias |
> Zeige: Ein Graph G ist genau dann bipartit, wenn jede
> geschlossene Wanderung in G gerade Länge hat.
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Die eine Richtung ist klar:
>
> Sei G bipartit. Dann können wir die Knoten des Graphen so
> einfärben, dass jede Kante einen roten mit einem blauen
> Knoten verbindet. Eine geschlossene Wanderung durchläuft
> dann abwechselnd einen roten und einen blauen Knoten. Damit
> Anfangs- und End- Knoten (wie für geschlossene Wanderung
> notwendig) die selbe Farbe haben, muss die Länge der
> Wanderung also Vielfaches von 2 sein.
>
> Allerdings weiß ich nicht, wie ich zeige, dass ein Graph
> in dem alle geschlossene Wanderungen gerade Läge haben,
> bipartit ist. Kann mir da jemand helfen?
Wenn $G$ zusammenhaengend ist,dann wuerde ich folgendes versuchen: Sei $a$ eine beliebige Ecke. Definiere $X:= [mm] \{x\in G|\text{$x$ hat geraden Abstand zu $a$}\}$ [/mm] und $Y:= [mm] G\setminus [/mm] X$; also $Y$ ist die Menge der Elemente, die zu $a$ ungeraden Abstand haben. Wenn z.B. [mm] $r,s\in [/mm] Y$, dann existieren Pfade ungerader Laenge von $a$ nach $r$ und von $a$ nach $s$. Waeren $r$ und $s$ verbunden, dann haette man einen geschlossen Pfad der Laenge ungerade+ungerade$+1$= ungerade.
P.S. Mmmmh, Schokokuchen!
|
|
|
|
