 |
 |
 |
 |
 |
 |
Startseite » Forum » bipartiter Graph
bipartiter Graph
Universität / Fachhochschule
Graphentheorie
Tags: Graphentheorie
 
|
  |
|---|
|
zeige: Ein Graph ist genau dann bipartit, wenn jede geschlossene Wanderung in gerade Länge hat. kann mir irgendjemand sagen, wie ich das zeigen soll?? Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Eine Richtung ist ja wohl einfach: Wenn bipartit ist, kann man seine Ecken so färben, dass jede Kante einen roten und einen blauen Endpunkt hat. Eine geschlossene Wanderung durchläuft abwechselnd rote und blaue Ecken, also insgesamt eine gerade Anzahl Kanten, da die Anfangsfarbe wieder getroffen werden muss. Umgekehrt nehmen wir an, es gäbe Graphen,in denen jede geschlossen Wanderung gerade ist, die aber nicht bipartit sind. Wenn dem so ist, gibt es sogar einen (von der Kantenzahl her) kleinsten Graphen mit dieser Eigenschaft. hat gewiss Kanten, denn kantenlose Graphen sind trivialerweise bipartit. Wähle eine Kante und betrachte den Graphen G',der aus durch Streichen der Kante entsteht. In ist auch jede geschlossene Wanderung gerade. Da weniger Kanten als hat, ist bipartit. Betrachte daher eine Zweifärbung von . Wenn und verschieden gefärbt sind, ist dies auch eine Zweifräbung von selbst. Wenn und gleich gefärbt sind, gibt es in keine Wanderung von nach denn zusammen mit ergäbe diese eine - demnach gerade - geschlossene Wanderung in im Widerspruch dazu, dass auf der Wanderung die Farben immer abwechseln. Also kann ich in der Zusammenhangskomponente von di enthält die Farben vertauschen, ohne dass beeinflusst wird, und nbin wieder beim ersten Fall. |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
847723
847298