Fünffarbensatz < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:39 Fr 17.02.2006 | | Autor: | Tyr7 |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo,
habe eine Frage zu der Vorgehensweise bei dem Beweis, dass sich jede Landkarte mit 5 Farben färben lässt.
Bei dem Beweis wird zuhilfe genommen, dass jeder einfache, planare Graph eine Knoten mit Grad [mm] \le [/mm] 5 besitzt. Dann wird gezeigt, dass sich dieser Knoten und seine Nachbarn mit 5 Farben färben lässt.
Meine Frage ist, was passiert mit den Knoten, die einen höheren Grad als 5 haben. Wird der Knoten mit dem Grad [mm] \le [/mm] 5 entfernt, nachdem er gefärbt wurde, so dass die übrigen Knoten, die früher einen höheren Grad als 5 hatten, jetzt einen niedrigeren Grad haben und das Ganze so weiter, bis es keinen Knoten mehr gibt, der den Grad >5 hat.
Vielen Dank und viele Grüße
Tyr
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:04 Fr 17.02.2006 | | Autor: | Frank05 |
> habe eine Frage zu der Vorgehensweise bei dem Beweis, dass
> sich jede Landkarte mit 5 Farben färben lässt.
> Bei dem Beweis wird zuhilfe genommen, dass jeder einfache,
> planare Graph eine Knoten mit Grad [mm]\le[/mm] 5 besitzt. Dann
> wird gezeigt, dass sich dieser Knoten und seine Nachbarn
> mit 5 Farben färben lässt.
>
> Meine Frage ist, was passiert mit den Knoten, die einen
> höheren Grad als 5 haben. Wird der Knoten mit dem Grad [mm]\le[/mm]
> 5 entfernt, nachdem er gefärbt wurde, so dass die übrigen
> Knoten, die früher einen höheren Grad als 5 hatten, jetzt
> einen niedrigeren Grad haben und das Ganze so weiter, bis
> es keinen Knoten mehr gibt, der den Grad >5 hat.
Naja man nimmt ja in dem Beweis nicht nur einfach so einen Knoten in die Hand und schaut was so lustiges passiert wenn man ihn anmalt.
Der Beweis basiert auf einer Induktion über die Anzahl der Knoten. Der Induktionsanfang ist dabei natürlich trivial und im Induktionsschritt wird dann der von dir angesprochene Knoten betrachet, um den Graphen ohne dieses Knoten mittels der Induktionshypothese zu färben.
Dabei besagt die Eulersche Polyederformel, dass eben ein Knoten mit [mm]\gamma(v) \le 5[/mm] existiert.
Falls nun gilt, dass [mm]\gamma(v) < 5[/mm] kann der Graph ohne diesen Knoten nach IH gefärbt werden, und der Knoten v hat nur max. 4 Nachbarn, womit die 5te Farbe für ihn übrig bleibt.
Interessanter ist der Fall [mm]\gamma(v) = 5[/mm].
Hier wird nun festgestellt, dass es mind. zwei Nachbarknoten von v gibt [mm]v_1, v_2[/mm], die nicht miteinander benachbart sind (sonst liegt ein Widerspruch zum Satz v. Kuratowski vor). Wenn man jetzt den Knoten v entfernt liegen [mm]v_1, v_2[/mm] o.B.d.A. an der gleichen Fläche. Nun identifiziert man diese beiden Knoten miteinander und färbt den daraus resultierenden Graphen gemäß IH. Damit haben dann die beiden Knoten die gleiche Farbe und es bleibt wieder die 5te Farbe für den Knoten v.
Es werden also nicht irgendwie sukzessive Knoten entfernt, sondern nur ein einziger, was genügt um die Induktion durchzuführen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:28 Fr 17.02.2006 | | Autor: | Tyr7 |
Hallo,
Mir ging es hauptsächlich darum, warum es auch für Graphen mit einer hohen Anzahl von Knoten geht und vor allem warum es für einen Knoten funktioniert, der den Grad > 5 hat.
Die Eulersche Polyederformel sagt, dass es einem mit [mm] \le [/mm] 5 gibt, aber was ist mit anderen, die vielleicht einen größerer Grad haben?
Bei der Induktion geht man von 5 Knoten zu 5+1 Knoten. Dabei wird gezeigt, dass es bei 6 Knoten geht (v + 5 Nachbarn) und somit gilt es auch für Anzahl Knoten > 6?
Viele Grüße
Tyr
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:48 Sa 18.02.2006 | | Autor: | Frank05 |
> Mir ging es hauptsächlich darum, warum es auch für Graphen
> mit einer hohen Anzahl von Knoten geht und vor allem warum
> es für einen Knoten funktioniert, der den Grad > 5 hat.
> Die Eulersche Polyederformel sagt, dass es einem mit [mm]\le[/mm] 5
> gibt, aber was ist mit anderen, die vielleicht einen
> größerer Grad haben?
>
> Bei der Induktion geht man von 5 Knoten zu 5+1 Knoten.
> Dabei wird gezeigt, dass es bei 6 Knoten geht (v + 5
> Nachbarn) und somit gilt es auch für Anzahl Knoten > 6?
Dann verstehe ich deine Frage nicht richtig.
Ich fasse die Induktion so auf, dass man von n+1 auf n Knoten geht. Egal wieviele Knoten vorhanden sind gibt es den Knoten mit Grad < 6. Nun kann es natürlich noch andere Knoten geben, die einen höheren Grad haben. Aber was für eine Rolle spielt das?
Nachdem aus dem Graphen mit n+1 Knoten ein Knoten entfernt wurde verbleibt ein Graph mit n Knoten. Gemäß dem Prinzip der Induktion gibt es eine Färbung, da auch hier ein Knoten vom Grad < 6 vorhanden sein wird. Und wieder kann es Knoten geben, deren Grad größer ist. Aber ich sehe immer noch nicht wieso das interessant sein sollte?
Falls du Probleme hast zu verstehen, was langfristig mit Knoten eines hohen Grades in dieser Induktion passiert, dann sieh dir vielleicht mal als Beispiel einen Stern-Graphen an, also einen Graphen mit einem zentralen Knoten v und k weiteren Knoten, die jeweils eine Kante zu v haben. In der Induktion wird zuerst stets einer der äußeren Knoten entfernt, um den Restgraphen zu färben. Führt man das oft genug durch, so wird schließlich auch der Grad von v < 6 sein. Wenn das der Fall ist erhält der Knoten v seine Farbe und es können wieder alle entfernten Knoten wie im Beweis beschrieben hinzugefügt werden, so dass jeweils mind. eine freie Farbe zur Verfügung steht.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:55 Sa 18.02.2006 | | Autor: | Tyr7 |
Hallo,
ja, genau so habe ich es in dem ersten Posting gemeint. Dabei dachte ich auch an einen Stern mit mehr als 5 Nachbarn (Zacken).
Somit werden die jeweils gefärbten Zacken entfernt, bis der Mittelpunkt [mm] \le [/mm] 5 ist und dann geht es.
Hmmm, vielleicht sind die Zacken noch nicht gefärbt, wenn sie entfernt (nicht beachtet) werden. Aber das Prizip ist mir jetzt klar.
Vielen Dank
Tyr
|
|
|
|
