Chromatisches Polynom
Das chromatische Polynom <math>\chi(G, \lambda)</math> gibt zu einem Graphen <math>G</math> die Anzahl der möglichen Knotenfärbungen mit <math>\lambda</math> Farben an, d. h. die Anzahl der Färbungen aller Knoten des Graphen, so dass Knoten, die durch eine Kante verbunden sind, verschiedene Farben tragen.
Beispiele[Bearbeiten]
Das chromatische Polynom eines Graphen mit <math>n</math> isolierten Knoten ist <math>\chi(G, \lambda)=\lambda^n</math>. Jeder der <math>n</math> Knoten kann unabhängig von den anderen eine der <math>\lambda</math> Farben annehmen.
Das chromatische Polynom eines vollständigen Graphen <math>K_n</math> ist
- <math>\chi(K_n, \lambda) = \prod_{i=0}^{n-1} (\lambda-i) = \lambda(\lambda-1)\cdots(\lambda-n+1)</math>
Die Farbe des ersten Knotens kann immer beliebig gewählt werden und für die Färbung des <math>(i+1)</math>-ten Knotens sind dann noch <math>\lambda-i</math> Farben übrig.
Eigenschaften[Bearbeiten]
Für jeden Graphen gibt es eine Zahl <math>\chi(G)</math>, sodass <math>\chi(G, \lambda) = 0</math> für alle <math>\lambda < \chi(G)</math>. 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 <math>\chi</math> überhaupt ein Polynom in <math>\lambda</math> ist, dies lässt sich jedoch induktiv zeigen, da für alle Kanten <math>e\in E</math> gilt: <math>\chi(G, \lambda)=\chi(G\setminus\{e\}, \lambda) - \chi(G/e, \lambda)</math> (wobei <math>G/e</math> derjenige Graph ist, der durch Kantenkontraktion von e entsteht).
Literatur[Bearbeiten]
- Martin Aigner: Combinatorial theory. Springer, 1979, ISBN 0-387-90376-3.
- M. Swamy, K. Thulasiraman: Graphs, Networks and Algorithms. Krieger Pub., 1980, ISBN 0-471-03503-3.
- William Thomas Tutte: Graph Theory. Addison-Wesley, 1984, ISBN 0-201-13520-5.
- Herbert Wilf: Algorithms and Complexity. Prentice-Hall, 1986, ISBN 0-13-022054-X.
- R. Graham, M. Grötschel , L. László (Hrsg.): Handbook of Combinatorics. Vol. 1, Elsevier, 1995, ISBN 0-262-07170-3.
Weblinks[Bearbeiten]
- Eric W. Weisstein: Chromatic Polynomial. In: MathWorld (englisch).