Fünf-Farben-Satz |
| 10.12.2025, 16:36 | su12357 | Auf diesen Beitrag antworten » |
| Fünf-Farben-Satz Aber WARUM ERFÜLLT G_1 die Bedingungen I,II und III und warum ist er dann 5-Listenfärbar Meine Ideen: So ich muss eine Ausarbeitung zum Fünf Farben Satz schreiben. Satz. Alle ebenen Graphen G können 5-listengefarbt werden: ¨ ? 
G) ? 5. Dann kommt: Wir beweisen per Induktion die folgende stärkere Aussage Sei G = (V, E) ein fast-triangulierter Graph, und sei B der Kreis,der das unbeschrankte Gebiet begrenzt. Wir machen folgende ¨ Annahmen uber die Farblisten ¨ C(v), v ? V : (1) Zwei benachbarte Ecken x, y von B sind bereits mit (verschiedenen) Farben ? und ? gefarbt. (2) |C(v)| ? 3 fur alle anderen Ecken v of B. (3) |C(v)| ? 5 fur alle Ecken v im Inneren. Dann kann die Farbung von x und y durch Auswahl aus den vorgegebenen Farblisten zu einer gültigen Färbung von G fortgesetzt werden. Wir führen den Beweis durch Induktion nach der Anzahl n der Knoten vor. Induktionsanfang: Für n?3 ist die Aussage trivial, da für den einzig nicht gefärbten Knoten v ja |C(v)|?3 Farben zu Verfügung stehen. Daraus kann man schließen, dass sich v mit einer von den Farben färben lässt. Induktionsschritt: Wir nehmen nun an, dass die Aussage für ?k Knoten gilt. Es gilt nun zu zeigen, dass daraus die Aussage für k+1 Knoten resultiert. Dieser Schritt erfordert die Unterscheidung zweier Fälle: Fall 1: Wir nehmen an, dass der Kreis B eine Sehne hat. Das bedeutet, dass es eine Kante gibt, die zwei Knoten u,v ? B verbindet, jedoch nicht zu B gehört. Die Sehne teilt den Graphen G in zwei Untergraphen G_1 und G_2. G_1 wird durch B_1 (der einen Hälfte des Kreises) und der Kante/ Sehne {u,v} begrenzt. G_2 wird durch die andere Hälfte des Kreises B_2 und der Kante/ Sehne {u,v} begrenzt. Betrachten wir zunächst den ersten Untergraphen G_1. Dieser enthält die Knoten u,v,x,y . G_1 ist fast-trianguliert und erfüllt die Bedingungen I, II und III und ist somit nach Voraussetzung 5-listenfärbar. Aber WARUM ERFÜLLT G_1 die Bedingungen I,II und III und warum ist er dann 5-Listenfärbar |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
