64 lines
1.6 KiB
Markdown
64 lines
1.6 KiB
Markdown
|
---
|
||
|
|
title: Greedy-Algorithmen
|
||
|
|
date: 2018-11-28
|
||
|
|
---
|
||
|
|
|
||
|
|
Greedy-Algorithmen suchen immer lokal die beste Lösung. Die Lösungen müssen
|
||
|
|
nicht global optimal sein.
|
||
|
|
|
||
|
|
# Algorithmus (Greedy-Färbung)
|
||
|
|
|
||
|
|
**Eingabe**: $G=(V,E)$ ohne Einschränkung $V \in \{1,...,n\}$
|
||
|
|
|
||
|
|
i) setze $c(1) = 1$
|
||
|
|
|
||
|
|
i) `for ` $i \in \{2,...,n\}$ setze
|
||
|
|
|
||
|
|
$$
|
||
|
|
c(i) = \min\limits_{k\in \mathbb{N}} \{ k \neq c(v) | v \in \{1,...,i+1\}
|
||
|
|
\cap \Gamma(i) \}
|
||
|
|
$$
|
||
|
|
|
||
|
|
i) **Ausgabe**: $c : V \rightarrow \{ 1,..., \max \{c(i) | i \in V\} \}$
|
||
|
|
|
||
|
|
|
||
|
|
## Korrektheit
|
||
|
|
|
||
|
|
Da benachbarte Knoten unterschiedliche Farben haben, sit $c$ eine gültige
|
||
|
|
Färbung.
|
||
|
|
|
||
|
|
**Laufzeit**: $O(|V|)$ Iterationen.
|
||
|
|
|
||
|
|
|
||
|
|
Wie gut ist die Lösung des Greedy-Algorithmus?
|
||
|
|
|
||
|
|
|
||
|
|
Sei
|
||
|
|
$$
|
||
|
|
C = \max \{ c(i) | i \in \{1,...,n\} \}
|
||
|
|
$$
|
||
|
|
die Anzahl der Farben die der Greedy-Algorithmus braucht und
|
||
|
|
$$
|
||
|
|
A(G) = \max\limits_{v \in V} deg(v)
|
||
|
|
$$
|
||
|
|
dann gilt
|
||
|
|
$$
|
||
|
|
\chi(G) \leq C \leq \Delta(G) + 1
|
||
|
|
$$
|
||
|
|
da jeder Knoten maximal $\Delta(G)$ Nachbarn hat, ist die gewählte Farbe im
|
||
|
|
Schritt ii) immer kleiner gleich $\Delta(G) + 1$.
|
||
|
|
|
||
|
|
Die Güte der Lösung ist abhängig von der Reihenfolge, in welcher der
|
||
|
|
Greedy-Algorithmus die Knoten abarbeitet.
|
||
|
|
|
||
|
|
**Beispiel**: Betrachte bipartiten Graph mit $V_1 = \{u_1,...,u_n\}$ und
|
||
|
|
$V_2=\{v_1,...,v_n\}$ und $E = \{ \{u_i,v_j\} \mid i,j \in \{1,...,n\}, i \neq
|
||
|
|
j\}$
|
||
|
|
|
||
|
|
a) Reihenfolge $(u_1,u_2,...,u_n,v_1,v_2,...,v_n)$, dann gilt $C = \chi(G)$
|
||
|
|
|
||
|
|
a) Reihenfolge $(u_1,v_1,u_2,v_2,...,u_n,v_n)$, dann gilt $C=n=\Delta(G) + 1$
|
||
|
|
|
||
|
|
Man kann zeigen, dass es immer eine Reihenfolge gibt, so dass $C = \chi(G)$,
|
||
|
|
aber diese Reihenfolge kann man im Allgemeinen nicht effizient finden.
|