| Autor |
Beitrag |
    
Andreas
| | Veröffentlicht am Donnerstag, den 11. Januar, 2001 - 08:35: | 
|
Brauche Hilfe bei dieser Aufgabe!
Man zeige, daß jeder Baum die chromatische Zahl 2 hat.
Danke im Voraus |
Matroid (Matroid)
| | Veröffentlicht am Donnerstag, den 11. Januar, 2001 - 21:04: |
|
Hallo Andreas,
das bedeutet doch, daß man die Knoten eines Baumes mit 2 Farben einfärben kann, so daß je zwei durch eine Kante verbundene Knoten verschieden gefärbt sind.
Zum Beweis:
Sagen wir, ich habe zwei Farben, nämlich rot und blau. Und einen Baum, das ist ein zusammenhängender, ungerichteter Graph ohne Schleifen oder Kreise.
Algorithmus für eine Zweifärbung der Knoten eines Baumes:
1. Wähle einen beliebigen Knoten des Baumes und färbe ihn rot.
Nun wende abwechselnd die Vorschriften 2 und 3 an, solange, bis alle Knoten gefärbt sind.
2. Färbe alle mit einem roten Knoten durch eine Kante verbundenen Knoten blau, wenn sie noch nicht gefärbt sind.
3. Färbe alle mit einem blauen Knoten durch eine Kante verbundenen Knoten rot, wenn sie noch nicht gefärbt sind.
Beweis, daß dieses Verfahren funktioniert:
a) Zeige: Das Verfahren bricht nach endlich vielen Schritten ab.
Weil der Baum ein zusammenhängender Graph ist, gibt es von jedem Knoten zu jedem anderen Knoten einen Weg. Insbesondere gibt es von dem Knoten, den wir in 1. gewählt haben einen Weg zu jedem anderen Knoten. Ein Weg hat eine Länge, die man mit der Anzahl der Kanten auf dem Weg angeben kann, d.h. jeder Knoten wird nach endlich vielen Schritten gefärbt.
b) Zeige: Wenn nach einigen Schritten ein Knoten o.B.d.A. rot gefärbt ist und es mit ihm durch eine Kante verbundene Knoten gibt, dann sind diese Knoten nicht mit einem blauen Knoten durch eine Kante verbunden.
Annahme des Gegenteils: Sei k der Name des Knotens aus 1., sei k' ein Knoten, der rot gefärbt ist, und der noch durch Kanten mit bisher ungefärbten Knoten verbunden ist. Sei k'' einer dieser ungefärbten Knoten. Wenn wir annehmen, daß k'' durch eine Kante mit einem bereits blau gefärbten Knoten k''' verbunden ist, dann gibt es also einen Weg von k nach k' und einen Weg von k nach k''' (denn nur wenn es von Ursprungsknoten k einen Weg zu k' und zu k''' können beide gefärbt worden sein).
Da aber auch k' und k'' sowie k'' und k''' durch eine Kante verbunden gibt, gibt es einen Kreis im Baum. Das ist ein Widerspruch.
Gruß
Matroid |
|
