Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 24/latex
\setcounter{section}{24}
\zwischenueberschrift{Färbungen}
\inputbeispiel{}
{
In einer Firma arbeiten verschiedene Personen, von denen manche sich gegenseitig nicht leiden können und daher nicht in einem Team arbeiten sollen. Diese Abneigungen werden durch einen \definitionsverweis {Ausschließungsgraphen}{}{} visualisiert. Eine Aufteilung in Teams, die diese Abneigungen berücksichtigt, ist eine Abbildung der Knotenpunkte \zusatzklammer {der Personen} {} {} in eine Teammenge mit der Eigenschaft, dass durch eine Abneigungskante verbundene Knotenpunkte auf unterschiedliche Teams abgebildet werden.
}
\inputdefinition
{}
{
Es sei
\mathl{(V,E)}{} ein
\definitionsverweis {Graph}{}{.}
Eine Abbildung
\maabbdisp {f} {V} {B
} {}
in eine Menge $B$ heißt
\definitionswort {Färbung}{}
des Graphen.
}
Bei $f$ denke man an Färbung und bei $B$ an bunt. Den Wert
\mathl{f(v)}{} nennt man die Farbe von $v$ unter der gegebenen Färbung. Es ist keine Einschränkung, nur Farbenmengen der Form
\mathl{\{1 , \ldots , k\}}{} zu betrachten.
Diese Definition nimmt keinen Bezug auf die Kantenmenge $E$. Dies wird hingegen bei der folgenden Definition entscheidend verlangt.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Petersen graph 3-coloring.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Petersen graph 3-coloring.svg } {} {Chris-martin} {Commons} {gemeinfrei} {}
\inputdefinition
{}
{
Es sei
\mathl{(V,E)}{} ein
\definitionsverweis {Graph}{}{.}
Eine
\definitionsverweis {Färbung}{}{}
\maabbdisp {f} {V} {B
} {}
heißt
\definitionswort {zulässig}{,}
wenn benachbarte Knotenpunkte stets eine verschiedene Farbe bekommen.
}
\inputdefinition
{}
{
Zu einem
\definitionsverweis {Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
nennt man die minimale Anzahl an Farben, die man für eine
\definitionsverweis {zulässige Färbung}{}{}
benötigt, die
\definitionswort {chromatische Zahl}{}
des Graphen. Sie wird mit $\chi(G)$ bezeichnet.
}
{Graph/Färbung/Einfache Eigenschaften/Fakt}
{Lemma}
{}
{
\faktsituation {Für die
\definitionsverweis {chromatische Zahl}{}{}
$\chi(G)$ eines
\definitionsverweis {Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}}
\faktuebergang {gelten die folgenden Aussagen.}
\faktfolgerung {\aufzaehlungfuenf{Ein Graph ist genau dann nicht leer, wenn seine chromatische Zahl $\geq 1$ ist.
}{Ein nichtleerer Graph besitzt genau dann die chromatische Zahl $1$, wenn er keine Kanten besitzt.
}{Ein Graph ist genau dann
\definitionsverweis {bipartit}{}{,}
wenn seine chromatische Zahl $\leq 2$ ist.
}{Es ist
\mavergleichskettedisp
{\vergleichskette
{ \chi(G)
}
{ \leq} { { \# \left( V \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{Der
\definitionsverweis {vollständige Graph}{}{}
$K_n$ besitzt die chromatische Zahl $n$.
}}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 24.6. }
\zwischenueberschrift{Das chromatische Polynom}
\inputdefinition
{}
{
Zu einem
\definitionsverweis {Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
versteht man unter dem
\definitionswort {chromatischen Polynom}{}
\mathl{P_{ G }}{} die Funktion, die durch
\mavergleichskettedisp
{\vergleichskette
{ P_{ G } \left( k \right)
}
{ =} { { \# { \left\{ f:V \rightarrow \{ 1 , \ldots , k \} \mid f \text{ zulässige Färbung} \right\} } }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gegeben ist.
}
Wir werden sehen, dass diese Funktion in der Tat ein Polynom ist, von daher wäre es korrekter, vorläufig von der chromatischen Funktion zu sprechen. Wenn man eine zulässige Färbung mit einer Permutation auf der Farbenmenge verknüpft, so erhält man wieder eine zulässige Färbung. Färbungen, die durch einen solchen Farbenwechsel auseinander hervorgehen, haben zwar die gleichen Eigenschaften, sie werden aber als verschiedene Färbungen gezählt, da ja eine Färbung als eine Abbildung definiert ist.
\inputbeispiel{}
{
Es sei $G$ ein Graph mit $n$ Knotenpunkten und ohne Kanten. Dann ist das \definitionsverweis {chromatische Polynom}{}{} gleich $X^n$. Es ist ja in diesem Fall jede Abbildung \maabbdisp {f} {V} { \{ 1 , \ldots , k \} } {} eine \definitionsverweis {zulässige Färbung}{}{} und somit gibt es nach Satz 2.2 $k^n$ zulässige Färbungen mit \zusatzklammer {höchstens} {} {} $k$ Farben.
}
\inputbeispiel{}
{
Es sei $G$ ein
\definitionsverweis {vollständiger Graph}{}{}
mit $n$ Knotenpunkten. Dann ist das
\definitionsverweis {chromatische Polynom}{}{}
gleich
\mathdisp {X(X-1)(X-2) \cdots (X-n+1)} { . }
Bei
\mavergleichskette
{\vergleichskette
{k
}
{ \leq }{n-1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
Farben gibt es keine zulässige Färbung des vollständigen Graphen. Bei
\mavergleichskette
{\vergleichskette
{k
}
{ \geq }{n-1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sind nur die injektiven Abbildungen
\maabbdisp {f} {V} { \{ 1 , \ldots , k \}
} {}
zulässige Färbungen. Davon gibt es
nach Lemma 2.8
\mathl{k(k-1)(k-2) \cdots (k-n+1)}{} Stück.
}
\inputfaktbeweis
{Chromatisches Polynom/Genau k Farben/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $G$ ein
\definitionsverweis {Graph}{}{}
und $P_{ G }$ sein
\definitionsverweis {chromatisches Polynom}{}{.}}
\faktfolgerung {Dann ist die Anzahl der
\definitionsverweis {zulässigen Färbungen}{}{}
von $G$ mit genau $k$ Farben gleich
\mathdisp {\sum_{j = 0}^k (-1)^j \binom { k } { j } P_{ G } \left( k-j \right)} { . }
}
\faktzusatz {}
\faktzusatz {}
}
{
Wir betrachten zulässige Färbungen von $G$ mit der Farbenmenge
\mathl{\{1 , \ldots ,k \}}{.} Die in Frage stehende Menge der zulässigen Färbungen mit genau $k$ Farben sind dabei die surjektiven Abbildungen. Zu
\mavergleichskette
{\vergleichskette
{ \ell
}
{ \in }{ \{ 1 , \ldots ,k \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sei $F_\ell$ die Menge der zulässigen Färbungen in
\mathl{\{ 1 , \ldots ,k \}}{,} die $\ell$ nicht treffen. Zu einer Teilmenge
\mavergleichskette
{\vergleichskette
{J
}
{ \subseteq }{\{ 1 , \ldots ,k \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mathl{\bigcap_{\ell \in J} F_\ell}{} die Menge der zulässigen Färbungen, die nur Farben aus
\mathl{\{ 1 , \ldots ,k \} \setminus J}{} verwenden. Mit
der Siebformel
ist
\mavergleichskettedisp
{\vergleichskette
{ { \# \left( \bigcup_{\ell = 1}^k F_\ell \right) }
}
{ =} { \sum_{j = 1 }^k (-1)^{j +1} \binom { k } { j } P_{ G } \left( k-j \right)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
der Übergang zum Komplement ergibt die Behauptung.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Chromatically equivalent graphs.svg} }
\end{center}
\bildtext {Diese drei nichtisomorphen Graphen haben jeweils das chromatische Polynom $(x-2)(x-1)^3x$.} }
\bildlizenz { Chromatically equivalent graphs.svg } {} {Koko90} {Commons} {CC-by-sa 3.0} {}
\inputfaktbeweis
{Chromatisches Polynom/Erste Eigenschaften/Fakt}
{Lemma}
{}
{
\faktsituation {Für das
\definitionsverweis {chromatische Polynom}{}{}}
\faktuebergang {gelten die folgenden Aussagen.}
\faktfolgerung {\aufzaehlungdrei{Die
\definitionsverweis {chromatische Zahl}{}{}
von $G$ ist die minimale Zahl
\mavergleichskette
{\vergleichskette
{k
}
{ \geq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskettedisp
{\vergleichskette
{ P_{ G } \left( k \right)
}
{ \geq} {1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{Mit
\mavergleichskette
{\vergleichskette
{n
}
{ = }{ { \# \left( V \right) }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gelten die Abschätzungen
\mavergleichskettedisp
{\vergleichskette
{ k(k-1) \cdots (k-n+1)
}
{ \leq} {P_{ G } \left( k \right)
}
{ \leq} { k^n
}
{ } {
}
{ } {
}
}
{}{}{.}
}{Für
\mavergleichskette
{\vergleichskette
{k
}
{ \geq }{ { \# \left( V \right) } +1
}
{ = }{ n+1
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{ P_{ G } \left( k \right)
}
{ =} { \sum_{ j = 0}^n { \left( \sum_{\ell = j}^n (-1)^{\ell -j} \binom { k } { \ell } \binom { \ell } { j } \right) } P_{ G } \left( j \right)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Insbesondere ist das chromatische Polynom durch die Werte
\mathl{P_{ G } \left( 0 \right) ,P_{ G } \left( 1 \right) , \ldots , P_{ G } \left( n \right)}{} festgelegt.
}}
\faktzusatz {}
\faktzusatz {}
}
{
(1) ist klar. (2). Die rechte Abschätzung ist klar, da rechts die Anzahl der Färbungen mit $k$ Farben überhaupt ohne Zulässigkeitsbedingung steht. Die linke Seite ist klar für
\mavergleichskette
{\vergleichskette
{k
}
{ \leq }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Für
\mavergleichskette
{\vergleichskette
{k
}
{ \geq }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
ist die Zahl links
nach Lemma 2.8
die Anzahl der injektiven Abbildungen von $G$ nach
\mathl{\{1 , \ldots , k\}}{,} und diese sind stets zulässig.
(3). Eine zulässige Färbung mit
\zusatzklammer {höchstens} {} {}
\mavergleichskette
{\vergleichskette
{k
}
{ \geq }{n+1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
Farben ist eine zulässige Färbung mit genau $\ell$ Farben für ein
\mavergleichskette
{\vergleichskette
{ \ell
}
{ = }{ 0,1 , \ldots , n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Es sei $Q(\ell)$ die Anzahl der zulässigen Färbungen mit genau $\ell$ Farben. Dann ist die Anzahl der zulässigen Färbungen mit $k$ Farben unter Verwendung von
Lemma 24.9
gleich
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{ \sum_{ \ell = 0}^n \binom { k } { \ell } Q(\ell)
}
{ =} { \sum_{ \ell = 0}^n \binom { k } { \ell } { \left( \sum_{j = 0}^\ell (-1)^j \binom { \ell } { j } P_{ G } \left( \ell -j \right) \right) }
}
{ =} { \sum_{ \ell = 0}^n \binom { k } { \ell } { \left( \sum_{j = 0}^\ell (-1)^{\ell -j} \binom { \ell } { j } P_{ G } \left( j \right) \right) }
}
{ =} { \sum_{ j = 0}^n { \left( \sum_{\ell = j}^n (-1)^{\ell -j} \binom { k } { \ell } \binom { \ell } { j } \right) } P_{ G } \left( j \right)
}
{ } {
}
}
{}
{}{.}
\inputfaktbeweis
{Chromatisches Polynom/Polynom/Fakt}
{Korollar}
{}
{
\faktsituation {Das
\definitionsverweis {chromatische Polynom}{}{}
$P_{ G }$ zu einem
\definitionsverweis {Graphen}{}{}
mit $n$ Knotenpunkten}
\faktfolgerung {ist ein normiertes Polynom vom Grad $n$.}
\faktzusatz {}
\faktzusatz {}
}
{
Nach
Lemma 24.10 (3)
hat die Funktion für
\mavergleichskette
{\vergleichskette
{k
}
{ \geq }{n+1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Form
\mavergleichskettedisp
{\vergleichskette
{ P_{ G } \left( k \right)
}
{ =} { \sum_{j = 0}^n R_j P_{ G } \left( j \right)
}
{ } {}
{ } {}
{ } {}
}
{}{}{}
mit
\mavergleichskettedisp
{\vergleichskette
{ R_j
}
{ =} { \sum_{\ell = j}^n (-1)^{\ell -j} \binom { k } { \ell } \binom { \ell } { j }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Diese Ausdrücke sind Polynome in $k$ vom Grad $\leq n$, wobei der Grad $n$ nur für
\mavergleichskette
{\vergleichskette
{\ell
}
{ = }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
vorkommt. Jedenfalls ist $P_{ G } \left( k \right)$ ein Polynom vom Grad $\leq n$. Nach
Lemma 24.10 (2)
ist der Limes von
\mathl{{ \frac{ P_{ G } \left( k \right) }{ k^n } }}{} für $k \rightarrow \infty$ gleich $1$, also muss der Leitkoeffizient des Polynoms gleich $1$ sein.
\inputfaktbeweis
{Chromatisches Polynom/Konstruktionen/Fakt}
{Lemma}
{}
{
\faktsituation {Für das
\definitionsverweis {chromatische Polynom}{}{}}
\faktfolgerung {gelten die folgenden Eigenschaften.
\aufzaehlungzwei {Es sei
\mavergleichskette
{\vergleichskette
{e
}
{ \in }{E
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Kante von $G$ mit dem zugehörigen
\definitionsverweis {Kontraktionsgraphen}{}{}
$G/e$. Dann gilt
\mavergleichskettedisp
{\vergleichskette
{ P_{ G }
}
{ =} { P_{ G \setminus \{e\} } - P_{ G /e }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
} {Bei einer disjunkten Vereinigung von zwei Graphen
\mavergleichskette
{\vergleichskette
{G
}
{ = }{ G_1 \uplus G_2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{ P_{ G }
}
{ =} { P_{ G_1 } \cdot P_{ G_2 }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}}
\faktzusatz {}
\faktzusatz {}
}
{
(1). Sei
\mavergleichskette
{\vergleichskette
{e
}
{ = }{\{u,v\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wir zeigen
\mavergleichskettedisp
{\vergleichskette
{ P_{ G \setminus \{e\} }
}
{ =} { P_{ G } + P_{ G /e }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
indem wir die
\definitionsverweis {zulässigen Färbungen}{}{}
analysieren. Eine zulässige Färbung von $G$ ist eine zulässige Färbung $f$ von
\mathl{G \setminus \{e\}}{,} bei der auch die Bedingung
\mavergleichskette
{\vergleichskette
{f(u)
}
{ \neq }{f(v)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
erfüllt ist. Somit müssen wir zeigen, dass die zulässigen Färbungen von
\mathl{G \setminus \{e\}}{} mit
\mavergleichskette
{\vergleichskette
{f(u)
}
{ = }{f(v)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
den zulässigen Färbungen von $G/e$ entsprechen. Über den surjektiven
\definitionsverweis {schwachen Graphhomomorphismus}{}{}
\maabbdisp {\varphi} {G} { G/e
} {}
erhält man aus einer zulässigen Färbung $f$ von $G/e$ direkt eine
\zusatzklammer {nichtzulässige} {} {}
Färbung $f \circ \varphi$ von $G$ mit identischem Wert auf
\mathkor {} {u} {und} {v} {}
und damit direkt eine zulässige Färbung auf $G \setminus \{e\}$ mit identischem Wert auf
\mathkor {} {u} {und} {v} {.}
Diese Gesamtzuordnung ist injektiv. Wenn umgekehrt eine zulässige Färbung
\maabbdisp {g} {G \setminus \{e\}} {B
} {}
mit
\mavergleichskette
{\vergleichskette
{g(u)
}
{ = }{g(v)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gegeben ist, so kann man dies direkt als eine Färbung auf $G/e$ auffassen. Wenn $d$ eine Kante von $G/e$ ist, so liegt dieser Kante eine Kante $d'$ in $G$ zugrunde, und daher überträgt sich die Zulässigkeit.
(2). Eine zulässige Färbung auf
\mathl{G_1 \uplus G_2}{} mit $k$ Farben besteht einfach aus einer zulässigen Färbung von $G_1$ und einer zulässigen Färbung von $G_2$, es gibt darüber hinaus keine weitere Bedingung, da es ja keine Kanten zwischen
\mathkor {} {G_1} {und} {G_2} {}
gibt. Die Anzahl der zulässigen Gesamtfärbungen ist daher das Produkt der Anzahlen der einzelnen zulässigen Färbungen.