' \(X:=\) Knoten mit ungeradem Grad in \(T\) Bestimme minimales Matching \(M\) für \(X\) es gilt: \(\ell(M) \leq \frac{1}{2}\text{opt}(K_n, \ell)\)
bestimme Eulertour W
es gilt: \(\ell(W) = \ell(T) + \ell(M) \leq \frac{3}{2}\text{opt}(K_n, \ell)\)
durchlaufe W, mit Abkürzungen, so dass jeder Knoten nur einmal besucht wird \( \Rightarrow \) Hamiltonkreis C es gilt: \(\ell(C)\leq \ell(W) = {{c1::\ell(T) + \ell(M) \leq \frac{3}{2}\text{opt}(K_n, \ell)}}\)
' \(X:=\) Knoten mit ungeradem Grad in \(T\) Bestimme minimales Matching \(M\) für \(X\) es gilt: \(\ell(M) \leq \frac{1}{2}\text{opt}(K_n, \ell)\)
bestimme Eulertour W
es gilt: \(\ell(W) = \ell(T) + \ell(M) \leq \frac{3}{2}\text{opt}(K_n, \ell)\)
durchlaufe W, mit Abkürzungen, so dass jeder Knoten nur einmal besucht wird \( \Rightarrow \) Hamiltonkreis C es gilt: \(\ell(C)\leq \ell(W) = {{c1::\ell(T) + \ell(M) \leq \frac{3}{2}\text{opt}(K_n, \ell)}}\)
Field-by-field Comparison
Field
Before
After
Text
3/2-Approximation Metrisches TSP<br><ol>
<li>Bestimme minimalen Spannbaum \(T\)<br>es gilt: \( \ell(T) \leq \text{opt}(K_n, \ell) \)
</li>
<li>' \(X:=\) Knoten mit ungeradem Grad in \(T\)<br>Bestimme minimales Matching \(M\) für \(X\) <br>es gilt: \(\ell(M) \leq \frac{1}{2}\text{opt}(K_n, \ell)\)</li>
<li>bestimme Eulertour W
<br>es gilt: \(\ell(W) = \ell(T) + \ell(M) \leq \frac{3}{2}\text{opt}(K_n, \ell)\)
</li>
<li>durchlaufe W, mit Abkürzungen, so dass jeder Knoten nur einmal besucht wird \( \Rightarrow \) Hamiltonkreis C<br>es gilt: \(\ell(C)\leq \ell(W) = {{c1::\ell(T) + \ell(M) \leq \frac{3}{2}\text{opt}(K_n, \ell)}}\)</li>
</ol>
Christofides' Algorithmus berechnet in polynomineller Zeit eine 1.5-Approximation für das metrische TSP.
Seit 1976 ist dies der beste Approximationsfaktor, für den ein polynomieller Algorithmus bekannt ist war.
September '20: Karlin, Klein, Gharan finden in polynomieller Zeit eine 1.4999999999999999999999999999999999999990-Approximation.
Geht es besser? Vermutlich. Aber: Es ist NP-schwer, eine 1.008-Approximation zu finden.
Field-by-field Comparison
Field
Before
After
Text
Christofides' Algorithmus berechnet in polynomineller Zeit eine {{c1::1.5-Approximation für das metrische TSP}}.
Extra
<ul>
<li>Seit 1976 ist dies der beste Approximationsfaktor, für den ein polynomieller Algorithmus bekannt <s>ist</s> war.</li>
<li><strong>September '20:</strong> Karlin, Klein, Gharan finden in polynomieller Zeit eine 1.4999999999999999999999999999999999999990-Approximation.</li>
<li>Geht es besser? Vermutlich.<br>
<strong>Aber:</strong> Es ist NP-schwer, eine 1.008-Approximation zu finden.</li>
</ul>
Sei \(G\) ein Graph, in dem man jeden Block mit \(k\) Farben färben kann.
Dann kann man auch \(G\) mit \(k\) Farben färben.
Field-by-field Comparison
Field
Before
After
Text
<img src="paste-7df7c4f76513b8f48a5f5c4a0fbf613a27433cfe.jpg"><br><br>Sei \(G\) ein Graph, in dem man jeden Block mit \(k\) Farben färben kann.<br><br>Dann kann man {{c1::auch \(G\) mit \(k\) Farben färben}}.
\(G \neq K_n,\ G \neq {{c1::C_{2n+1} }},\ G\) zshgd.: \(\Rightarrow\) \(G\) kann in Zeit \(O(|E|)\) mit \(\Delta(G)\) Farben gefärbt werden
Satz von Brooks
\(K_n\) ist der vollständige Graph auf (n) Knoten - jeder Knoten ist mit jedem anderen verbunden. Er braucht \(n\) Farben.
\(C_{2n+1}\) ist ein Kreis mit einer ungeraden Anzahl von Knoten (z.B. Dreieck, Fünfeck, ...). Er braucht 3 Farben, obwohl \(\Delta = 2\).
Field-by-field Comparison
Field
Before
After
Text
<img src="paste-7df7c4f76513b8f48a5f5c4a0fbf613a27433cfe.jpg"><br><br>\(G \neq {{c1::K_n}},\ G \neq {{c1::C_{2n+1} }},\ G\) zshgd.:<br>\(\Rightarrow\) \(G\) kann in Zeit \(O(|E|)\) mit \(\Delta(G)\) Farben gefärbt werden
Extra
Satz von Brooks<br><br><div>\(K_n\) ist der vollständige Graph auf (n) Knoten - jeder Knoten ist mit jedem anderen verbunden. Er braucht \(n\) Farben.</div>
<div>\(C_{2n+1}\) ist ein Kreis mit einer ungeraden Anzahl von Knoten (z.B. Dreieck, Fünfeck, ...). Er braucht 3 Farben, obwohl \(\Delta = 2\).</div>
\(\forall k \in \mathbb{N},\ \forall r \in \mathbb{N}\): Es gibt Graphen ohne einen Kreis mit Länge \(\leq k\), aber mit chromatischer Zahl \(\geq r\).
\(\forall k \in \mathbb{N},\ \forall r \in \mathbb{N}\): Es gibt Graphen ohne einen Kreis mit Länge \(\leq k\), aber mit chromatischer Zahl \(\geq r\).
Lokal sieht der Graph aus wie ein Baum (alle Knoten, die man von einem \(v\) aus in \(k/2\) Schritten erreichen kann).
Field-by-field Comparison
Field
Before
After
Text
\(\forall k \in \mathbb{N},\ \forall r \in \mathbb{N}\): Es gibt Graphen ohne einen Kreis mit Länge \(\leq k\), aber mit {{c1::chromatischer Zahl \(\geq r\)}}.
Extra
Lokal sieht der Graph aus wie ein Baum (alle Knoten, die man von einem \(v\) aus in \(k/2\) Schritten erreichen kann).<br><br><img src="paste-3893a1a6c745c86f2e98fa901ab33f000e40b5b1.jpg">
Die Heuristik findet eine Färbung mit \(\leq 6\) Farben für planare Graphen.
Field-by-field Comparison
Field
Before
After
Text
<img src="paste-7df7c4f76513b8f48a5f5c4a0fbf613a27433cfe.jpg"><br><br>Die Heuristik findet eine Färbung mit \({{c1::\leq 6}}\) Farben für planare Graphen.
Gilt für die (gewählte) Reihenfolge \(|N(v_i) \cap \{v_1, \ldots, v_{i-1}\}| \leq k\) \(\forall\, 2 \leq i \leq n\), dann benötigt der Greedy-Algorithmus höchstens \(k+1\) viele Farben.
Gilt für die (gewählte) Reihenfolge \(|N(v_i) \cap \{v_1, \ldots, v_{i-1}\}| \leq k\) \(\forall\, 2 \leq i \leq n\), dann benötigt der Greedy-Algorithmus höchstens \(k+1\) viele Farben.
Heuristik: \(v_n\) := Knoten vom kleinsten Grad. Lösche \(v_n\). \(v_{n-1}\) := Knoten vom kleinsten Grad im Restgraph. Lösche \(v_{n-1}\). Iteriere.
Falls \(G=(V,E)\) erfüllt: In jedem Subgraphen gibt es einen Knoten mit Grad \(\leq k\) \(\Rightarrow\) Heuristik liefert Reihenfolge \(v_1,\ldots,v_n\) für die der Greedy-Algorithmus höchstens \(k+1\) Farben benötigt
Field-by-field Comparison
Field
Before
After
Text
<img src="paste-abfd33d5257708cb778d485196521618b5c07e9e.jpg"><br><br>Gilt für die (gewählte) Reihenfolge \(|N(v_i) \cap \{v_1, \ldots, v_{i-1}\}| \leq k\) \(\forall\, 2 \leq i \leq n\), dann benötigt der Greedy-Algorithmus höchstens \({{c1::k+1}}\) viele Farben.
Extra
Heuristik:<br>\(v_n\) := Knoten vom kleinsten Grad. Lösche \(v_n\).<br>\(v_{n-1}\) := Knoten vom kleinsten Grad im Restgraph. Lösche \(v_{n-1}\). Iteriere.<br><br>Falls \(G=(V,E)\) erfüllt:<br>In jedem Subgraphen gibt es einen Knoten mit Grad \(\leq k\)<br>\(\Rightarrow\) Heuristik liefert Reihenfolge \(v_1,\ldots,v_n\) für die der Greedy-Algorithmus höchstens \(k+1\) Farben benötigt
' {{c1::\(X:=\) Knoten mit ungeradem Grad in \(T\) Bestimme minimales Matching \(M\) für \(X\) es gilt: \(\ell(M) \leq \frac{1}{2}\text{opt}(K_n, \ell)\) }}
' {{c1::\(X:=\) Knoten mit ungeradem Grad in \(T\) Bestimme minimales Matching \(M\) für \(X\) es gilt: \(\ell(M) \leq \frac{1}{2}\text{opt}(K_n, \ell)\) }}
Bestimme minimalen Spannbaum T
es gilt: \( \ell(T) \leq \text{opt}(K_n, \ell) \)
verdopple alle Kanten von T
es gilt: \( 2\ell(T) \leq 2\text{opt}(K_n, \ell) \)
bestimme Eulertour W
es gilt: \( \ell(W) = 2\ell(T) \leq 2\text{opt}(K_n, \ell) \)
{{c1::durchlaufe W, mit Abkürzungen, so dass jeder Knoten nur einmal besucht wird \( \Rightarrow \) Hamiltonkreis C es gilt: \(\ell(C) \leq \ell(W) = 2\ell(T) \leq 2\text{opt}(K_n, \ell)\)}}
Bestimme minimalen Spannbaum T
es gilt: \( \ell(T) \leq \text{opt}(K_n, \ell) \)
verdopple alle Kanten von T
es gilt: \( 2\ell(T) \leq 2\text{opt}(K_n, \ell) \)
bestimme Eulertour W
es gilt: \( \ell(W) = 2\ell(T) \leq 2\text{opt}(K_n, \ell) \)
{{c1::durchlaufe W, mit Abkürzungen, so dass jeder Knoten nur einmal besucht wird \( \Rightarrow \) Hamiltonkreis C es gilt: \(\ell(C) \leq \ell(W) = 2\ell(T) \leq 2\text{opt}(K_n, \ell)\)}}
Field-by-field Comparison
Field
Before
After
Text
Algorithmus Metrisches TSP<br><ol>
<li>Bestimme minimalen Spannbaum T
<br>es gilt: \( \ell(T) \leq \text{opt}(K_n, \ell) \)
</li>
<li>verdopple alle Kanten von T
<br>es gilt: \( 2\ell(T) \leq 2\text{opt}(K_n, \ell) \)
</li>
<li>bestimme Eulertour W
<br>es gilt: \( \ell(W) = 2\ell(T) \leq 2\text{opt}(K_n, \ell) \)
</li>
<li>{{c1::durchlaufe W, mit Abkürzungen, so dass jeder Knoten nur einmal besucht wird \( \Rightarrow \) Hamiltonkreis C}}<br></li>
</ol>
2-Approximation Metrisches TSP<br><ol>
<li>Bestimme minimalen Spannbaum T
<br>es gilt: \( \ell(T) \leq \text{opt}(K_n, \ell) \)
</li>
<li>verdopple alle Kanten von T
<br>es gilt: \( 2\ell(T) \leq 2\text{opt}(K_n, \ell) \)
</li>
<li>bestimme Eulertour W
<br>es gilt: \( \ell(W) = 2\ell(T) \leq 2\text{opt}(K_n, \ell) \)
</li>
<li>{{c1::durchlaufe W, mit Abkürzungen, so dass jeder Knoten nur einmal besucht wird \( \Rightarrow \) Hamiltonkreis C<br>es gilt: \(\ell(C) \leq \ell(W) = 2\ell(T) \leq 2\text{opt}(K_n, \ell)\)}}</li>
</ol>
Es gibt bipartite Graphen und eine Reihenfolge \(V = \{v_1, \ldots, v_n\}\) der Knoten, für die der Greedy-Algorithmus \(|V|/2\) viele Farben benötigt.
Es gibt bipartite Graphen und eine Reihenfolge \(V = \{v_1, \ldots, v_n\}\) der Knoten, für die der Greedy-Algorithmus \(|V|/2\) viele Farben benötigt.
Vollständig bipartiter Graph ohne ein perfektes Matching
Field-by-field Comparison
Field
Before
After
Text
<img src="paste-abfd33d5257708cb778d485196521618b5c07e9e.jpg"><br><br>Es gibt bipartite Graphen und eine Reihenfolge \(V = \{v_1, \ldots, v_n\}\) der Knoten, für die der Greedy-Algorithmus \({{c1::|V|/2}}\) viele Farben benötigt.
Extra
<img src="paste-ecb9a75e5082691ee6c7c0b1899b7cb1de7004c5.jpg"><br>Vollständig bipartiter Graph ohne ein perfektes Matching
Heuristik: \(v_n\) := Knoten vom kleinsten Grad. Lösche \(v_n\). \(v_{n-1}\) := Knoten vom kleinsten Grad im Restgraph. Lösche \(v_{n-1}\). Iteriere.
Falls \(G=(V,E)\) erfüllt: In jedem Subgraphen gibt es einen Knoten mit Grad \(\leq k\)
\(\Rightarrow\) Heuristik liefert Reihenfolge \(v_1,\ldots,v_n\) für die der Greedy-Algorithmus höchstens \(k+1\) Farben benötigt
Field-by-field Comparison
Field
Before
After
Text
<img src="paste-64d1ec7afe8d86718547048820e1a3dd13d47a8c.jpg"><br><br>Heuristik:<br>\(v_n\) := Knoten vom kleinsten Grad. Lösche \(v_n\).<br>\(v_{n-1}\) := Knoten vom kleinsten Grad im Restgraph. Lösche \(v_{n-1}\). Iteriere.<br><br>Falls \(G=(V,E)\) erfüllt:<br>{{c1::In jedem Subgraphen gibt es einen Knoten mit Grad \(\leq k\) }}
Extra
\(\Rightarrow\) Heuristik liefert Reihenfolge \(v_1,\ldots,v_n\) für die der Greedy-Algorithmus höchstens \(k+1\) Farben benötigt
Es gibt eine Reihenfolge \(V = \{v_1, \ldots, v_n\}\) der Knoten, für die der Greedy-Algorithmus nur \(\chi(G)\) viele Farben benötigt.
Field-by-field Comparison
Field
Before
After
Text
<img src="paste-abfd33d5257708cb778d485196521618b5c07e9e.jpg"><br><br>Es gibt eine Reihenfolge \(V = \{v_1, \ldots, v_n\}\) der Knoten, für die der Greedy-Algorithmus nur \({{c1::\chi(G)}}\) viele Farben benötigt.
Eine (Knoten-)Färbung eines Graphen \(G = (V, E)\) mit \(k\) Farben ist eine Abbildung \(c : V \to [k]\), so dass gilt: {{c1::\(c(u) \neq c(v)\) für alle Kanten \(\{u, v\} \in E\). }}
Eine (Knoten-)Färbung eines Graphen \(G = (V, E)\) mit \(k\) Farben ist eine Abbildung \(c : V \to [k]\), so dass gilt: {{c1::\(c(u) \neq c(v)\) für alle Kanten \(\{u, v\} \in E\). }}
Field-by-field Comparison
Field
Before
After
Text
Eine (Knoten-)Färbung eines Graphen \(G = (V, E)\) mit \(k\) Farben ist eine Abbildung \(c : V \to [k]\), so dass gilt:<br>{{c1::\(c(u) \neq c(v)\) für alle Kanten \(\{u, v\} \in E\). }}
Jeder Graph kann in Zeit \(O(|E|)\) mit \(\Delta(G)+1\) Farben gefärbt werden.
Field-by-field Comparison
Field
Before
After
Text
<img src="paste-7df7c4f76513b8f48a5f5c4a0fbf613a27433cfe.jpg"><br><br>Jeder Graph kann in Zeit \(O({{c1::|E|}})\) mit \(\Delta(G)+1\) Farben gefärbt werden.
\(G=(V,E)\) zshgd. und es gibt \(v \in V\) mit \(\deg(v) < \Delta(G)\) \(\Rightarrow\) Heuristik (oder Breiten-/Tiefensuche) liefert Reihenfolge, für die der Greedy-Algorithmus höchstens \(\Delta(G)\) Farben benötigt
\(G=(V,E)\) zshgd. und es gibt \(v \in V\) mit \(\deg(v) < \Delta(G)\) \(\Rightarrow\) Heuristik (oder Breiten-/Tiefensuche) liefert Reihenfolge, für die der Greedy-Algorithmus höchstens \(\Delta(G)\) Farben benötigt
Field-by-field Comparison
Field
Before
After
Text
<img src="paste-7df7c4f76513b8f48a5f5c4a0fbf613a27433cfe.jpg"><br><br>\(G=(V,E)\) zshgd. und es gibt \(v \in V\) mit \(\deg(v) < \Delta(G)\)<br>\(\Rightarrow\) Heuristik (oder Breiten-/Tiefensuche) liefert Reihenfolge, für die der Greedy-Algorithmus höchstens \({{c1::\Delta(G)}}\) Farben benötigt
