Diskussion:Färbung (Graphentheorie)

Generische Überschrift

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)

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={V₁,...,V_k} eine Partition von V, so dass für jedes i aus {1,...,k} gilt, dass je zwei beliebige verschiedene Knoten v und w von V_i 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={V₁,...,V_k} 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={V₁,...,V_k} eine Partition von G und ist für jedes i jeder Knoten aus V_i mit jedem Knoten aus V\V_i 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.

Dead Link

Der Weblink auf das "GF-Graphenfärbungsprogramm" zeigt leider auf eine nicht mehr existierende Subdomain. Weiß irgendwer wo die Seite hin umgezogen ist? --Pamtrs 14:03, 6. Okt. 2008 (CEST)

Hallo. Die Seite wurde von mir unterhalten und ich werde sie wieder aufsetzen - dann hier melden. Leider kann ich als neuer Benutzer auch den Link zu der Dipl.-Arbeit aktal.; es wäre http://homepage.univie.ac.at/alessandro.tomazic/docs/Diplomarbeit.pdf . Gruß, A. Tomazic.

Aufteilung des Artikels

Hallo Leute, ich würde den Artikel gerne aufteilen in Kantenfärbung, Knotenfärbung und dann noch einen neuen Artikel zu Listanfärbungen anlegen. Dies alles in einen Artikel zu pressen scheint mir n bisschen erzwungen und unübersichtlich. Gibts Meinungen? LG --NikelsenH (Diskussion) 17:57, 10. Aug. 2013 (CEST)

Ich kann mir zu Kanten- und Listenfärbungen eigenständige Artikel gut vorstellen. Unter dem Lemma Färbung (Graphentheorie) würde ich aber weiterhin in erster Linie Knotenfärbungen behandeln, weil das anscheinend auch in der Literatur der mit Abstand am häufigsten betrachtete Gegenstand zu sein scheint, wenn es um Färbungen im Kontext der Graphentheorie geht. Siehe auch [1].--goiken 22:19, 10. Aug. 2013 (CEST)

Stimme goiken zu. Man kann ja kurz auf die anderen Begriffe verweisen. Im Moment ist es etwas durcheinander, aber das wird sich ja dann bald legen. Danke für deine Initiative. --Andreschulz (Diskussion) 17:01, 16. Aug. 2013 (CEST)

Alternativ könnte man bei Färbung einen Übersichtsartikel plazieren, welcher die Zusammenhänge und Dualitäten der einzelnen Färbungsbegriffe behandelt und dann in den einzelnen Artikeln tiefergehende Eigenschaften behandeln. Die englische Wiki behandelt noch Flächenfärbungen, ich weiß aber nicht ob das einen Einzelnen Artikel rechtfertigt. Bisher ist dieser Zusammenhang ja gut im Abschnitt Knotenfärbung Planarer Graphen abgehandelt. Hätte da jemand evtl noch eine schöne Quelle? --NikelsenH (Diskussion) 09:09, 18. Aug. 2013 (CEST)

Existiert keine Färbung…

Hallo, beim Lesen des Artikels bin ich über den Satz "Existiert für noch so viele Farben keine Färbung setzt man symbolisch χ ( G ) = ∞" im Abschnitt "Anzahl der Färbungen" gestolpert. Mir kommt das ziemlich trivial vor. Wenn ein Knoten eine Kante zu sich selbst hat, ist der Graph nicht färbbar, ansonsten sollte ein Graph doch immer färbbar sein, wenn die Anzahl der Farben der Anzahl der Knoten entspricht, also jeder Knoten eine andere Farbe hat. Ich denke, dass der Satz schon einen Sinn hat und es deshalb nicht so trivial ist, wie ich denke. Wo ist das Problem? -- 85.212.111.129 00:35, 4. Aug. 2016 (CEST)

Beispiele einbauen

Als Mathe-Interessierter lese ich diese und andere Artikel immer wieder mit Interesse und Aufmerksamkeit.

Allerdings fehlt mir dann manchmel einfach das Verständnis für das was da beschrieben wird.

Es wäre also hilfreich ein überschaubares Beispiel anzuführen, dass den Sachverhalt darstellt.

Wie gesagt eine Anregung.

Danke --Lambdaoe (Diskussion) 09:26, 27. Sep. 2017 (CEST)