Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 24/kontrolle

Aus Wikiversity



Färbungen

Beispiel  Referenznummer erstellen

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 Ausschließungsgraphen visualisiert. Eine Aufteilung in Teams, die diese Abneigungen berücksichtigt, ist eine Abbildung der Knotenpunkte (der Personen) in eine Teammenge mit der Eigenschaft, dass durch eine Abneigungskante verbundene Knotenpunkte auf unterschiedliche Teams abgebildet werden.



Definition  Referenznummer erstellen

Es sei ein Graph. Eine Abbildung

in eine Menge heißt Färbung des Graphen.

Bei denke man an Färbung und bei an bunt. Den Wert nennt man die Farbe von unter der gegebenen Färbung. Es ist keine Einschränkung, nur Farbenmengen der Form zu betrachten.

Diese Definition nimmt keinen Bezug auf die Kantenmenge . Dies wird hingegen bei der folgenden Definition entscheidend verlangt.


Definition  Referenznummer erstellen

Es sei ein Graph. Eine Färbung

heißt zulässig, wenn benachbarte Knotenpunkte stets eine verschiedene Farbe bekommen.


Definition  Referenznummer erstellen

Zu einem Graphen nennt man die minimale Anzahl an Farben, die man für eine zulässige Färbung benötigt, die chromatische Zahl des Graphen. Sie wird mit bezeichnet.



Lemma Referenznummer erstellen

Für die chromatische Zahl eines Graphen gelten die folgenden Aussagen.

  1. Ein Graph ist genau dann nicht leer, wenn seine chromatische Zahl ist.
  2. Ein nichtleerer Graph besitzt genau dann die chromatische Zahl , wenn er keine Kanten besitzt.
  3. Ein Graph ist genau dann bipartit, wenn seine chromatische Zahl ist.
  4. Es ist
  5. Der vollständige Graph besitzt die chromatische Zahl .

Beweis

Siehe Aufgabe 24.6.



Das chromatische Polynom

Definition  Referenznummer erstellen

Zu einem Graphen versteht man unter dem chromatischen Polynom die Funktion, die durch

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.


Beispiel  Referenznummer erstellen

Es sei ein Graph mit Knotenpunkten und ohne Kanten. Dann ist das chromatische Polynom gleich . Es ist ja in diesem Fall jede Abbildung

eine zulässige Färbung und somit gibt es nach Satz 2.2 zulässige Färbungen mit (höchstens) Farben.



Beispiel  Beispiel 24.8 ändern

Es sei ein vollständiger Graph mit Knotenpunkten. Dann ist das chromatische Polynom gleich

Bei Farben gibt es keine zulässige Färbung des vollständigen Graphen. Bei sind nur die injektiven Abbildungen

zulässige Färbungen. Davon gibt es nach Lemma 2.8 Stück.




Lemma  Lemma 24.9 ändern

Es sei ein Graph und sein chromatisches Polynom.

Dann ist die Anzahl der zulässigen Färbungen von mit genau Farben gleich

Beweis  

Wir betrachten zulässige Färbungen von mit der Farbenmenge . Die in Frage stehende Menge der zulässigen Färbungen mit genau Farben sind dabei die surjektiven Abbildungen. Zu sei die Menge der zulässigen Färbungen in , die nicht treffen. Zu einer Teilmenge ist die Menge der zulässigen Färbungen, die nur Farben aus verwenden. Mit der Siebformel ist

der Übergang zum Komplement ergibt die Behauptung.


Diese drei nichtisomorphen Graphen haben jeweils das chromatische Polynom .



Lemma  Lemma 24.10 ändern

Für das chromatische Polynom gelten die folgenden Aussagen.

  1. Die chromatische Zahl von ist die minimale Zahl mit
  2. Mit gelten die Abschätzungen
  3. Für ist

    Insbesondere ist das chromatische Polynom durch die Werte festgelegt.

Beweis  

(1) ist klar. (2). Die rechte Abschätzung ist klar, da rechts die Anzahl der Färbungen mit Farben überhaupt ohne Zulässigkeitsbedingung steht. Die linke Seite ist klar für . Für . ist die Zahl links nach Lemma 2.8 die Anzahl der injektiven Abbildungen von nach , und diese sind stets zulässig. (3). Eine zulässige Färbung mit (höchstens) Farben ist eine zulässige Färbung mit genau Farben für ein . Es sei die Anzahl der zulässigen Färbungen mit genau Farben. Dann ist die Anzahl der zulässigen Färbungen mit Farben unter Verwendung von Lemma 24.9 gleich



Korollar  Referenznummer erstellen

Das chromatische Polynom zu einem Graphen mit Knotenpunkten

ist ein normiertes Polynom vom Grad .

Beweis  

Nach Lemma 24.10  (3) hat die Funktion für die Form

mit

Diese Ausdrücke sind Polynome in vom Grad , wobei der Grad nur für vorkommt. Jedenfalls ist ein Polynom vom Grad . Nach Lemma 24.10  (2) ist der Limes von für gleich , also muss der Leitkoeffizient des Polynoms gleich sein.



Lemma  Lemma 24.12 ändern

Für das chromatische Polynom

gelten die folgenden Eigenschaften.

  1. Es sei eine Kante von mit dem zugehörigen Kontraktionsgraphen . Dann gilt
  2. Bei einer disjunkten Vereinigung von zwei Graphen ist

Beweis  

(1). Sei . Wir zeigen

indem wir die zulässigen Färbungen analysieren. Eine zulässige Färbung von ist eine zulässige Färbung von , bei der auch die Bedingung erfüllt ist. Somit müssen wir zeigen, dass die zulässigen Färbungen von mit den zulässigen Färbungen von entsprechen. Über den surjektiven schwachen Graphhomomorphismus

erhält man aus einer zulässigen Färbung von direkt eine (nichtzulässige) Färbung von mit identischem Wert auf und und damit direkt eine zulässige Färbung auf mit identischem Wert auf und . Diese Gesamtzuordnung ist injektiv. Wenn umgekehrt eine zulässige Färbung

mit gegeben ist, so kann man dies direkt als eine Färbung auf auffassen. Wenn eine Kante von ist, so liegt dieser Kante eine Kante in zugrunde, und daher überträgt sich die Zulässigkeit.

(2). Eine zulässige Färbung auf mit Farben besteht einfach aus einer zulässigen Färbung von und einer zulässigen Färbung von , es gibt darüber hinaus keine weitere Bedingung, da es ja keine Kanten zwischen und gibt. Die Anzahl der zulässigen Gesamtfärbungen ist daher das Produkt der Anzahlen der einzelnen zulässigen Färbungen.