date-created: 2024-07-01 10:27:26 date-modified: 2024-07-08 11:44:56

Graphen-Färbung

anchored to 115.00_graphentheorie_anchor proceeds from 115.09_Graphen_Knotenfärbung

Overview

Wir haben uns zuvor schon Knotenfärbung angeschaut

Knotenfärbung (bei Graphen)

Ferner wurde in dieser Struktur auch schon die Kantenfärbung definiert und bearbeitet.

Wir wollen uns jetzt ferner diverse Sätze anschauen, die das Färben besser umsetzen und weiter beschreiben und definieren kann.

Färbung

Satz (45) | Satz von Brooks

[!Definition] Satz von Brooks | 36

Sei $G=(V,E)$ ein zusammenhängender Graph mit $n\ge 2$ Knoten und dem Maximalgrad $\Delta$.

Was können wir über einen normalen Graphen aussagen, was bilden die zwei Ausnahmen (warum) #card

Dann ist jetzt $\mathcal{X}(G)\le \Delta$, außer, wenn $G$ vollständig ist oder ein Kreis mit ungerader Länge $\ge 3$ (weil man dann 3 Farben brauch).

Für diese Ausnahmen gilt folgend: $\mathcal{X}(G)=\Delta +1$

Beweis

Er ist der Kreis!

Für $n=2$ ist die Aussage klar und muss nicht bewiesen werden. Aufgrund von Satz 35 bzw. dessen Folgerung link here können wir folgend annehmen, dass $n\ge 3$ ist.

Aufgrund der Folgerung aus Satz 35 können wir annehme, dass $G=(V,E)$ $\Delta$-regulär ist (also des maximalen Grades innerhalb des Graphen!), denn $\Delta \ge 3$ ( für $\Delta =2$ wäre $G$ ein Kreis) Ferner können wir annehmen, dass $G$ 2-zsh ist!.

–> Wenn es das nicht ist, dann können wir den Graphen in Komponenten $G_1.G_2,\dots$ aufteilen ( die durch eine Menge von Schnittknoten erzeugt wird). Dadurch gilt dann: $G_1\cup \{v\}$ und $G_2\cup \{v\}$ sind nicht $\Delta$-regulär -> insbesondere haben sie Knoten von Grad $<\Delta$ –> und somit brauchen sie selbst höchstens $\Delta$-Farben.

Aus dieser Betrachtung setzen wir dann folgende Annahme:

Annahme: $G$ hat Knoten $u$ der zwei Nachbarn $v_1,v_2$ besitzt –> die nicht adjazent sind!, sodass dann $G\setminus \{v_1,v_2\}$ zusammenhängend ist. Wir wenden den gierigen Algorithmus, den wir mal angesetzt / konzipiert haben, an Link anchtragen.

Setze jetzt $v_1=u$ und $v_{n-1}\in V\setminus \{v_1,v_2,v_n\}$ ist zu $v_n$ benachbart. Es gibt diesen Knoten, weil wir nicht zwingend den Minimalknoten anschauen und er so wahrscheinlich / per Definition noch einen Nachbarn haben sollte.

$v_{n-2}\in V\setminus \{v_1,v_2,v_n,v_{n-1}\}$ ist zu $v_n$ oder $v_{n-1}$ benachbart sind.

Für jedes $3\le i\le n$ existiert dann ein Knoten $v_i\in V\setminus \{v_1,v_2,v_n,v_{n-1},v_{i-1}\}$ der zu mindestens einen Knoten $v_{i+1},\dots v_n$ (also weiterhin der Bereich von rechts nach Links / wir konstruieren von Hinten) benachbart ist, da $G\setminus \{v_1,v_2\}$ zusammenhängend ist ( und wir somit bei Betrachtung der anderen Knoten in dieser Menge eben solchen Nachbar finden können!)

Der Algorithmus startet also mit $v_1$ und gibt $v_1$ und $v_2$ die selbe Farbe –> da $v_1$ und $v_2$ nicht benachbart sind <– und somit braucht der Algo nicht mehr als $\Delta$-Farben, da jeder Knoten zu höchstens $\Delta -1$ Vorgängern benachbart ist und ferner $v_n$ zu $v_1$ und auch $v_2$.

Wir haben die zweite Bedingung gesetzt, dass man beim entfernen eines Knoten weiterhin einen zusammenhängenden beibehält.

Für einen vollständigen Graphen gilt die Aussage natürlich, weswegen wir sie folgend auch nicht betrachten werden / wollen.

Fall 1:

Ist $G$ $3$-zusammenhängend und ferner $G\ne K_n$ (nicht vollständig).

Wir wollen einen Startknoten $u$ auswählen. Da er $3$-zsh ist, und wir einen solchen Startknoten suchen, wo wir anschließend zwei Knoten finden können, die nicht benachbart sind ($v_1,v_2$ wieder), können wir einfach jeden Knoten als Startknoten $u$ wählen –> da es durch die $3$-zsh-Komponente folgt.

Fall 2:

Sei jetzt $G$ $2-zsh$. Ferner sei $x\in V$.

Wenn jetzt $G\setminus x$ auch noch $2-zsh$ ist, dann wäre $v_1=x,$ und der zweite Knoten $v_2$ wird irgendein Knoten mit Abstand 2 zu $x$ sein ( damit wir die Eigenschaft haben, dass sie nicht benachbart sind (und der Algorithmus angewandt werden kann!)) Somit ist dann $u$ der Knoten auf dem Weg zwischen $\underset{x}{\underbrace{v_1}}\to v_2$

Wenn dann jetzt $G\setminus x$ nur noch zusammenhängend ( nicht mehr 2-zsh!) ist, dann wählen wir die Knoten $v_1,v_2$ so, dass sie in unterschiedlichen Schnittkopmonenten liegen.

Dann ist der Graph ohne $v_1,v_2$ weiterhin zusammenhängend!

Clique | Färbung

[!Req] Definition | Clique

Bevor wir die Verbindung zwischen Cliquen und der Färbung bilden, müssen wir sie noch definieren.

Wie definieren wir die Cliquezahl eines Graphen? #card

Betrachten wir folgenden Graphen, so können wir erkennen, dass es einen 4-vollständigen Teilgraphen gibt!

somit ist dann $w(G)=4$

Clique | Färbung

[!Definition]

Was kann mit der Cliquezahl über die Graphenfärbungszahl ${}_{\mathcal{X}}(G)$ ausgesagt werden? Was kann man noch folgern? #card

Wir können mit der Cliquenzahl eine untere Schranke für die Knotenfärbung bilden; $${}_{\mathcal{X}}(G)\ge \omega (G)$$

(Jedoch kann man in die andere Richtung nicht viel aussagen: Also kleine Cliquezahl und somit eine niedrige chromatische Zahl)

Das kann man unter Betrachtung des Graphen von Mycielski zeigen:

In seiner Konstruktion startet dieser mit einem $5$-Kreis, wobei da also ${}_{\mathcal{X}}(G_3)=3$ und ferner $w(G)=2$ ist.

Man kann diesen Graphen jetzt induktiv weiter-ausbauen: $G_{n+1}$ beschreibt dann: Zu jedem Knoten $v$ aus $G_n$ erstellen wir einen Knoten $v^{\prime }$. Dieser Knoten $v^{\prime }$ wird dann mit allen Nachbarn von $v$ verbunden (und nicht mit $v$ selbst!)

Ferner wird noch ein Knoten $x$ eingeführt, welcher mit allen $v^{\prime }$ verbunden wird.

Wir sehen hier, dass sich die Farbe proportional mit der Menge an Knoten verändern wird, jedoch die Cliquezahl immer gleich bleibt, also $w(G_{n+1})=2$

Satz (46) | Kantenfärbung

[!Satz] Vizing | 19646

Betrachten wir einen Graphen $G=(V,E)$.

Was können wir unter Betrachtung des Maximalgrades über die Kantenfärbung aussagen? #card

Es gilt folgend: $$\Delta (G){\le }_{{\mathcal{X}}^{\prime }}(G)\le \Delta (G)+1$$

(Wobei) $\Delta (G)$ der maximal-Grad des Graphen ist!

–> Wir sehen also, dass der maximale-Grad garantiert die Mindestmenge von Farben für eine Kantenfärbung angibt!

Perfekte Graphen

Wir möchten uns noch weitere Graphen mit diversen Eigenschaften anschauen.

[!Definition]

Betrachten wir einen einfachen Graphen $G=(V,E)$.

Wann nennen wir diese Graphen dann perfekt? #card

Wir nennen $G$ jetzt perfekt, wenn gilt:

• alle induzierten Untergraphen $H$ ( also auch $G$ selbst) weißt auf: ${}_{\mathcal{X}}(H)=w(H)$ (Also die Clique-Zahl und Färbungszahl bleibt gleich!)

Betrachten wir ein Beispiel dafür:

[!Tip] kleinster nicht-perfekte Graph

Welcher wäre das? #card

Der $C_5$ ist der kleinste nicht-perfekte Graph:

Denn ${}_{\mathcal{X}}(C_5)=3$ und $w(C_5)=2$

Satz (47) | Lovász

[!Definition] Satz von Lovász (1972)

Wann ist ein einfacher Graph perfekt?

Ein einfacher Graph ist genau dann perfekt, wenn auch sein Komplement perfekt ist!

(Erinnerung): Das Komplement eines Graphen $G=(V,E)$ besteht aus der selben Knotenmenge $V$ und allen Kanten $\overline{E}$, die nicht in G enthalten sind, also $e\in \overline{E}⟺e\notin E$

Beispiel dafür:

Oder auch:

Perfekte Graphen Vermutung

[!Satz] Perfekte Graphen Vermutung (von Berge)

(1961)

Wann wird ein einfacher Graph als perfekt eingestuft? Bezug zu einem Kreis und komplementären Graphen #card

Ein Einfacher Graph ist genau dann perfekt, wenn er weder einen Kreis ungerader Länge $\ge 5$ noch einen dazu komplementären Graphen als induzierten Untergraphen enthält.

(Dieser Satz wurde mit einem Computer beweisen –> Bad! )

Kritische Graphen

[!Definition] Kritischer Graph

wann nennen wir einen Graphen kritisch? #card

Wir nennen einen einfachen Graphen $G=(V,E)$ kritisch, falls ${}_{\mathcal{X}}(G\setminus v){<}_{\mathcal{X}}(G)$ für alle Knoten $v\in V$. (Das heißt also, dass wir jeden Knoten entfernen könnten (einzeln) und sich die Färbung dabei ändert) (genauer kann sie nur um eins sinken!)

Wir nennen einen Graphen $G$ $k$-kritisch, wenn folgend ${}_{\mathcal{X}}(G)=k$ ist!

Beispiel dafür:

–> wäre dann 3-färbbar

[!Example] Grötsch Graph

Welcher als gutes Beispiel für einen solchen Graphen geben kann:

Verliert jeweils eine Farbe:

oder

Lemma (48) | Minimalgrad

[!Lemma]

Ein jeder $G=(V,E)$ Graph mit ${}_{\mathcal{X}(G)}$ enthält einen $k$-kritischen Untergraphen $H$!

In einem $k$-kritischen Graphen $G=(V,E)$ ist der Minimalgrad folgend gesetzt:

Wie können wir den Minimalgrad in diesem Graphen setzen/beschreiben? #card

Der Minimalgrad ist: $$\delta (G)\ge k-1,\mid E\mid =\frac{1}{2}(k-1)\mid V\mid$$ Was wir in 115.87_uebung07 beweisen!

Lemma (49) | Untrennbarkeit durch vollständigen Untergraphen

[!Definition]

Was können wir über einen kritischen Graphen im Kontext von Trennung durch Untergraphen aussagen? #card

Ein kritischer Graph $G=(V,E)$ kann nicht durch einen vollständigen Untergraphen getrennt werden.

–> Das heißt, ist $S$ eine trennende Knotenmenge $S$, dann ist der von $S$ induzierte Untergraph nicht vollständig

Beweisen können wir das folgend:

Sei $S$ eine trennende Knotenmenge und $H_s$ der von $S$ auf aufspannende Untergraph.

$G$ zerfällt also in $m$ Untergraphen $G_i$ mit $\bigcap V(G_i)=S$ und es gilt dann: ${}_{\mathcal{X}}(G)={\max }_{\mathcal{X}}G{(}_i)$, falls $H_s$ vollständig ist.

Da aber alle $G$ echte Untergraphen sind, gitlt damit dann ${}_{\mathcal{X}}(G_i){<}_{\mathcal{X}}(G),\forall i$ –> $G$ ist kritisch!

und damit folgt dann also: ${}_{\mathcal{X}}(G){<}_{\mathcal{X}}(G)$ was im widerspruch steht!

Hadwiger Vermutung

[!Definition] Hadwiger Vermutung

Für alle $k$ gilt: Ist ${}_{\mathcal{X}}(G)\ge k$, so enthält $G$ einen Untergraph der zu $K_k$ okntrahiert werden kann.

(Diese Struktur wurde nur für alle $k\le 6$) gezeigt

Es ist noch viel Raum nach oben, um das zu beweisen!!

Satz (50) | 3-reguläre Landkarten, ohne Brücken

[!Satz] (50) | Tait | 3-reguläre Landkarten, ohne Brücken

Es gilt, dass eine 3-reguläre Landkarte ohne Brücken genau dann 4-färbbar ist, wenn ihre Kanten 3-färbbar sind!

Satz (53/54) | Whitney - maximal planare, 4-zsm

[!Satz] Satz (53) | maximal, planarer, 4-zshm Graph

Es gilt, dass ein maximal planarer, 4-zusammenhängender Graph einen Hamiltonkreis aufweist.

welche Folgerung können wir hieraus ziehen? #card

Zum Beweis der 4-Farben Vermutung genügt es jetzt also zu zeigen, dass alle planaren Hamiltonsche Graphen 4-färbbar sind –> Zeigt wieder auf, dass die Eigenschaft von hamiltonsch doch etwas aufwendiger / schwieriger zu sein scheint.

Hieraus folgt auch noch eine weitere Folgerung:

Satz ( 55) | 4-zsm, planare Graphen

[!Satz] Satz (55) |

Gegeben sei ein $G=(V,E)$, der 4-zusammenhängend und planar ist.

Was folgt für diesen graph? Weswegen? #card

dieser planare Graph besitzt einen Hamiltonkreis.

–> Was in etwa daraus folgt, dass wir hier kein trennendes Dreieck haben, wie es bei dem 3-regulären Graphen der Fall war!

Satz (56) | Grinberg

[!Req] Satz von Grinberg über hamiltonsche, planare Graphen

Sei $G=(V,E)$ ein schlingenloser, hamiltonscher und planarer Graph mit $n=|V\mid$ Knoten und $C$ ist ein Hamiltonkreis.

Seien dann jetzt $f_i$ (oder auch $g_i$) die Anzahl der Flächen mit $i$ Randkanten im Inneren - oder Äußeren von $C$ (also innerhalb / außerhalb des hamiltonsche Kreises)

Es folgt jetzt: $$\sum _i(i-2)f_i=\sum _i(i-2)g_i=n-2$$

Wie können wir das beweisen? #card

Betrachten wir die Grafik #nachtragen

Wir erkennen, dass die Struktur des Graphen innerhlab des hamiltonsche Graphen limitiert ist –> Weil wir den Constraint des Hamiltonsche Kreis haben

Es können somit nur bestimmte Kanten innerhalb dessen auftreten..

Sei dann $q$ die Anzahl von Kanten die im inneren von $C$ liegen

• Im inneren von $C$ gibt es dann $q+1$ Flächen! Somit folgt $\sum _{f=q+1}()$

Jede der $q$ Kanten ist zu $2$ Flächen inzident jede der $n$ Kanten von $C$ is mit eienr dieser Flächen inzident

Damit folgt dann: $$2q+n=\sum _i(i\cdot f_i)$$

$$\begin{array}{rl}>n& =\sum _i(i\cdot f_i-2q)=\sum _i(if-2)\sum _i(f_i-2)\\ & -\sum _i(i-2)\cdot f_i+2⟹\sum _i(i-2)\cdot f_i=n-2>\end{array}$$ (Am ende wurde das $q$ durch die Summenformel der oberen Angabe eingeführt)

[!Feedback]

Wenn jetzt ein beliebiger Graph die Gleichung nicht erfüllt, so ist er auch nicht Hamiltonsch!

Am Beispiel vom Herschell Graph etwa:

$n=11,f=9,f_4+g_4=9$ –> und somit geht unsere Gleichung nicht auf!

Definition | Unabhängigkeit

[!Definition] Unabhängige Teilmenge eines Graphen

Sei $G=(V,E)$, dann heißt eine Teilmenge $A\subseteq V$ unabhängig, wenn keine zwei Knoten von $A$ durch eine Kante verbunden sind.

Was beschreiben wir mit diesem Konzept/ Was meint die Unabhängigkeitszahl? #card

-> Die Unabhängigkeitszahl $\alpha (G)$ ist die Mächtigkeit einer größten unabhängigen Menge.

Satz | Zsm, unabhangigkeitszahl -> Hamiltonsch

[!Feedback] Erds-Chvátal

Sei $G=(V,E)$ ein Graph mit $\mid V\mid \ge 3$ und einer Zusammenhangszahl $k$ und einer Unabhängigkeitszahl $\alpha$.

Es gilt jetzt: Ist $k\ge \alpha$, dann ist $G$ hamiltonsch!

Wie beweisen wir das? #card

Wir wollen unter Betrachtung der Kontraposition beweisen:

Angenommen $G$ hat eine Zusammenhangszahl $k$ und ist nicht hamiltonsch, dann folgt $\alpha \ge k+1$

Für $k=0,1$ ist die Aussage klar –> keinen Zusammenhang, kann auch keinen hamiltonschen Weg haben und wenn der Zusammenhang 1 ist, so gibts keinen Kreis -> und schon gar keinen Hamiltonkreis!

Für $k\ge 2$ hat $G$ einen Kreis, sei dieser dann $Cmit\ast \ast maximalerL\ddot{a}nge\ast \ast :>>Seijetzt$G_{1}$eineKomponentevon$G \setminus C$und$v_{1}, \dots v_{l}$dieKnotenauf$C_{i}$,dizu$G_{1}$adjazentsind.-->Dabeiist\ast \ast keinpaar\ast \ast$v_{i},v_{j}$benachbart!>>Fernergilt:${ v_{1}, \dots, v_{l} }$isteine\ast \ast trennendeKnotenmenge\ast \ast undfernermusshierbeiauchgelten,dass$l \geq k$(sonstk\ddot{o}nntenwirnichtkompletttrennen!)>>WirwahlenjetzteineRichtungauf$C$unddannseien$w_{1}, \dots w_{l}$dieKnoten,diejeweilsnach$v_{i}$kommen.>>-->Wir\ast \ast behaupten\ast \ast ,dass${ w_{1}, \dots, w_{l} }$unabh\ddot{a}ngigsind!>>Angenommen$w_{i},w_{j}$sinddann\ast \ast adjazent\ast \ast :DannStreichenwir$(v_{i},w_{i})$und$(v_{j},w_{j})$aus$C$undf\ddot{u}genferner$w_{i},w_{j}$unddenPfadvon$v_{i} \to v_{j}$in$G_{1}$ein>DamitistderneueKreis,denwirjakonstruierenkonnten,gr\ddot{o}ßeralso$C$!-->underwarnichtdermaximaleKreis,denwirkonstruierenkonnten>>>Wegender$Max$von$C$istkein$w_{i}$mit$G_{1}$benachbart.>>Ist$w_{0}$einKnoten,soist${ w_{1}, w_{2} ,\dots w_{l} }$unabh\ddot{a}ngig\ast \ast undsomitfolgt\ast \ast :$$\alpha \ge l+1\ge k+1$$