1.6 KiB
| title | date |
|---|---|
| Greedy-Algorithmen | 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.