Planarer Graph als kantendisjunkte Vereinigung dreier Wälder
lhal...@aol.com
Gezeigt werden soll, dass jeder planare Graph eine kantendisjunkte
Vereinigung dreier Wälder (= kreisfreier Graphen) ist.
Das ist gleichbedeutend mit der Frage, ob man die Kanten so mit drei
Farben färben kann, dass kein gleichfarbiger Kreis entsteht.
Leider fehlt mir dazu die passende Beweisidee. Eine Reduktion auf die
Vierfärbbarkeit der Knoten ist mir nicht gelungen.
(Man kann sicher davon ausgehen, dass der Graph maximal planar ist.)
Philipp Zumstein
> Gezeigt werden soll, dass jeder planare Graph eine kantendisjunkte
> Vereinigung dreier Wälder (= kreisfreier Graphen) ist.
Dies wird auch (edge-)arboricity genannt.
> Das ist gleichbedeutend mit der Frage, ob man die Kanten so mit drei
> Farben färben kann, dass kein gleichfarbiger Kreis entsteht.
>
> Leider fehlt mir dazu die passende Beweisidee. Eine Reduktion auf die
> Vierfärbbarkeit der Knoten ist mir nicht gelungen.
>
> (Man kann sicher davon ausgehen, dass der Graph maximal planar ist.)
Ist dies eine Übungsaufgabe? Falls ja, könnte es hilfreich sein, zu
wissen, welche Begriffe und Sätze in der Vorlesung gezeigt wurden. Falls
nein, kann man sich einen Standardbeweis über Matroidentheorie anschauen.
Grüsse,
Philipp
kay...@web.de
Ja, es ist eine Übungsaufgabe. Behandelte Ergebnisse zur Planarität
sind:
- Eulersche Formel (|V| - |E| + |R| = 2)
- für planare Graphen gilt |E| <= 3|V| - 6 (Gleichheit bei maximaler
Planarität)
- G ist maximal planar <=> G ist Triangulation
- Vierfarbensatz
- Satz von Kuratowski
Matroidentheorie hatten wir noch gar nicht.
Man kann bei der Aufgabe von einem maximal planaren Graphen ausgehen.
Mir ist aber nicht klar, wie man bei einem Beweis z. B. die
Trianguliertheit benutzen würde.
Grüße,
Kay
Philipp Zumstein
Hm.. Ich weiss nicht ob man dies so "einfach" beweisen kann. Hier mal
ein Ansatz, der aber nur in 4 von 5 Fällen funktioniert:
Wir machen eine Induktion nach Anzahl der Knoten. Die Fälle n=1,2,3 sind
richtig. Für n>=4 nehmen wir uns einen Knoten v in der Triangulierung,
welcher Grad höchstens 5 hat. Solch einen Knoten gibt es immer; folgt
aus deinem zweitem Punkt. Nun kann man die Fälle unterscheiden, je
nachdem welchen Grad der Knoten hat. Induktiv weiss man, dass man G-v in
drei kantenspannende Bäume zerlegen kann. Nun "nehmen" wir den Knoten v
wieder dazu und setzen die Kantenfärbung entsprechend fort. Dazu muss
man für Grad 4 Knoten noch eine Diagonale einsetzen... Ich lasse die
weiteren Details weg, denn für Grad 5 Knoten funktioniert es nicht!
Zusammengefasst kann ich "nur" folgendes beweisen:
Sei G ein planarer, *4-degenerierter* Graph.
Dann kann man seine Kanten mit drei Farben
färben, so dass jede Farbkomponente keine
Kreis enthält.
Beziehungsweise könnte man auch die Aussage
Sei G ein planarer Graph.
Dann kann man seine Kanten mit *vier* Farben
färben, so dass jede Farbkomponente keinen
Kreis enthält.
analog beweisen.
Vielleicht hilft dir das etwas um die Übungsaufgabe *sinnvoll zu
bearbeiten*. Ich wäre dann an einer (Muster)Lösung für diese Aufgabe
interessiert.
Grüsse,
Philipp
kay...@web.de
Die "Musterlösung" bestand im Beweis einer Richtung des Satzes von
Nash-Williams. Ich habe nicht gehört, dass irgendeiner meiner
Kommilitonen diese Aufgabe gelöst hat... Gott sei Dank waren die
anderen drei Aufgaben auf dem Übungsblatt recht einfach. :-)
Nach mehrmaligem Googlen habe ich auch eine einfachere Lösung
gefunden, die auf einer kanonischen Ordnung der Knoten beruht.
MfG,
Kay