Chromatische Zahl - LinkFang.de





Chromatische Zahl


Die chromatische Zahl [math]\chi(G)[/math] (auch Knotenfärbungszahl oder kurz Färbungszahl, selten auch Farbzahl genannt) eines Graphen ist die kleinste Zahl [math]k[/math], für die der Graph eine zulässige Knotenfärbung mit [math]k[/math] Farben besitzt. (Eine Färbung heißt zulässig oder gültig, wenn es keine benachbarten Knoten gibt, die mit der gleichen Farbe gefärbt sind.) Die chromatische Zahl ist zugleich die kleinste natürliche Zahl λ, für die das chromatische Polynom [math]\chi(G,\lambda)\neq 0[/math] ist.

Die achromatische Zahl [math]\psi (G)[/math] eines Graphen [math]G[/math] ist die größte Zahl [math]k[/math], für die [math]G[/math] eine gültige und vollständige Knotenfärbung mit [math]k[/math] Farben hat. (Eine Färbung heißt vollständig, wenn es zu jedem Paar von verschiedenen Farben eine Kante gibt, deren Endknoten mit diesen beiden Farben gefärbt sind.)

Die pseudo-achromatische Zahl [math]\psi_s (G)[/math] eines Graphen [math]G[/math] ist die größte Zahl [math]k[/math], für die [math]G[/math] eine vollständige Knotenfärbung hat. Im Gegensatz zur achromatischen Zahl ist hier nicht die Gültigkeit der Färbung verlangt.

Siehe auch


Kategorien: Graphentheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Chromatische Zahl (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.