Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Färbung von Graphen und planare Graphen

Färbung von Graphen und planare Graphen

Universität / Fachhochschule

Graphentheorie

Tags: Graphentheorie

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
Cyborg

Cyborg aktiv_icon

18:00 Uhr, 06.02.2016

Antworten
Hallo,

Ich stehe vor folgender Aufgabe:
Sei G ein planarer Graph. Beweisen Sie: Jeder ebene Graph enthält einen Knoten v mit d(v)≤5.
Folgern Sie daraus den 6 Farbensatz.

Beweisidee:
G planar --> lässt sich in der Ebene zeichnen. d.h. die Knotengrade sind nach oben beschränkt.
Mit der Eulerschen Polyederformel gilt E-K+F=2.
Andererseits ist 3E≤2K, weil jede Kante 2 Ecken hat, aber an jeder Ecke mindestens 3 Kanten zusammenkommen. Wenn jedes Land mindestens 6 Nachbarn hätte, d.h. jede Fläche mindestens 6 Kanten hätte (und natürlich jede Kante zu 2 Flächen gehört), dann wäre 6F≤2K. Damit ergibt sich aber der Widerspruch
2=E-K+F ≤ 2/3 K – K + 1/3 K=0.
Wegen diesem Widerspruch muß es also mindestens ein Land mit höchstens 5 Nachbarn geben.

6Farbensatz: G ist 6-färbbar
Beweis durch VI nach der Anzahl der Länder:
IA: Für eine Karte mit nur einem Land ist G 6-färbbar, da man nur eine Farbe benötigt.
IV: Karte mit n+1 Ländern: Wenn es ein Land gibt, daß nur 5 (oder weniger) Nachbarn hat, dann benutze IV, um die anderen n Länder mit 6 Farben zu färben. Weil das letzte Land nur 5 Nachbarn hat, gibt es eine Farbe, die von seinen Nachbarn nicht verwendet wurde und mit der dieses letzte Land also gefärbt werden kann.für jede Zerlegung der Sphäre gibt es somit ein Land, das höchstens 5 Nachbarn hat.

Kann ich das so schreiben? Ich hoffe mir kann jemand helfen.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)
Online-Nachhilfe in Mathematik
Antwort
Sina86

Sina86

19:20 Uhr, 06.02.2016

Antworten
Hallo Cyborg,

ich sage dir gleich mal, dass ich keine Graphenexpertin bin, mich aber ein wenig damit beschäftigt habe. Habe jetzt nicht alles verfolgt, aber es fällt mir gleich am Anfang der Beweisidee etwas auf:

"G planar --> lässt sich in der Ebene zeichnen. d.h. die Knotengrade sind nach oben beschränkt."

Warum folgt daraus die Beschränktheit der Knotengrade? Gegenbeispiel:

Sei G=(V,E):=(0×ℤ,{0×[z,z+1]∣z∈ℤ})∪({(1,0)T},{{(1,0)T+t⋅((0,z)-(1,0))∣t∈[0,1]}∣z∈ℤ})
wobei wir für M⊆ℝ definieren: 0×M:={(0,m)T∣m∈M}⊂ℝ2

Dies ist auf jeden Fall ein planarer Graph, denn der Graph ist eigentlich die y-Achse, wobei die Vetoren, die als y-Eintrag ganze Zahlen besitzen, die Vertices sind und die dazwischenliegenden Intervalle die dazugehörigen Kanten, plus einen einzelnen Punkt (1,0) auf der x-Achse, welcher mit jedem Vertex auf der y-Achse verbunden ist. Der Graph ist planar, denn die Intervalle auf der y-Achse sind per Definition bis auf die Endpunkte disjunkt und es gilt

(1,0)T+t⋅((0,z1)-(1,0))=(1,0)T+s⋅((0,z2)-(1,0))⇔(-t,z1⋅t)=(-s,z2⋅s)

Aus der ersten Komponente folgt also -t=-s⇔t=s und damit automatisch z1=z2.

Nun ist aber degG((1,0))=∣ℤ∣=∞, also der Grad nicht beschränkt.

Beste Grüße
Sina
Cyborg

Cyborg aktiv_icon

12:08 Uhr, 07.02.2016

Antworten
Hallo Sina,

besten Dank für deine Antwort, so habe ich es noch gar nicht betrachtet ;-)

Wenn ich den ersten Satz weglasse, ist der Rest dann so korrekt?

LG Cyborg
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.