Satz von Brooks

Satz von Brooks

Der Satz von Brooks gibt ein Obergrenze für die Anzahl der Farben an, die benötigt werden, um allen Knoten eines Graphen so zu färben, dass keine zwei benachbarten Knoten dieselbe Farbe haben. Der Satz lautet: Die Knotenfärbungszahl eines zusammenhängenden Graphen, der weder vollständig noch ein Kreis ungerader Länge ist, ist höchstens so hoch wie der Maximalgrad des Graphen.

Literatur

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Färbung von Graphen — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

  • Liste von Physikern — Die Liste von Physikern ist alphabetisch sortiert und enthält nur Forscher, die wesentliche Beiträge zum Fachgebiet geleistet haben. Die Liste soll neben den Lebensdaten das Fachgebiet des Forschers nennen und wenige Stichworte zu den Aspekten… …   Deutsch Wikipedia

  • Mel Brooks’ Spaceballs — Filmdaten Deutscher Titel Mel Brooks’ Spaceballs Videotitel: Spaceballs Mel Brooks’ verrückte Raumfahrt Originaltitel Spaceballs …   Deutsch Wikipedia

  • Peter Alexander von Ustinow — Peter Ustinov (1992) Sir Peter Alexander Baron von Ustinov CBE (* 16. April 1921 in Swiss Cottage, Camden, London; † 28. März 2004 in Genolier, Kanton Waadt, Schweiz) war einer der int …   Deutsch Wikipedia

  • Bipartition (Graphentheorie) — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

  • Eindeutig k-färbbarer Graph — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

  • Färbungsproblem — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

  • Graphenfärbung — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

  • Graphfärbung — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

  • Gültige Färbung — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”