Anki Deck Changes

Algorithmus Metrisches TSP

1. {{c1::Bestimme minimalen Spannbaum T
   es gilt: \( \ell(T) \leq \text{opt}(K_n, \ell) \)}}
   

Ein M-augmentierender Pfad ist ein Pfad, der abwechselnd Kanten aus \( M \) und nicht aus \( M \) enthält und der in von \( M \) nicht überdeckten Knoten beginnt und endet.

Ein Matching \( M \subseteq E \) ist ein inklusionsmaximales Matching, wenn es kein Matching \( M' \) gibt mit \( M \subseteq M' \) und \( |M'| > |M| \).

Jedes Matching, das nicht (kardinalitäts-)maximal ist, besitzt einen augmentierenden Pfad.

Seien \( M \), \( M' \) beliebige Matchings.

Betrachte den Teilgraphen mit Kantenmenge \( M \oplus M' \).



Jeder Knoten hat Grad \( \leq 2 \) \( \Rightarrow \) Kollektion von Pfaden und Kreisen.

Jeder Pfad/Kreis wechselt ab zwischen Kanten aus \( M \) und \( M' \).

Seien \( M \), \( M' \) beliebige Matchings.

Betrachte den Teilgraphen mit Kantenmenge \( M \oplus M' \).



Falls \( |M| < |M'| \), so gibt es mindestens einen Pfad mit Start- und Endkante in \( M' \).

Wie funktioniert der Algorithmus um ein maximales Matching zu finden?

Eine Kantenmenge \( M \subseteq E \) heisst Matching in einem Graphen \( G = (V, E) \), falls kein Knoten des Graphen zu mehr als einer Kante aus \( M \) inzident ist.

Ein Matching \( M \) heisst perfektes Matching, wenn {{c2::jeder Knoten durch genau eine Kante aus \( M \) überdeckt wird, oder, anders ausgedrückt, wenn \( |M| = \frac{|V|}{2}\)}}.

Seien \( M \), \( M' \) beliebige Matchings.

Betrachte den Teilgraphen mit Kantenmenge \( M \oplus M' \).



Jeder Knoten hat Grad \( \leq 2 \) \( \Rightarrow \) Kollektion von Pfaden und Kreisen.

Für jede Kante in \( M_{\text{max}} \) gilt: Mindestens einer der beiden Endpunkte wird von einer Kante aus \( M_{\text{Greedy \) überdeckt}}

Inklusionsmaximal? Kardinalitätsmaximal?

Jede Kante in \( M_{\text{Greedy}} \) kann höchstens zwei Kanten aus \( M_{\text{max \)}} überdecken.

Inklusionsmaximal? Kardinalitätsmaximal?

Ein Matching \( M \subseteq E \) ist ein (kardinalitäts-)maximales Matching, wenn es kein Matching \( M' \) gibt mit \( |M'| > |M| \).

Beim metrischen TSP kann man aus einem MST eine 2-Approximation ableiten.

Ein Knoten \( v \) wird von \( M \) überdeckt, falls es eine Kante \( e \in M \) gibt, die \( v \) enthält.

Algorithmus Metrisches TSP

1. Bestimme minimalen Spannbaum T
   es gilt: \( \ell(T) \leq \text{opt}(K_n, \ell) \)
2. verdopple alle Kanten von T
   es gilt: \( 2\ell(T) \leq 2\text{opt}(K_n, \ell) \)
3. bestimme Eulertour W
   es gilt: \( \ell(W) = 2\ell(T) \leq 2\text{opt}(K_n, \ell) \)
4. durchlaufe W, mit Abkürzungen, so dass jeder Knoten nur einmal besucht wird \( \Rightarrow \) Hamiltonkreis C
   

Für alle \( k \) gilt: jeder \( k \)-reguläre bipartite Graph enthält ein perfektes Matching.

In \( k \)-regulären bipartiten Graphen kann man in Zeit \( O(|E|) \) ein perfektes Matching bestimmen.

In bipartiten Graphen kann man in Zeit \( O(|V| \cdot |E|) \) ein perfektes Matching bestimmen.

Konzept der augmentierenden Pfade: \( O(|V| \cdot |E|) \) für bipartite Graphen

Mit einem Greedy-Algorithmus kann man in Zeit \( O(|E|) \) ein inklusionsmaximales Matching \( M_{\text{Greedy}} \) bestimmen mit
\[{{c2:: |M_{\text{Greedy} }| \geq |M_{\text{max} }| / 2, }}\]
wobei \( M_{\text{max}} \) ein kardinalitätsmaximales Matching ist.

State of the Art Matching:

• \( O({{c1::|E|^{1+o(1)} }}) \) für bipartite Graphen
• \( O({{c2::|V|^{1/2} \cdot |E|}}) \) für generelle Graphen

Ein bipartiter Graph \( G = (A \uplus B, E) \) enthält ein Matching \( M \) der Kardinalität \( |M| = |A| \iff \forall X \subseteq A : |X| \leq |N(X)| \).