 |
 |
 |
 |
 |
 |
Startseite » Forum » Graph 2-färbbar genau dann wenn..
Graph 2-färbbar genau dann wenn..
Universität / Fachhochschule
Graphentheorie
Tags: Graphentheorie
 
|
  |
|---|
|
Guten Abend, ich soll folgende Satz beweisen: Eine normale Landkarte(ohne Schlingen,Brücken,Mehrfachkanten) ist genau dann 2-färbbar wenn der Grad jedes Knote gerade ist. Nehmen wir an dass die Landkarte 2 färbbar ist und der Grad der Knote ungerade ist. Für den Grad gleich 3 glaube wir hätten wir ein Gegenbeispiel somit wäre diese Richtung fertig. Für die Gegenrichtung ist es ein bisschen schwerer: Ich würde gerne zeigen dass wenn der Grad jede Knote gerade ist dann ist unser Graph bipartit und wenn es bipartit ist dann können wir eine 2-Färbung haben. Mein Problem ist von die gerade Knotengrad die Bipartitheit zu folgen. Hier kann man als Zwischenschritt auch haben dass wenn es eine gerade Knotengrad hat dann ist es ein Euler'sche Graph und dann die Bipartitheit folgen aber dies kann ich auch nicht. Bipartit bei uns war definiert nur als eine Graph wo die Knotenmenge in zwei disjunkte Teilmengen geteilt werden kann. Wäre sehr dankbar um Hilfe. Beschäftige mich ganze Tag mit diesem Beweis. LG simssims Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Hallo, stimmt der Satz denn? Betrachte den vollständigen Graphen , also bis auf Isomorphie eindeutigen Graphen, bei dem die einzigen beiden Knoten durch eine Kante verbunden sind. Sicher ist er 2-färbbar und ebenso sicher hat jeder Knoten einen ungeraden Grad, nämlich 1. Kann es sein, dass du irgend etwas weggelassen hast oder falsch abgetippt? Kannst du nicht einfach einen Scan der Originalaufgabenstellung liefern? Mfg Michael |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
1543182
1543162