date-created: 2024-06-10 10:36:56 date-modified: 2024-06-27 04:53:44

Knotenfärbung (bei Graphen)

anchored to 115.00_graphentheorie_anchor #computerscience #graphtheory

Euphorisch als eines der größten Probleme in der Informatik betitelt möchten wir das Einfärben von Graphen betrachten. ( Als wichtiger Punkt dient hier etwa die Frage um die Einfärbung eines Graphen mit 4 Farben, wenn er planar ist.)

Der Beweis ist aber unschön, weil wir da mit Computern lösen, bzw wir uns auf diesen verlassen müssen (und dabei eventuelle Rundungsfehler das Ergebnis verfälschen o.ä.)

Dennoch werden wir uns etwa für die EInfärbung mit 5-Farben einen Beweis anschauen, der soweit auch funktioniert und umsetzbar ist.

Overview

Wir wollen zuerst die Knotenfärbung grundlegend definieren: Haben wir zuvor bereits betrachtet, siehe 115.01_grundlagen

[!Definition] Knotenfärbung

Sei $G=(V,E)$ ein Graph.

Wie können wir die Knotenfärbung dann definieren, welche Bedingung wird dabei gesetzt? Was ist mit der chromatischen Zahl gemeint? #card

Eine Knotenfärbung ist eine Abbildung $$f:V\to M$$ (wobei $M$ Die Farbmenge darstellt., also einfach die verschiedenen Farben )
Wobei diese Abbildung folgend für beliebige Kanten $(u,v)\in E$ implizieren, muss dass $f(u)\ne f(v)$ (Wir also unterschiedliche Farben für zwei benachbarte Knoten haben!).

Chromatische Zahl Die chromatische Zahl $\mathcal{X}(G)$ ist dann die kleinste Zahl von Farben, die eine Knotenfärbung für $G$ ermöglicht! Mann nennt eine Knotenfärbung mit $k$-Farben dann auch eine K-Färbung

Betrachten wir dafür folgenden Graphen. Seine chromatische Färbung wäre dann $\mathcal{X}(G)=4$

Analog können wir auch eine Färbung von Kanten ermöglichen, die das gleiche Konzept verfolgt, dabei aber eben auf die Kanten bezogen ist / wird und nicht auf die Knoten direkt.

Kantenfärbung

[!Definition] Kantenfärbung

Sei wieder $G=(V,E)$ ein Graph.

Wie können wir jetzt eine Kantenfärbung beschreiben / definieren? was gibt der chromatische Index an? #card

Wenn wir eine Abbildung: $$g:E\to M$$ (M ist die Farbmenge) konstruieren können, sodass dann für beliebige $e,f\in E$ ( wenn sie adjazent, also aneinanderliegend sind) nicht die gleiche Farbe haben, also $$g(e)\ne g(f)$$ Dann sprechen wir von einer validen Kantenfärbung.

Dabei beschreibt jetzt der Chromatische Index ${\mathcal{X}}^{\prime }(G)$ die kleinste Zahl von Farben, um die Kantenfärbung des Graphen umsetzen zu können.

Visuell ist es also einfach analog zur Knotenfärbung, aber mit Kanten!

Beispiele:

Folgend einige Beispiele, für die man die chromatische Zahl gut bestimmen kann:

Für die Vollständige Graphen gilt etwa: $K_n⟹\mathcal{X}(K_n=n)$

Für vollständige Graphen der Form $K_{n,m}$ gilt weiter: $\mathcal{X}(K_{n,m})=2$ ( da man einfach die eine Seite und die andere Seite färben kann!)

[!Tip] chromatische Zahl bei Kreisen:

Betrachten wir zwei Kreise, und wollen die chromatische Zahl für sie finden:

Unter welcher Abhängigkeit ist die chromatische Zahl bestimmt/definiert? #card

$$\mathcal{X}(C_n)=\{\begin{array}{ll}?2& \text{ falls n gerade ist}\\ >3& \text{ sonst}\end{array}$$

Kantenfärbung

Haben wir zuvor schon in Kantengraphen betrachtet, jedoch können wir im Bezug auf die Färbung noch eine Aussage tätigen!

[!Important] Kantenfärbung $G==L(G)$

Konstruieren wir einen Kantengraphen $L(G),G=(V,E)$ (also einen solchen, der für jede Kante einen Knoten und für adjazente Kanten eine Kante zu den entsprechenden Knoten hat) dann können wir eine Aussage bezüglich der Färbung dieser Graphen treffen:

Was folgt für die Färbung aus dieser Konstruktion? #card

Da wir die Konstruktion 1-1 konvertieren und somit auch die Abhängigkeiten beibehalten, ist die Knotenfärbung von $G$ gleichbedeutend, wie die Knotenfärbung des Kantengraphen $L(G)$. Visuell etwa:

Den Chromatischen Index für die Kantenfärbung geben wir folgend mit : $${\mathcal{X}}^{\prime }(G)$$ an!

Wir möchten ferner noch den Begriff eine Kantengraphen definieren,

Wir können aus dieser Definition und der Eigenschaft einer Planarität dann eine Folgerung formulieren, die etwas über die Färbbarkeit von planaren Graphen sagen kann.

Lemma (34) | 5-Färbung für planaren Graphen

[!Lemma] Lemma 34

Jeder planare Graph $G=(V,E)$ hat eine 5-Färbung

Wie kann diese Aussage bewiesen werden? #card

Wir wollen diese Aussage folgend beweisen:

Wir wissen, dass ein planarer Graph $G$ einen Knoten mit $\mathrm{deg}(v)\le 5$ aufweist Korollar (13) Knotengrad avg <6

Mit dieser Betrachtung können wir einen Graphen mit dieser Eigenschaft betrachten und bearbeiten. Wir wollen hier dann diesen Knoten $v$ entfernen ( und den Rest betrachten), welcher den Grad aufweist.:

Sei also $deg(v)\le 4$: dann: 0. lösche $v$ aus dem Graphen (wir werden ihn erst am Ende färben, wenn wir alle anderen gefärbt haben, da es einfacher ist, wir weniger Constraints in der Betrachtung haben)

1. Berechne $G^{\prime }=G\setminus \{v\}$ und Berechne rekursiv die 5-Färbung von $G^{\prime }$ (Also die Betrachtung des Graphen ohne den Knoten $v$!)
2. Am Ende wird $v$ die letzte übrige Farbe erhalten. - diese Farbe hat dann keiner der Nachbarn!

Visuell also:

Sei jetzt $\mathrm{deg}(v)=5$ als nächster Fall: (Wir wissen hier, dass die Nachbarn nicht alle paarweise verbunden sein können, sonst wäre es ein $K_5$ und das ist dann nicht mehr planar!)

Also hat $v$ dann 2 Nachbarn, die keine gemeinsame Kante haben (also nicht verbunden sind) Wir gehen wie folgt vor:

1. Lösche $v$ und verschmelze $x,y$ und erzeuge einen neuen Graphen
2. Berechne jetzt die 5-Färbung füý $G^{\prime }$ wieder rekursiv.
3. In $G$ bekommen $x,y$ diesselbe Farbe Dadurch folgt dann, dass anschließend wieder nur eine Farbe für $v$ übrig bleibt!

Visuell sieht dieser Fall folgend aus:

Wir haben so wieder reduziert und können dann rekursiv weiter nach den obigen beiden Fällen agieren, um den Graphen vollständig, richtig zu färben!

Alternativ können wir einen Greedy-Algorithmus betrachten, der genau diese Färbung ebenfalls implementiert:

Algorithmus zur Knotenfärbung

Die Grundlegende Idee: Wir geben den Farben Nummern und iterieren von einem Startpunkt durch den ganzen Graphen:

• Ein neuer Knoten wird gefärbt, indem die Nachbarn angeschaut werden und dabei dann immer die kleinste, noch nicht benutzte Farbe, betrachtet wird.
• Dieser wird anschließend nach und nach durchlaufen und ferner eine valide Färbung erzeugen ( auch wenn sie nicht optimal ist! )

[!Definition] Greed-Algorithmus zur Knotenfärbung

Wie ist der Algorithmus aufgebaut, wie durchläuft er den Graphen, Was ist eine Konsequenz/ein mögliches Problem? Wie viele Farben wird der Algorithmus in Abhängigkeit des Graphen maximal verwenden? #card

Folgend der Algorithmus: Sei hierfür wieder $G=(V,E)$ ein einfacher Graph und ferner $v=\{v_1,v_2,\dots ,v_n\}$ ( eine direkte Nummerierung der Knoten, damit wir damit besser arbeiten können)

Wir iterieren jetzt den Graphen Schritt für Schritt:

1. Färbe $v_1$ mit der Farbe 1 ( Initialfärbung)
2. Wiederhole jetzt folgend $n$ mal - also für jeden Knoten
3. Färbe $v_i$ mit der kleinstmöglichen Farbe (die Farben sind ja nummeriert!) und Berücksichtige dabei die Farben der benachbarten Knoten (also wenn zwei Knoten zu einem neuen führen, dann wird bei dem neuen geschaut, welche Farbe - minimal - noch nicht von den beiden Nachbarn genommen wurde und dann diese eingefärbt)

Problem: Der Algorithmus wird nicht garantiert die beste Färbung finden. Es kann sein, dass er etwa für die $K_{n,m}$ Graphen mehr als 2 Farben benötigt:

Weiterhin können wir hier sehen, dass der Algorithmus höchstens $\Delta (G)+1$ Farben benutzen wird (also den maximalen Grad im Graphen +1)

Wir können also einsehen, dass dieser Algorithmus nicht immer die beste Graphenfärbung bringen wird.

[!Attention] Nicht optimale Lösung

Der Algorithmus wird u.U. nicht die beste Einfärbung finden können. Erkennbar an folgendem Beispiel:

Aber diesen kann man auch besser einfärben, sodass weniger Farben verwendet werden:

siehe Minimale Knotengrade für mehr Informationen zu den Knotengraden!

[!Definition] Der Algorithmus wird dann immer maximal $max(deg(v))+1$ Farben benötigen, weil er eine neue Färbung abhängig von der Menge von Nachbarn bestimmt.

Einfach darzustellen mit einem vollständigen Graphen: Jeder Nachbar hat seine eigene Farbe (was von einem Ausgang gleich $\mathrm{deg}(v)=k$) und weiterhin brauch auch der Knoten $v$ noch eine eigene Farbe! Also $\mathrm{deg}(v)+1$

Satz (35) | Obere Schranke der Farben

[!Satz] Obere Schranke für chromatische Zahl

Wir können die chromatische Zahl folglich oberst beschränken:

Wie kann das beschrieben werden, warum folgt das? #card

Wir beschreiben diese obere Schranke mit $\mathcal{X}(G)\le {\max }_H\delta (H)+1$, wobei $H$ einen induzierten Untergraphen von $G$ beschreibt.

Wir wissen, also dass die Oberschranke der maximal-Grad des Graphen +1 ist!

Beweis Satz (35) Obere Schranke der Farben

Beweisidee: (Wir beweisen das dadurch, dass wir durch den naiven Algorithmus oben zeigen können, dass die Menge von Farben genau $h+1$ ist).

(Die Idee ist also den Graphen Schritt für Schritt zu reduzieren (immer einen Knoten zu entfernen) und dann beim angekommenen Minimal-Graphen die $h$ Farben zu verteilen und dann mit dieser Information die restlichen Knoten einfärben zu können ).

Beweis: Sei jetzt $h={\max }_h\delta (H)$ ( der maximale Minimalgraph aller Untergraphen) Dann gibt es in $G$ einen Knoten mit Grad $\le h$ (denn der Graph ist auch selbst in dem Untergraph und somit muss diese Instanz existieren).

Sei dann $v_n$ so ein entsprechender Knoten, den wir dann (wieder) als letztes Betrachten werden (wir bilden wieder die rekursive Färbung und machen diesen Knoten am Ende, weil es einfacher ist!)

Wir betrachten jetzt also $G\setminus v_n$ (und färben rekursiv den Rest-Graphen gemäß des Algorithmus ein) und ferner sei $H_1$ ein induzierter Untergraph von $G\setminus v_n$.

Dieser hat einen Knoten $v_{n-1}$ von Grad $\le h$

(jetzt argumentieren wir induktiv weiter).

Sei dann $H_2$ wieder ein induzierter Untergraph von $G\setminus \{v,v_{n-1}\}$ (also wir machen den Graphen weiter kleiner und entfernen eine weitere Kante, die wir später einfärben werden). Dieser Graph $H_2$ hat dann einen Knoten $v_{n-2}$ vom Grad $\le h$ Das wiederholen wir jetzt weiter und weiter

Wenn der Greedy Algorithmus dann die Knoten in der Reihenfolge $v_1,v_2,v_n$ bekommt, braucht er dann $\le h+1$ Farben. und dadurch folgt dann $\mathcal{X}(G)\le h+1$ (Aber das ist nur eine Schranke, wir können an Beispielen sehen, dass das nicht immer funktioniert)

Betrachten wir dazu etwa ein Beispiel: Im Beispiel hat das Dreieck einen min-Grad von 2 (und somit dann etnsprechend 2+1 =3 Farben, beim Rest aber nicht. Dadurch können wir nur urteilen, dass die Färbung maximal 2+1 Farben haben (es ist ja eine obere Schranke!).

[!Definition] Induzierter Untergraph

Mit einen induzierten Untergraphen meinen wir eine Teilmenge von Knoten eines Graphen - wobei dann auch die adjazenten Kanten zu den Knoten dazugehören:

Wir wissen, also dass die Oberschranke der maximal-Grad des Graphen +1 ist!

Dafür schauen wir alle Untergraphen (das inkludiert auch den Original-Graphen) Das Maxima aus den minimal-Graden aus den untergraphen

(induzierter Untergraph): #nachtragen

Folgerung aus Satz (35) Obere Schranke der Farben

[!Tip] Folgerung: Wenn $G$ nicht k-regulär ist, dann gilt: $\mathcal{X}(G)\le k=\Delta (G)$ (regulär heißt alle Knoten haben Grad $k$; $K_5$ ist etwa $4$ regulär.)

Anders formuliert also: Wenn er für kein $k$ regulär ist, dann gilt die Aussage!! (Im Normalfall brauchen wir nicht $k+1$ viele Farben, das ist nur bei speziellen Fällen bei $k$-regulären.)

Zusammenhang Clique und Färbung

siehe etwa Example ==Independent set –> clique== oder [[222.16_graph_centrality.md]] oder [3-SAT $preceq$ Clique](theo_Polynomzeit-Reduktion.md#3-SAT%20%20Clique)

[!Definition] Cliquenzahl

Wir wollen die Cliquezahl eines Graphen $G=(V,E)$ beschreiben und definieren.

Wann spricht man von einer Clique, was gibt die Cliquenzahl an? #card

Mit der Cliquen-Zahl beschreiben wir die Anzahl der Knoten innerhalb des größten vollständigen Untergraphen von $G$.

Die Cliquenzahl wird definiert mit $\omega (G)$

Also wenn wir einen Graphen betrachten und dieser in einem Untergraph davon eine vollständige Struktur aufweist, dann gibt die Clique-Zahl an, wie viele Knoten dabei einbezogen werden.

Visuell etwa:

und ferner ist $\omega (G)=4$

ein weiteres Beispiel: mit $\omega (G)=3$:

[!Important] Beobachtung

Man kann in den obigen Beispielen erkennen, dass die chromatische Zahl immer $\ge$ der CLiquenzahl ist. $$\mathcal{X}(G)\ge \omega (G)$$

Hierbei können wir uns dann folgende Frage stellen und diese mit einer Konstruktion zeigen: $$\text{ Haben Graphen mit kleiner Cliquenzahl auch eine niedrige chromatische Zahl??}$$

Konstruktion des Mycielski Graphen

Wir wollen ferner einen Graphen konstruieren: Hierbei sei: $G_3=C_5$ mit $(\mathcal{X})({\mathcal{G}}_3)=3$ und $\omega (G_3)=2$ (was also die Ungleichung einhält).

Wir erhalten den ersten Kreis

Wir erweitern folgend, $G_{n+1}$ wird gebaut mit:

• Zu jedem Knoten $v\in G_n$ erstellen wir einen Knoten $v^{\prime }$ und verbinden ihn mit allen Nachbarn von $v$:

als letzter Schritt:

• Wir fügen am Ende einen neuen Knoten $x$ ein - in die Mitte - und verbinden ihn mit allen $v^{\prime }\in G_{n+1}$

Womit wir hier jetzt resultieren:

[!Attention]

$$\omega (G_{n+1}=2),\mathcal{X}(G_{n+1})=n+1$$ Was also die obige Annahme nicht verletzt!

Satz (37) | von Vizing

[!Definition] Satz 37

Sei ein Graph $G=(V,E)$.

Was folgt jetzt im Bezug auf die Werte der chromatischen Zahl und dem maximalgrad des Graphen? #card

Wir können jetzt den Wert der chromatischen Zahl einschränken: $$\Delta (G)\le {\mathcal{X}}^{\prime }(G)\le \Delta (G)+1$$