Jedes Matching, das nicht (kardinalitäts-)maximal ist, besitzt einen augmentierenden Pfad.
Note 1: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
GqP(r@WnwP
Before
Front
Back
Jedes Matching, das nicht (kardinalitäts-)maximal ist, besitzt einen augmentierenden Pfad.
(Berge, 1957)
After
Front
Jedes Matching, das nicht (kardinalitäts-)maximal ist, besitzt einen augmentierenden Pfad.
Theorem name included
Theorem name included
Back
Jedes Matching, das nicht (kardinalitäts-)maximal ist, besitzt einen augmentierenden Pfad.
Theorem name included
Theorem name included
(Berge, 1957)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Jedes Matching, das nicht {{c2::(kardinalitäts-)maximal}} ist, besitzt {{c1::einen augmentierenden Pfad}}. | Jedes Matching, das nicht {{c2::(kardinalitäts-)maximal}} ist, besitzt {{c1::einen augmentierenden Pfad}}.<br><br><i>Theorem name included</i> |
Note 2: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
Q@0nZt+]Z(
Previous
Note did not exist
New Note
Front
Für alle \( k \) gilt: jeder \( k \)-reguläre Graph enthält du dumme nuss, das gilt nur für bipartite.
Back
Für alle \( k \) gilt: jeder \( k \)-reguläre Graph enthält du dumme nuss, das gilt nur für bipartite.
Counterexample:
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Für alle \( k \) gilt: jeder \( k \)-reguläre<b> </b>Graph enthält {{c1::du dumme nuss, das gilt nur für bipartite}}. | |
| Extra | Counterexample:<br><img src="paste-193a551c914a2a5dbdcd979b38301cf09f2dbf89.jpg"> |
Note 3: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
nu1#7ym9)6
Before
Front
Für alle \( k \) gilt: jeder \( k \)-reguläre bipartite Graph enthält ein perfektes Matching.
Back
Für alle \( k \) gilt: jeder \( k \)-reguläre bipartite Graph enthält ein perfektes Matching.
(Frobenius, 1917)
Es gilt sogar: Der Graph ist die Vereinigung von perfekten Matchings.
Es gilt sogar: Der Graph ist die Vereinigung von perfekten Matchings.
After
Front
Für alle \( k \) gilt: jeder \( k \)-reguläre bipartite Graph enthält ein perfektes Matching.
Theorem-name included
Theorem-name included
Back
Für alle \( k \) gilt: jeder \( k \)-reguläre bipartite Graph enthält ein perfektes Matching.
Theorem-name included
Theorem-name included
(Frobenius, 1917)
Es gilt sogar: Der Graph ist die Vereinigung von perfekten Matchings.
Es gilt sogar: Der Graph ist die Vereinigung von perfekten Matchings.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Für alle \( k \) gilt: jeder \( k \)-reguläre <b>bipartite </b>Graph enthält {{c1::ein perfektes Matching}}. | Für alle \( k \) gilt: jeder \( k \)-reguläre <b>bipartite </b>Graph enthält {{c1::ein perfektes Matching}}.<br><i><br>Theorem-name included</i> |
Note 4: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
z7su4`:n$D
Before
Front
\(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
Back
\(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
After
Front
\(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
Algorithmus erklärt
Back
\(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
Algorithmus erklärt
BFS/DFS von dem Knoten \(v\) starten. Dann Reihenfolge umdrehen, wir enden also \(v\), für welchen wir \(\Delta(G) - 1\) plus \(1\) für \(v\) selber brauchen.
Da nach entfernen von \(v\) für alle \(v' \in V\) gilt \(\deg'(v) \leq \Delta(G)\), weil wir ja einen entfernt haben.
Da nach entfernen von \(v\) für alle \(v' \in V\) gilt \(\deg'(v) \leq \Delta(G)\), weil wir ja einen entfernt haben.
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 | <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<br><br><i>Algorithmus erklärt</i> |
| Extra | BFS/DFS von dem Knoten \(v\) starten. Dann Reihenfolge umdrehen, wir enden also \(v\), für welchen wir \(\Delta(G) - 1\) plus \(1\) für \(v\) selber brauchen.<br><br>Da nach entfernen von \(v\) für alle \(v' \in V\) gilt \(\deg'(v) \leq \Delta(G)\), weil wir ja einen entfernt haben. |