Diskussion:Färbung (Graphentheorie)
aus Wikipedia, der freien Enzyklopädie
Oh Hilfe! Gerne die Mathematik hier (und merci an dieser Stelle für die Arbeit, die hier drin steckt!) Aber kann irgendjemand nicht ein paar einleitende Worte schreiben, worum's hier geht? Das versteht ja noch nicht mal mehr ein Durchschnittsmathematiker wie ich, geschweige denn ein Laie, der über diesen Artikel stolpert! ;-) Uli 20:31, 22. Mär 2003 (CET)
- Werde ich machen, sobald ich zeit habe. Das habe ich auch bei den anden Graphenartikeln vor, aber da ich nur einer von sehr wenigen "Experten" hier auf diesem Gebiet bin und wenig Zeit habe, dauert das auch etwas. --Coma 13:20, 21. Feb 2004 (CET)
- Der Artikel gehört zu einer ganzen Reihe von Artikeln zur Graphentheorie und baut auf vorhergehenden Artikeln auf... Ist momentan nur für Leute, die Vorkenntnisse haben. Siehe auch Liste graphentheoretischer Artikel. --Coma 13:26, 23. Mär 2003 (CET)
- Der Artikel ist noch sehr kürzungsfähig, am Anfang ist überhaupt nicht klar, worum es geht. So kann man die Partitionen am Anfang weglassen und gleich zu den Färbungen kommen. Ich werde das machen, wenn ich dazu Zeit hab'. Galaxy07]] 21. Febr 2004
-
- Partition und Färbung gehören einfach zusammen. Jede Färbung ist eine Partition und jede Partition impliziert eine Färbung! Das kann man also nicht sinnvoll einfach weglassen! --Coma 13:20, 21. Feb 2004 (CET)
-
-
- Ja, dann macht man aber zwei Seiten, Färbungen und Partitionen, wenn man darauf Wert legt, und verlinkt sie. Es ist unschön, wenn eine Seite zu Färbungen mit der Definition einer Partition beginnt. Galaxy07
-
-
-
-
- Ja, lieber zwei kleine Artikel als einen großen. Das erleichtert den Zugang zu den Texten ungemein. Das ist sogar wissenschaftlich erforscht. Wichtig ist aber, dass die Texte sinnvoll und hilfreich miteinander verlinkt sind. Stern 16:33, 21. Feb 2004 (CET)
-
-
Inhaltsverzeichnis |
neue Fassung
So, ich hab jetzt meine Fassung geschrieben. Ungenutzt sind folgende Textstellen geblieben, die in einfach mal hier reinkopiere:
Partitionen
Ist G=(V,E) ein ungerichteter Graph ohne Mehrfachkanten und P={V1,...,Vk} eine Partition von V, so dass für jedes i aus {1,...,k} gilt, dass je zwei beliebige verschiedene Knoten v und w von Vi nicht benachbart sind, d.h. v und w sind durch keine Kante verbunden, so nennt man P eine Partition von G. Enthält P genau zwei Elemente, so nennt man P auch Bipartition. Ein Graph G=(V,E), der eine Partition P={V1,...,Vk} besitzt nennt man k-partit. Die Partition mit genau |V| Elementen (d.h. die Partition, die nur einelementige Teilmengen enthält} ist eindeutig und man nennt sie trivial. Sie existiert offensichtlich in jedem ungerichteten Graphen ohne Mehrfachkanten, d.h. jeder Graph ist |V|-partit. Einen 2-partiten Graph, d.h. einen Graphen, der eine Bipartition besitzt, nennt man auch bipartit oder paar (siehe hierzu auch bipartiter Graph).
Ist P={V1,...,Vk} eine Partition von G und ist für jedes i jeder Knoten aus Vi mit jedem Knoten aus V\Vi benachbart, so nennt man G vollständig k-partit. Ist k=|V|, d.h. P ist trivial, so nennt man G auch einfach nur vollständig. Offensichtlich ist dies genau dann der Fall, wenn jeder Knoten mit jedem anderen Knoten benachbart ist.
Ein Graph ist offenbar genau dann k-partit, wenn er k-färbbar ist. Man bezeichnet daher oft auch eine Partition eines Graphen als Färbung und sagt, dass ein Graph G eindeutig k-färbbar ist, wenn es nur eine Partition von G mit k-Farben gibt.
zu NP-Vollständigkeit
Auch sind keine vernünftigen Approximationsalgorithmen bekannt. Im Gegenteil, es konnte gezeigt werden, dass unter gewissen Annahmen kein Approximationsalgorithmen existiert, der besser als irgend eine nichttriviale Funktion approximiert. Das Problem einen Graphen zu färben zählt damit zu den schwersten NP-Problemen überhaupt.
zu Def
Gerichtete Graphen und solche mit Mehrfachkanten sind nicht Gegenstand der Betrachtungen, da es nicht auf die Richtung der Kanten bzw. ihrer Vielfachheit ankommt.
Galaxy07 23:13, 21. Feb 2004 (CET)
>>Der Vier-Farbensatz besagt, dass die chromatische Zahl eines planaren Graphen höchstens 4 ist.<< Stimmt das wirklich so? in meinem diskrete strukturen buch steht, dass die Chromatische Zahl x(g) ist die minimale Anzahl Farben die für eine Knotenfärbung von G benötigt werden. minimal und höchstens wiederspricht sich irgendwie :/ ---> Hat sich erledigt. Ich hab gerade rausgefunden dass das höchstens 4 für planare Graphen gilt.
