Graphen einfärben

Neue Frage »

05.02.2007, 13:11	katrinchen_	Auf diesen Beitrag antworten »
Graphen einfärben hi, ich soll beweisen das man die knoten eines ungerichteten Graphen mit Maximalgrad k mit höchstens k+1 Farben so einfärben kann, dass adjazente Knoten immer verschiedene Farben bekommen. Was solln denn adjazente Knoten sein? Benachbarte Knoten?? Wie soll ich mir das vorstelln, bei einem Graph mit z.b. grad 1 sind z.b. 5 Knoten in einer ebene, also benötigt man doch nur 2 verschiedene farben.... Bei einem Grapg mit grad 2, dann sind doch die knoten von ebene 1 und ebene 2 auch noch adjazent oder??
05.02.2007, 14:01	Divergenz	Auf diesen Beitrag antworten »
RE: Graphen einfärben Hallo, ja adjazente Knoten sind benachbarte, da sie einen Eintrag in der den Graphen repräsentierenden Adjazenzmatrix haben. Dein Beispiel zum Maximalgrad 1 stimmt doch dann, wenn du 2=1+1 Farben benötigst. Die Idee ist halt, dass wenn du einen Knoten vom Maximalgrad färben willst, du eine Farbe benötigst und im worst case k weitere Farben für seine Nachbarn, falls diese untereinander alle benachbart sind. Was du mit deinem zweiten Bsp. meinst verstehe ich leider nicht!
05.02.2007, 14:17	Abakus	Auf diesen Beitrag antworten »
RE: Graphen einfärben Zur Adjazenz siehe hier. Grüße Abakus ** verschoben nach Sonstiges (Graphentheorie) **
05.02.2007, 14:18	katrinchen_	Auf diesen Beitrag antworten »
ja, also ich wollte wissen wie das genau gemeint ist mit dem nachbarn, aber ich glaub ich habs verstanden, also alle knoten die mit einer kante direkt verbunden sind, sind nachbarn oder?
05.02.2007, 14:18	Divergenz	Auf diesen Beitrag antworten »
genau!
05.02.2007, 14:26	katrinchen_	Auf diesen Beitrag antworten »
okay, kann man das direkt mit induktion beweisen, oder is das ein schlechter weg und es geht schneller mit nem inderekten beweis
Anzeige

05.02.2007, 14:29	Divergenz	Auf diesen Beitrag antworten »
Ich würde sagen, es geht indirekt ganz gut! Für ne Induktion sieht mir das recht kompliziert aus.
05.02.2007, 15:05	katrinchen_	Auf diesen Beitrag antworten »
ja hmm aber irgendwie gelingt mir das nicht so richtig.. ich hatte jetzt einfach geschrieben, das bei einem knoten mit null kanten eine farbe genügt, bei einem knoten mit einer kante2 farben.....bei einem knoten mit k kanten, k+1 farben ausreichen....aber das is glaube kein beweis sondern nur ne behauptung.
05.02.2007, 15:26	Divergenz	Auf diesen Beitrag antworten »
RE: Graphen einfärben Also, ich hatte ja schon mal angefangen. Nimm dir einen Knoten mit Maximalgrad und färbe ihn und seine Nachbarn. Dafür brauchst du doch nur alle k+1 Farben, wenn die Nachbarn alle gegenseitig benachbart sind. Ist das aber der Fall, so besitzen sie damit auch den Grad k und können keine weiteren Nachbarn haben. Nun kannst du dir auf diesem Weg ja mal weiter überlegen, wie man beim Färben vorgehen muss oder was passieren muss, um eine weitere Farbe zu benutzen! Was passiert dabei mit den Graden der beteiligten Knoten?!
05.02.2007, 15:33	katrinchen_	Auf diesen Beitrag antworten »
na wenn ich eine weitere farbe benutze, dann müsste doch der grad abnehmen.
05.02.2007, 16:11	Divergenz	Auf diesen Beitrag antworten »
Nein, wenn du gezwungen wärst an einem Knoten die k+2te Farbe zu verwenden, dann doch nur, weil dieser Knoten schon Nachbarn mit insgesamt k+1 Farben besitzt. Das heißt aber, dass dieser Knoten mind. den Grad k+1 haben muss, was ein Widerspruch zur Annahme ist!
05.02.2007, 16:25	katrinchen_	Auf diesen Beitrag antworten »
wieso ist das denn ein widerspruch?? Die annahme heisst doch, bei grad k gibts k+1 verschiedene farben.. also bei k+1 gibts k+2 farben, wo ist da der widerspruch?
05.02.2007, 17:02	Divergenz	Auf diesen Beitrag antworten »
Es ist ein Widerspruch, da du zeigen willst, dass es eben nicht nötig ist k+2 Farben zu benutzen, wenn der Maximalgrad k ist! Die Annahme ist also, Maiximalgrad ist zwei, man braucht aber mind. k+2 Farben. Dann war jetzt der Schluss, dass ein Knoten einen hören Grad hat, also ein Widerspruch!
05.02.2007, 17:52	katrinchen_	Auf diesen Beitrag antworten »
achso, es geht zwar ist aber nicht nötig?
06.02.2007, 10:48	Divergenz	Auf diesen Beitrag antworten »
Natürlich kann man auch mehr Farben benutzen (soviel wie eben Knoten da sind), aber die Kunst und das Interessante ist ja, unter der Bedingung dass benachbarte Knoten verschiedene Farben haben, so wenig wie möglich Farben zu benutzen. Und da ist eben die Behauptung, dass man maximal k+1 Farbe benötigt!

Neue Frage »

Antworten »

Graphen einfärben

Verwandte Themen