Chromatisches Polynom

Chromatisches Polynom

Das chromatische Polynom χ(G,λ) gibt zu einem Graphen G die Anzahl der möglichen Knotenfärbungen mit λ Farben an, d.h. die Anzahl der Färbung aller Knoten des Graphen, so dass Knoten, die durch eine Kante verbunden sind, verschiedene Farben tragen.

Inhaltsverzeichnis

Beispiele

Das chromatische Polynom eines Graphen mit n isolierten Knoten ist χ(G,λ) = λn. Jeder der n Knoten kann unabhängig von den anderen eine der λ Farben annehmen.

Das chromatische Polynom eines vollständigen Graphen Kn ist

\chi(K_n, \lambda) = \prod_{i=0}^{n-1} (\lambda-i) = \lambda(\lambda-1)\cdots(\lambda-n+1)

Die Farbe des ersten Knotens kann immer beliebig gewählt werden und für die Färbung des (i + 1)-ten Knotens sind dann noch λ − i Farben übrig.

Eigenschaften

Für jeden Graphen gibt es eine Zahl χ(G), sodass χ(G,λ) = 0 für alle λ < χ(G). Diese Zahl ist die chromatische Zahl des Graphen und gibt an, wie viele Farben für eine zulässige Knotenfärbung mindestens benötigt werden.

Es ist zunächst einmal nicht klar, dass χ überhaupt ein Polynom in λ ist, dies lässt sich jedoch induktiv zeigen, da für alle Kanten e\in E gilt: \chi(G, \lambda)=\chi(G\setminus\{e\}, \lambda) - \chi(G/e, \lambda) (wobei G / e derjenige Graph ist, der durch Kantenkontraktion von e entsteht).

Weblinks

Literatur

  • Martin Aigner: Combinatorial theory. Springer, 1979, ISBN 0-387-90376-3
  • Swamy M., Thulasiraman K.: Graphs, Networks and Algorithms. Krieger Pub. Co., 1980, ISBN 0-471-03503-3
  • Tutte W.: Graph Theory. Addison-Wesley, 1984, ISBN 0-201-13520-5
  • Wilf, H. S., "Algorithms and Complexity", Prentice-Hall, 1986
  • Graham R. (Ed.), Grötschel M. (Ed.), László L. (Ed.): Handbook of Combinatorics. Vol. 1, Elsevier, 1995, ISBN 0-262-07170-3

Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

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

  • Primpolynom — In der Algebra, einem Teilgebiet der Mathematik, ist ein irreduzibles Polynom ein Polynom, das sich nicht als Produkt zweier nicht invertierbarer Polynome schreiben lässt und somit nicht in „einfachere“ Polynome zerfällt. Ihre Bedeutung für die… …   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ä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

  • 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

  • Gültige Kantenfä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 Knotenfä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”