Anki Deck Changes

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

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: CKz#W`~;R+

modified

Before

Front

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.

Back

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.

\( \Rightarrow \) durch Tauschen entlang \( M \) können wir das Matching vergrössern

After

Front

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.

Back

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.

\( \Rightarrow \) durch Tauschen entlang \( M \) können wir das Matching vergrössern

Field-by-field Comparison

Field	Before	After
Text	Ein {{c1::M-augmentierender Pfad}} ist ein Pfad, der a{{c2::bwechselnd Kanten aus \( M \) und nicht aus \( M \) enthält und der in von \( M \) nicht überdeckten Knoten beginnt und endet}}.	Ein {{c1::M-augmentierender Pfad}} ist ein Pfad, der {{c2::abwechselnd Kanten aus \( M \) und nicht aus \( M \) enthält und der in von \( M \) nicht überdeckten Knoten beginnt und endet}}.

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: DVs)|{g]G9

modified

Before

Front

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

Back

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

After

Front

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

Back

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

Field-by-field Comparison

Field	Before	After
Text	Ein Matching \( M \subseteq E \) ist ein {{c1::inklusionsmaximales Matching}}, wenn es kein Matching \( M' \) gibt mit \( M \subseteq M' \) und \( \|M'\| > \|M\| \).	Ein Matching \( M \subseteq E \) ist ein {{c1::inklusionsmaximales Matching}}, wenn {{c2::es kein Matching \( M' \) gibt mit \( M \subseteq M' \) und \( \|M'\| > \|M\| \)}}.

Tags: ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings

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

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: Ogv;,*^ce|

modified

Before

Front

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

Back

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

(Denn sonst könnten wir die Kante zu \( M_{\text{Greedy}} \) hinzufügen.)

After

Front

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

Back

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

(Denn sonst könnten wir die Kante zu \( M_{\text{Greedy}} \) hinzufügen.)

Field-by-field Comparison

Field	Before	After
Text	<img src="paste-889d732e37d44fee9ae8a068d3fc03393243ad71.jpg"><br><br>Für jede Kante in \( M_{\text{max}} \) gilt: {{c1::Mindestens einer der beiden Endpunkte wird von einer Kante aus \( M_{\text{Greedy}} \) überdeckt}}	<img src="paste-889d732e37d44fee9ae8a068d3fc03393243ad71.jpg"><br><br>Für jede Kante in \( M_{\text{max}} \) gilt: {{c1::Mindestens einer der beiden Endpunkte wird von einer Kante aus \( M_{\text{Greedy} } \) überdeckt}}

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: cF!WjeyLtp

modified

Before

Front

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

Back

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

After

Front

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

Back

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

Field-by-field Comparison

Field	Before	After
Text	<img src="paste-889d732e37d44fee9ae8a068d3fc03393243ad71.jpg"><br><br>Jede Kante in \( M_{\text{Greedy}} \) kann höchstens {{c1::zwei Kanten aus \( M_{\text{max}} \)}} überdecken.	<img src="paste-889d732e37d44fee9ae8a068d3fc03393243ad71.jpg"><br><br>Jede Kante in \( M_{\text{Greedy}} \) kann höchstens {{c1::zwei Kanten aus \( M_{\text{max} } \)}} überdecken.

Tags: ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings::1._Algorithmen

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

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: e}S|+cs>4(

modified

Before

Front

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

Back

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

After

Front

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

Back

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

Field-by-field Comparison

Field	Before	After
Text	Ein Matching \( M \subseteq E \) ist ein {{c1::(kardinalitäts-)maximales Matching}}, wenn es kein Matching \( M' \) gibt mit \( \|M'\| > \|M\| \).	Ein Matching \( M \subseteq E \) ist ein {{c1::(kardinalitäts-)maximales Matching}}, wenn {{c2::es kein Matching \( M' \) gibt mit \( \|M'\| > \|M\| \)}}.

Tags: ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings

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

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: g9kFpAzwii

added

New Note

Front

Big \(O\) von Matching-Algorithmen:

Für bipartite Graphen

\( O(|V|^{1/2} \cdot |E|) \) Hopcroft-Karp (ungewichtet)
\( O(|E|^{1+o(1)}) \) (mit polynominellen Gewichte)

Für allgemeine Graphen (mit polynominellen Gewichten)

\( O({{c1::|V|^{1/2} \cdot |E|}}) \) Micali-Vazirani (ungewichtet) / Gabow-Tarjan
\( O({{c2::|V|^{2.373} }}) \) mit Matrix-Multiplikation - Mucha, Sankowski (ungewichtet)

Back

Big \(O\) von Matching-Algorithmen:

Für bipartite Graphen

\( O(|V|^{1/2} \cdot |E|) \) Hopcroft-Karp (ungewichtet)
\( O(|E|^{1+o(1)}) \) (mit polynominellen Gewichte)

Für allgemeine Graphen (mit polynominellen Gewichten)

\( O({{c1::|V|^{1/2} \cdot |E|}}) \) Micali-Vazirani (ungewichtet) / Gabow-Tarjan
\( O({{c2::|V|^{2.373} }}) \) mit Matrix-Multiplikation - Mucha, Sankowski (ungewichtet)

Field-by-field Comparison

Field	Before	After
Text		Big \(O\) von Matching-Algorithmen:<br><br>Für bipartite Graphen <ul> <li>\( O(\|V\|^{1/2} \cdot \|E\|) \) Hopcroft-Karp (ungewichtet)</li> <li>\( O(\|E\|^{1+o(1)}) \) (mit polynominellen Gewichte)</li> </ul>Für allgemeine Graphen (mit polynominellen Gewichten) <ul> <li>\( O({{c1::\|V\|^{1/2} \cdot \|E\|}}) \) Micali-Vazirani (ungewichtet) / Gabow-Tarjan</li> <li>\( O({{c2::\|V\|^{2.373} }}) \) mit Matrix-Multiplikation - Mucha, Sankowski (ungewichtet)</li> </ul>

Tags: ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings::1._Algorithmen

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

Before

Front

Back

After

Front

Back

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

Before

Front

Back

After

Front

Back

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

Before

Front

Back

After

Front

Back

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

Before

Front

Back

After

Front

Back

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

Before

Front

Back

After

Front

Back

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

Previous

New Note

Front

Back