Anki Deck Changes

Commit: e72fc727 - fix some auw

Author: obrhubr <obrhubr+noreply@noreply.com>

Date: 2026-03-27T16:24:43+01:00

Changes: 4 note(s) changed (1 added, 3 modified, 0 deleted)

Note 1: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: Pp@EGP+L[^
added

Previous

Note did not exist

New Note

Front

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings::1._Algorithmen
Hopcroft-Karp findet in einem bipartiten Graphen in {{c1::\(O(\sqrt{|V|} \cdot |E|)\)}} ein maximales Matching.

Back

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings::1._Algorithmen
Hopcroft-Karp findet in einem bipartiten Graphen in {{c1::\(O(\sqrt{|V|} \cdot |E|)\)}} ein maximales Matching.
Field-by-field Comparison
Field Before After
Text Hopcroft-Karp findet in einem {{c1::<b>bipartiten Graphen</b>}} in {{c1::\(O(\sqrt{|V|} \cdot |E|)\)}} ein {{c1::maximales Matching}}.
Tags: ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings::1._Algorithmen

Note 2: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: hFx`}69EnK
modified

Before

Front

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings::1._Algorithmen
Der Algorithmus von Hopcroft-Karp verbessert den augmentierenden-Pfad-Algorithmus,
indem er pro Iteration nicht nur einen, sondern eine
inklusionsmaximale Menge paarweise disjunkter kürzester augmentierender Pfade
findet und simultan augmentiert.

Die while-Schleife wird nur \(O(\sqrt{|V|})\) mal durchlaufen.
Proof Sketch Included

Back

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings::1._Algorithmen
Der Algorithmus von Hopcroft-Karp verbessert den augmentierenden-Pfad-Algorithmus,
indem er pro Iteration nicht nur einen, sondern eine
inklusionsmaximale Menge paarweise disjunkter kürzester augmentierender Pfade
findet und simultan augmentiert.

Die while-Schleife wird nur \(O(\sqrt{|V|})\) mal durchlaufen.
Proof Sketch Included
Gesamtlaufzeit: \(O(\sqrt{|V|} \cdot (|V| + |E|))\).

Proof Sketch
Augmentieren mit kürzestem Pfad \(P\) erhöht die Länge des nächsten kürzesten Pfades um mindestens 2.
  • Sei M ein Matching, für das der kürzeste augmentierende Pfad Länge k hat und M' ein anderes beliebiges Matching. Dann gilt \(|M'| \le |M| + \frac{|V|}{k + 1}\)

After

Front

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings::1._Algorithmen
Der Algorithmus von Hopcroft-Karp (bipartiter Graph) verbessert den augmentierenden-Pfad-Algorithmus,
indem er pro Iteration nicht nur einen, sondern eine
inklusionsmaximale Menge paarweise disjunkter kürzester augmentierender Pfade
findet und simultan augmentiert.

Die while-Schleife wird nur \(O(\sqrt{|V|})\) mal durchlaufen.
Proof Sketch Included

Back

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings::1._Algorithmen
Der Algorithmus von Hopcroft-Karp (bipartiter Graph) verbessert den augmentierenden-Pfad-Algorithmus,
indem er pro Iteration nicht nur einen, sondern eine
inklusionsmaximale Menge paarweise disjunkter kürzester augmentierender Pfade
findet und simultan augmentiert.

Die while-Schleife wird nur \(O(\sqrt{|V|})\) mal durchlaufen.
Proof Sketch Included
Gesamtlaufzeit: \(O(\sqrt{|V|} \cdot (|V| + |E|))\).

Proof Sketch
Augmentieren mit kürzestem Pfad \(P\) erhöht die Länge des nächsten kürzesten Pfades um mindestens 2.
  • Sei M ein Matching, für das der kürzeste augmentierende Pfad Länge k hat und M' ein anderes beliebiges Matching. Dann gilt \(|M'| \le |M| + \frac{|V|}{k + 1}\)
Field-by-field Comparison
Field Before After
Text Der Algorithmus von Hopcroft-Karp verbessert den augmentierenden-Pfad-Algorithmus,<br>indem er pro Iteration nicht nur einen, sondern eine<br>{{c1::inklusionsmaximale Menge paarweise disjunkter kürzester augmentierender Pfade}}<br>findet und simultan augmentiert.<br><br>Die while-Schleife wird nur \(O({{c2::\sqrt{|V|}}})\) mal durchlaufen.<br><i>Proof Sketch Included</i> Der Algorithmus von Hopcroft-Karp (<b>bipartiter Graph</b>)&nbsp;verbessert den augmentierenden-Pfad-Algorithmus,<br>indem er pro Iteration nicht nur einen, sondern eine<br>{{c1::inklusionsmaximale Menge paarweise disjunkter kürzester augmentierender Pfade}}<br>findet und simultan augmentiert.<br><br>Die while-Schleife wird nur \(O({{c2::\sqrt{|V|}}})\) mal durchlaufen.<br><i>Proof Sketch Included</i>
Tags: ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings::1._Algorithmen

Note 3: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: u_Z|D!/cJ.
modified

Before

Front

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings::1._Algorithmen
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

Back

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings::1._Algorithmen
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

After

Front

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings::1._Algorithmen
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 (Hopcroft-Karp)

Back

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings::1._Algorithmen
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 (Hopcroft-Karp)
Field-by-field Comparison
Field Before After
Text State of the Art Matching:<br><ul><li>\( O({{c1::|E|^{1+o(1)} }}) \)&nbsp;für bipartite Graphen </li><li>\( O({{c2::|V|^{1/2} \cdot |E|}}) \)&nbsp;für generelle Graphen</li></ul> State of the Art Matching:<br><ul><li>\( O({{c1::|E|^{1+o(1)} }}) \)&nbsp;für bipartite Graphen&nbsp;</li><li>\( O({{c2::|V|^{1/2} \cdot |E|}}) \)&nbsp;für generelle Graphen (Hopcroft-Karp)</li></ul>
Tags: ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings::1._Algorithmen

Note 4: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: yQa5-0YeQw
modified

Before

Front

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings::1._Algorithmen
Für \(n\) gerade und \(\ell : \binom{[n]}{2} \to \mathbb{N}_0\) kann man in Zeit
\(O(n^3)\) ein minimales (gewichtsminimales) perfektes Matching in \(K_n\) finden.

Back

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings::1._Algorithmen
Für \(n\) gerade und \(\ell : \binom{[n]}{2} \to \mathbb{N}_0\) kann man in Zeit
\(O(n^3)\) ein minimales (gewichtsminimales) perfektes Matching in \(K_n\) finden.
Dies wird im Christofides-Algorithmus für das metrische TSP benötigt.

After

Front

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings::1._Algorithmen
Für \(n\) gerade und \(\ell : \binom{[n]}{2} \to \mathbb{N}_0\) kann man in Zeit \(O(n^3)\) ein minimales (gewichtsminimales) perfektes Matching in \(K_n\) finden.

Back

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings::1._Algorithmen
Für \(n\) gerade und \(\ell : \binom{[n]}{2} \to \mathbb{N}_0\) kann man in Zeit \(O(n^3)\) ein minimales (gewichtsminimales) perfektes Matching in \(K_n\) finden.
Dies wird im Christofides-Algorithmus für das metrische TSP benötigt.
Field-by-field Comparison
Field Before After
Text Für \(n\) gerade und \(\ell : \binom{[n]}{2} \to \mathbb{N}_0\) kann man in Zeit<br>\(O({{c1::n^3}})\) ein {{c2::minimales (gewichtsminimales) perfektes Matching}} in \(K_n\) finden. Für \(n\) gerade und \(\ell : \binom{[n]}{2} \to \mathbb{N}_0\) kann man in Zeit&nbsp;\(O({{c1::n^3}})\) ein {{c2::minimales (gewichtsminimales) <b>perfektes</b> Matching}} in \(K_n\) finden.
Tags: ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings::1._Algorithmen
↑ Top