Graph/Färbungen/Einführung/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen


Beispiel  

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  

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.

Petersen graph 3-coloring.svg


Definition  

Es sei ein Graph. Eine Färbung

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


Definition  

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

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.