Anki Deck Changes

Falsch

Siehe Mycielski-Konstruktion.

Konstruktion:
Aus \(G_k = (V_k, E_k)\) mit \(V_k = \{v_1,\ldots,v_n\}\) bilde \(G_{k+1}\):
Füge Knoten \(w_1,\ldots,w_n, z\) hinzu. \(w_i\) ist mit allen Nachbarn von \(v_i\) verbunden (aber nicht mit \(v_i\) selbst). \(z\) ist mit allen \(w_i\) verbunden.
Der neue Graph ist dreiecksfrei und braucht eine Farbe mehr als \(G_k\).

Wahr

Hall-Satz: Da \(G\) \(k\)-regulär ist, hat jeder Knoten in \(X\) Grad \(k\), jeder in \(N(X)\) Grad \(\leq k\). Weil in bipartiten Graphen die Gradsumme links gleich der Gradsumme rechts ist, folgt \(|N(X)| \geq |X|\). Damit ist Halls Bedingung erfüllt und ein Matching der Größe \(|A|\) existiert.

Es gilt sogar: \(E\) lässt sich in \(k\) disjunkte perfekte Matchings partitionieren (iteratives Entfernen eines perfekten Matchings liefert jeweils einen \((k-1)\)-regulären Graphen).

Perfektes Matching in \(k\)-regulären bipartiten Graphen
Das Skript erwähnt, dass es einen Algorithmus gibt, der in Zeit \(O(|E|)\) ein perfektes Matching in \(k\)-regulären bipartiten Graphen findet, sagt aber explizit: „Der allgemeine Fall ist deutlich schwieriger."
Bewiesen wird im Skript nur der Spezialfall \(k = 2^k\) (Satz 1.54).

Note, es geht mit Hopcroft-Karp in \(O(\sqrt{|V|} \cdot |E|)\) schneller.

Augmentierende-Pfade-Algorithmus

• Man startet mit einem beliebigen Matching und sucht iterativ \(M\)-augmentierende Pfade
• Diese baut schichtweise einen Layer-Graphen auf: \(L_0\) sind die unüberdeckten Knoten in \(A\), ungerade Schichten erreicht man über Kanten in \(E \setminus M\), gerade über Kanten in \(M\). Findet man einen unüberdeckten Knoten in \(B\), liefert Backtracking einen augmentierenden Pfad, entlang dessen man augmentiert (\(M := M \oplus P\)). 

Jede Suche kostet \(O(|V| + |E|)\), und man augmentiert höchstens \(|V|/2\) Mal, was \(O(|V| \cdot |E|)\) ergibt.

Das ist der Blossom-Algorithmus.

Dies wird im Christofides-Algorithmus für das metrische TSP benötigt.

Satz 1.54 - Eulertour-basierter Algorithmus

• \(2^k\)-regulärer bipartiter Graph ist eulersch (alle Knoten haben geraden Grad).
• In jeder Zusammenhangskomponente berechnet man eine Eulertour in \(O(|E|)\)
• Dann läuft man diese ab und entfernt jede zweite Kante. 
• Der verbleibende Graph ist \(2^{k-1}\)-regulär. Nach \(k\) Iterationen ist der Graph \(2^0 = 1\)-regulär, also selbst ein perfektes Matching. 

Die Gesamtlaufzeit ist \[\sum_{i=1}^{k} O\!\left(\frac{|E|}{2^{i-1}}\right) = O(|E|)\] weil sich die Kantenzahl in jeder Iteration halbiert (geometrische Reihe).