H3.9.b - chromatische Zahl

ab26iget.stud.tu
Mausschubser
Mausschubser
Beiträge: 63
Registriert: 14. Okt 2008 20:19

H3.9.b - chromatische Zahl

Beitrag von ab26iget.stud.tu »

Um die Formel zu bestimmen , ich habe das gefunden :

Der Satz von Vizing besagt, dass der chromatische Index eines Graphen mindestens so groß wie sein Maximalgrad aber höchstens eins größer als dieser ist, also formal:

GradMax (G) <= chromatische Index (G) <= GradMax (G) +1
Obwohl der Maximalgrad leicht zu bestimmen ist und der chromatische Index nur einen von zwei möglichen Werten annehmen kann, ist das Problem, für einen gegebenen Graphen genau diesen einen Wert zu bestimmen

Kann das richtig sein?
Vielen Dank !

kned
Mausschubser
Mausschubser
Beiträge: 80
Registriert: 14. Okt 2008 18:49
Kontaktdaten:

Re: H3.9.b - chromatische Zahl

Beitrag von kned »

Überlegen Sie sich die chromatische Zahl für beliebige, vollständige Graphen.
Vollständiger Graph ist ein Begriff aus der Graphentheorie und bezeichnet einen Graphen, in dem alle Knoten miteinander verbunden sind.
also stimmt deine Lösung nicht ganz :D

ab26iget.stud.tu
Mausschubser
Mausschubser
Beiträge: 63
Registriert: 14. Okt 2008 20:19

Re: H3.9.b - chromatische Zahl

Beitrag von ab26iget.stud.tu »

kned hat geschrieben:
Überlegen Sie sich die chromatische Zahl für beliebige, vollständige Graphen.
Vollständiger Graph ist ein Begriff aus der Graphentheorie und bezeichnet einen Graphen, in dem alle Knoten miteinander verbunden sind.
also stimmt deine Lösung nicht ganz :D
ja das stimmt nicht ganz ,

MonkeyT
DON'T PANIC
Beiträge: 42
Registriert: 17. Apr 2009 18:02

Re: H3.9.b - chromatische Zahl

Beitrag von MonkeyT »

Ich habe hier folgendes Beispiel (siehe Anhang)

grad_max(G) = 4
chromatischer Zahl = 2 ???

Das steht ja im Widerspruch zum Satz von Vizing, was ist nicht korrekt an meinem Beispiel?
Dateianhänge
Graph_G_1.jpg
Graph_G_1.jpg (28.03 KiB) 620 mal betrachtet

h_thies
Neuling
Neuling
Beiträge: 6
Registriert: 19. Mär 2009 00:03

Re: H3.9.b - chromatische Zahl

Beitrag von h_thies »

Der Satz von Vizing gilt für Kantenfärbungen, nicht für Knotenfärbungen.

Radze
Erstie
Erstie
Beiträge: 21
Registriert: 10. Okt 2008 10:14

Re: H3.9.b - chromatische Zahl

Beitrag von Radze »

Um die Antwort etwas ausfürhrlicher zu gestalten:
Der Satz von Vizing besagt, dass der chromatische Index eines Graphen mindestens so groß wie sein Maximalgrad aber höchstens eins größer als dieser ist.
Ich denke das Problem hierbei ist, dass Vizing die Aussage für Kantenfärbung getroffen hat.

Die chromatische Zahl hingegegen bezieht sich auf die Knotenfärbung.

Damit haben wir gezeigt, dass Terminologie in der Graphenthoerie die größten Probleme schafft. qed ^^

MonkeyT
DON'T PANIC
Beiträge: 42
Registriert: 17. Apr 2009 18:02

Re: H3.9.b - chromatische Zahl

Beitrag von MonkeyT »

LOL :mrgreen:

Danke für den Hinweis ;)

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: H3.9.b - chromatische Zahl

Beitrag von bruse »

Für planare Graphen gilt ja außerdem noch der Vierfarbensatz. So einfach konnte es also eh nicht gewesen sein :-)

edit: Das ist für die Aufgabenstellung aber egal.
Zuletzt geändert von bruse am 10. Mai 2009 16:55, insgesamt 1-mal geändert.
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

daniel_b
Computerversteher
Computerversteher
Beiträge: 363
Registriert: 15. Okt 2008 16:23

Re: H3.9.b - chromatische Zahl

Beitrag von daniel_b »

Wenn ich nicht irgendwas falsch gemacht hab, ist die 3.9b ohne einen einzigen Satz, Beweis, Gesetz, etc. lösbar. Was macht ihr denn da?

Antworten

Zurück zu „Archiv“