199 lines
4.7 KiB
Markdown
199 lines
4.7 KiB
Markdown
---
|
|
title: Knoten-Färbung
|
|
date: 2018-11-28
|
|
---
|
|
|
|
# Motivation
|
|
|
|
a) Mobilfunk: Masten/Frequenzen
|
|
|
|
i) Mobilfunkmasten, deren Sendebereich überlappt, brauchen verschiedene
|
|
Frequenzen zum senden.
|
|
|
|
i) Wir wollen insgesamt möglichst wenige Frequenzen nutzen
|
|
|
|
**Als Graph**: Mobilfunkmasten $\widehat{=}$ Knoten. Kanten zwischen
|
|
Knoten, falls Sendebereich überlappt. Frequenzen zuweisen, so dass
|
|
benachbarte Knoten unterschiedliche Frequenzen haben
|
|
|
|
a) Compilerbau: Zur selben Zeit genutzte Variablen sollen in unterschiedlichen
|
|
Registern gespeichert werden
|
|
|
|
a) Landkarten: Benachbarte Länder sollen unterschiedliche Farben bekommen.
|
|
Länder $\widehat{=}$ Knoten. Kanten zu Knoten, falls Länder eine gemeinsame
|
|
Grenze haben (hier: planare Graphen).
|
|
|
|
|
|
# Definition (Knoten-Färbung)
|
|
|
|
Sei $k \in \mathbb{N}$ und $G=(V,E)$ Graph
|
|
|
|
i) Eine $k$-Färbung von $G$ ist eine Abbildung
|
|
|
|
$$
|
|
C: v \rightarrow \{1,...,k\}
|
|
$$
|
|
|
|
mit der Eigenschaft $\forall \{u,v\} \in E : c(u) \neq c(v)$
|
|
|
|
i) $G$ heist **$k$-färbbar**, falls es eine $k$-Färbung von $G$ gibt
|
|
|
|
i) Die **chromatische Zahl** $\chi(G)$ von $G$ ist definiert als
|
|
|
|
$$
|
|
\chi(G) = \min \{ k\in \mathbb{N} | G \text{ ist } k \text{-färbbar} \}
|
|
$$
|
|
|
|
|
|
## Beispiel
|
|
|
|
a) 
|
|
|
|
$$
|
|
c(1) = 1 \\
|
|
c(2) = 3 \\
|
|
c(3) = 2 \\
|
|
c(4) = 1 \\
|
|
c(5) = 2 \\
|
|
\\
|
|
\chi(G) = 3
|
|
$$
|
|
|
|
a) Jeder Graph $G=(V,E)$ miz $|V|=n$ ist $n$-färbbar
|
|
|
|
a) Es gilt $\chi(K_n) = n$
|
|
|
|
a) Kreise $C_n$
|
|
|
|
i) falls $n$ gerade ist $\chi(C_n) = 2$
|
|
|
|
i) falls $n$ ungerade ist $\chi(C_n) = 3$
|
|
|
|
a) Bipartite Graphen: Bipartiter Graph $G=(V,E)$. Es gibt eine Partition von
|
|
$V$ in $V_1$ und $V_2$. $V = V_1 \biguplus V_2$ und $E \subseteq \{ \{u,v\} | u
|
|
\in V_1, v \in V_2 \}$. Bipartite Graphen haben $\chi(G) = 2$ und es gilt
|
|
sogar:
|
|
|
|
|
|
# Satz
|
|
|
|
Ein Graph $G=(V,E)$ hat $\chi(G) = 2$ $\Leftrightarrow$ $G$ ist bipratit.
|
|
|
|
|
|
## Beweis
|
|
|
|
"$\Leftarrow$" siehe oben
|
|
|
|
"$\Rightarrow$" Sei $G=(V,E)$ ein Graph mit $\chi(G) = 2$. Das heißt $\exists c
|
|
: V \rightarrow \{1,2\}$ mit $\forall \{u,v\} \in E: c(u) \neq c(v)$.
|
|
|
|
Setze $V_1 = \{v \in V | c(v) = 1 \}$ und $V_2 = \{v \in V | c(v) = 2 \}$.
|
|
Damit gilt $V = V_1 \biguplus V_2$ und $E \subseteq \{ \{u,v\} | u \in V_1, v
|
|
\in V_2 \}$ denn es gibt keine Katen zu Knoten gleicher Farbe.
|
|
|
|
|
|
Es gilt weiterhin
|
|
|
|
# Satz
|
|
|
|
Sei $G=(V,E)$ Graph, dann gilt $\chi(G) = 2$ genau dann, wenn $G$ keinen Kreis
|
|
ungerader Länge enthält.
|
|
|
|
## Beweis
|
|
|
|
"$\Rightarrow$" Sei $G$ ein Graph, der einen Kreis ungerader Länge enthält. Für
|
|
diesen Teilgraph braucht man schon 3 Farben. Damit kann $G$ nicht 2-färbbar
|
|
sein.
|
|
|
|
"$\Leftarrow$" Sei $G$ ein Graph der keinen Kreis ungerader Länge enthäöt. Wir
|
|
nehmen ohne Einschränkung an, dass $G$ zusammenhängend ist. Wähle $s\in V$
|
|
beliebig und führe Breitensuche auf $G$ mit Startknoten $s$ aus. Liefert
|
|
Spannbaum $T = \{ \{v,pred[v]\} | v \in V \setminus \{s\} \}$ und
|
|
Abstandsvektor $d[v]$.
|
|
|
|
Wir setzen $c: V \rightarrow \{1,2\}$ mit $c(v) = \begin{cases}
|
|
1 & 2 \mid d[v] \\
|
|
2 & 2 \nmid d[v]
|
|
\end{cases}$. Dies liefert die Färbung auf $T$.
|
|
|
|
Die weiteren Kanten von $G$ schließen Kreise gerader Länge. Deshalb haben
|
|
Endknoten immer unterschiedliche Farben.
|
|
|
|
$$
|
|
\tag*{$\Box$}
|
|
$$
|
|
|
|
|
|
$$
|
|
\chi(G) = 2 \Leftrightarrow G\text{ ist bipartit} \Leftrightarrow G \text{
|
|
enthält keinen Kreis ungerader Länge}
|
|
$$
|
|
|
|
|
|
# Satz
|
|
|
|
Sei $G=(V,E)$ ein planarer Graph. Dann gilt $\chi(G) \leq 6$.
|
|
|
|
## Beweis
|
|
|
|
(per Induktion)
|
|
|
|
Die Aussage ist trivial, falls $|V| \leq 6$.
|
|
|
|
**Induktionsschritt**: Sei nun $G=(V,E)$ planar mit $|V| \geq 6$. Da $G$
|
|
planar, $\exists v \in V : deg(v) \leq 5$.
|
|
|
|
Betrachte $G' = G \setminus \{v\}$. Nach Induktionsanfang gibt es eine Färbung
|
|
für $G'$ mit maximal 6 Farben. Das heißt
|
|
|
|
$$
|
|
\exists c' : V \setminus \{v\} \rightarrow \{1,...,6\} \text{ so dass} \\
|
|
\forall \{u,w\} \in E, u,w \neq v : c'(u) \neq c'(v)
|
|
$$
|
|
|
|
Wir konstruieren
|
|
|
|
$$
|
|
c: V \rightarrow \{1,...,6\} \text{ mit} \\
|
|
c(u) = \begin{cases}
|
|
c'(u) & u \neq v \\
|
|
\min \{\{1,...,6\} \setminus \{c'(x)\} | x \in \Gamma(v)\} & u = v
|
|
\end{cases}
|
|
$$
|
|
|
|
Da $|\Gamma(v)| \leq 5$ ist $c(v) \in \{1,...,6\}$ wohl definiert und $c$ ist
|
|
Färbung von $G$.
|
|
|
|
$$
|
|
\tag*{$\Box$}
|
|
$$
|
|
|
|
|
|
Mit ein wenig mehr Aufwand kann man zeigen
|
|
|
|
$$
|
|
G \text{ planar} \Rightarrow \chi(G) \leq 5
|
|
$$
|
|
|
|
|
|
Es gilt sogar
|
|
|
|
# Satz
|
|
|
|
Sei $G=(V,E)$ planar, dann gilt $\chi(G) \leq 4$
|
|
|
|
|
|
## Bemerkungen
|
|
|
|
i) Computergestützter Beweis
|
|
|
|
i) Es gibt einen Algorithmus, der für planare Graphen eine 4-Färbung in
|
|
Laufzeit $O(|V|^2)$ berechnet
|
|
|
|
i) Für allgemeine Graphen ist die Frage $\chi(G) \stackrel{?}{\le} 3$ nicht
|
|
effizient zu entscheiden (d.h. wir kennen keinen Algorithmus mit polynomieller
|
|
Laufzeit)
|
|
|
|
|
|
Deshalb: effiziente Algorithmen, die eine nicht-optimale Lösung finden
|