Stiergraph/Charakteristisches Polynom/Chromatisches Polynom/Aufgabe/Lösung

Wir nummerieren die Knotenpunkte von links nach rechts und von oben nach unten. Die Adjazenzmatrix ist
${\begin{pmatrix}0&0&1&0&0\\0&0&0&1&0\\1&0&0&1&1\\0&1&1&0&1\\0&0&1&1&0\end{pmatrix}}.$

Das charakteristische Polynom ist die Determinante von

${\begin{pmatrix}X&0&-1&0&0\\0&X&0&-1&0\\-1&0&X&-1&-1\\0&-1&-1&X&-1\\0&0&-1&-1&X\end{pmatrix}}.$

Wir entwickelen nach der ersten Spalte und erhalten

${}{\begin{aligned}\chi _{}&=X\cdot \det {\begin{pmatrix}X&0&-1&0\\0&X&-1&-1\\-1&-1&X&-1\\0&-1&-1&X\end{pmatrix}}-\det {\begin{pmatrix}0&-1&0&0\\X&0&-1&0\\-1&-1&X&-1\\0&-1&-1&X\end{pmatrix}}\\&=X^{2}\cdot \det {\begin{pmatrix}X&-1&-1\\-1&X&-1\\-1&-1&X\end{pmatrix}}-X\det {\begin{pmatrix}0&-1&0\\X&-1&-1\\-1&-1&X\end{pmatrix}}+X\det {\begin{pmatrix}-1&0&0\\-1&X&-1\\-1&-1&X\end{pmatrix}}+\det {\begin{pmatrix}-1&0&0\\0&-1&0\\-1&-1&X\end{pmatrix}}\\&=X^{2}\cdot \det {\begin{pmatrix}X&-1&-1\\-1&X&-1\\-1&-1&X\end{pmatrix}}+2X\det {\begin{pmatrix}-1&0&0\\-1&X&-1\\-1&-1&X\end{pmatrix}}+\det {\begin{pmatrix}-1&0&0\\0&-1&0\\-1&-1&X\end{pmatrix}}\\&=X^{2}{\left(X(X^{2}-1)+(-X-1)-(1+X)\right)}-2X(X^{2}-1)+X\\&=X{\left(X{\left(X(X^{2}-1)-2X-2\right)}-2(X^{2}-1)+1\right)}\\&=X{\left(X^{4}-5X^{2}-2X+3\right)}\end{aligned}}$
Eine zulässige Färbung ist insbesondere eine Färbung des Stierkopfes. Dieser ist ein vollständiger Graph mit drei Knotenpunkten und sein chromatisches Polynom ist ${}X(X-1)(X-2)$ . Jede zulässige Färbung kann man auf den ganzen Stier zulässig ausdehnen, wobei für die Hörner jeweils nur die Farbe der anliegenden Schläfe ausgeschlossen ist. Deshalb ist das chromatische Polynom gleich
${}X(X-1)(X-2)(X-1)^{2}=X(X-1)^{3}(X-2)\,.$

This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.