Anki Deck Changes

Commit: 8f2908dd - minitest 2

Author: lhorva <lhorva@student.ethz.ch>

Date: 2026-03-12T16:43:50+01:00

Changes: 10 note(s) changed (10 added, 0 modified, 0 deleted)

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

Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID: D/A{W?@*_o
added

Previous

Note did not exist

New Note

Front

ETH::2._Semester::A&W::1._Graphentheorie::7._Färbungen ETH::2._Semester::A&W::Minitests::2
Wahr oder falsch?

Jeder Kreis ist 2-färbbar.

Back

ETH::2._Semester::A&W::1._Graphentheorie::7._Färbungen ETH::2._Semester::A&W::Minitests::2
Wahr oder falsch?

Jeder Kreis ist 2-färbbar.
Falsch
Field-by-field Comparison
Field Before After
Front Wahr oder falsch?<br><br>Jeder Kreis ist 2-färbbar.
Back Falsch
Tags: ETH::2._Semester::A&W::1._Graphentheorie::7._Färbungen ETH::2._Semester::A&W::Minitests::2

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

Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID: K>bJ4n9}2B
added

Previous

Note did not exist

New Note

Front

ETH::2._Semester::A&W::1._Graphentheorie::7._Färbungen ETH::2._Semester::A&W::Minitests::2
Wahr oder falsch?

Es gibt einen Algorithmus mit polynomieller Laufzeit, der eine \(1,5\)-Approximation für das metrische Problem des Handlungsreisenden (TSP) findet.

Back

ETH::2._Semester::A&W::1._Graphentheorie::7._Färbungen ETH::2._Semester::A&W::Minitests::2
Wahr oder falsch?

Es gibt einen Algorithmus mit polynomieller Laufzeit, der eine \(1,5\)-Approximation für das metrische Problem des Handlungsreisenden (TSP) findet.
Wahr
Field-by-field Comparison
Field Before After
Front Wahr oder falsch?<br><br>Es gibt einen Algorithmus mit polynomieller Laufzeit, der eine \(1,5\)-Approximation für das metrische Problem des Handlungsreisenden (TSP) findet.
Back Wahr
Tags: ETH::2._Semester::A&W::1._Graphentheorie::7._Färbungen ETH::2._Semester::A&W::Minitests::2

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

Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID: MK
added

Previous

Note did not exist

New Note

Front

ETH::2._Semester::A&W::1._Graphentheorie::7._Färbungen ETH::2._Semester::A&W::Minitests::2
Wahr oder falsch?

Es gibt einen polynomiellen Algorithmus, der für jeden planaren Graphen eine geeignete Einfärbung mit 6 Farben findet.

Back

ETH::2._Semester::A&W::1._Graphentheorie::7._Färbungen ETH::2._Semester::A&W::Minitests::2
Wahr oder falsch?

Es gibt einen polynomiellen Algorithmus, der für jeden planaren Graphen eine geeignete Einfärbung mit 6 Farben findet.
Wahr
Field-by-field Comparison
Field Before After
Front Wahr oder falsch?<br><br>Es gibt einen polynomiellen Algorithmus, der für jeden planaren Graphen eine geeignete Einfärbung mit 6 Farben findet.
Back Wahr
Tags: ETH::2._Semester::A&W::1._Graphentheorie::7._Färbungen ETH::2._Semester::A&W::Minitests::2

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

Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID: N{,q$aNY7]
added

Previous

Note did not exist

New Note

Front

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings ETH::2._Semester::A&W::Minitests::2
Wahr oder falsch?

Jeder Graph ohne Dreieck hat eine chromatische Zahl von höchstens 100.

Back

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings ETH::2._Semester::A&W::Minitests::2
Wahr oder falsch?

Jeder Graph ohne Dreieck hat eine chromatische Zahl von höchstens 100.
Falsch
Field-by-field Comparison
Field Before After
Front Wahr oder falsch?<br><br>Jeder Graph ohne Dreieck hat eine chromatische Zahl von höchstens 100.
Back Falsch
Tags: ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings ETH::2._Semester::A&W::Minitests::2

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

Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID: cQtd|[>DYL
added

Previous

Note did not exist

New Note

Front

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings ETH::2._Semester::A&W::Minitests::2
Wahr oder falsch?

Jeder \(k\)-reguläre bipartite Graph \(G = (A \cup B, E)\) für \(k \geq 1\) hat ein Matching der Größe \(|A|\).

Back

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings ETH::2._Semester::A&W::Minitests::2
Wahr oder falsch?

Jeder \(k\)-reguläre bipartite Graph \(G = (A \cup B, E)\) für \(k \geq 1\) hat ein Matching der Größe \(|A|\).
Wahr
Field-by-field Comparison
Field Before After
Front Wahr oder falsch?<br><br>Jeder \(k\)-reguläre bipartite Graph \(G = (A \cup B, E)\) für \(k \geq 1\) hat ein Matching der Größe \(|A|\).
Back Wahr
Tags: ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings ETH::2._Semester::A&W::Minitests::2

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

Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID: itUq/f`To4
added

Previous

Note did not exist

New Note

Front

ETH::2._Semester::A&W::1._Graphentheorie::7._Färbungen ETH::2._Semester::A&W::Minitests::2
Wahr oder falsch?

Ist \(G\) ein Graph mit maximalem Grad \(\Delta(G)\), so findet der Greedy-Algorithmus (mit beliebiger Knotenreihenfolge) stets eine zulässige Färbung mit höchstens \(\Delta(G) + 1\) Farben.

Back

ETH::2._Semester::A&W::1._Graphentheorie::7._Färbungen ETH::2._Semester::A&W::Minitests::2
Wahr oder falsch?

Ist \(G\) ein Graph mit maximalem Grad \(\Delta(G)\), so findet der Greedy-Algorithmus (mit beliebiger Knotenreihenfolge) stets eine zulässige Färbung mit höchstens \(\Delta(G) + 1\) Farben.
Wahr
Field-by-field Comparison
Field Before After
Front Wahr oder falsch?<br><br>Ist \(G\) ein Graph mit maximalem Grad \(\Delta(G)\), so findet der Greedy-Algorithmus (mit beliebiger Knotenreihenfolge) stets eine zulässige Färbung mit höchstens \(\Delta(G) + 1\) Farben.
Back Wahr
Tags: ETH::2._Semester::A&W::1._Graphentheorie::7._Färbungen ETH::2._Semester::A&W::Minitests::2

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

Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID: k/*bc^92[M
added

Previous

Note did not exist

New Note

Front

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings ETH::2._Semester::A&W::Minitests::2
Wahr oder falsch?

Ein (kardinalitäts-)maximale Matching in einem bipartiten Graphen kann in der Zeit \(O(\sqrt{|V|}(|V| + |E|))\) gefunden werden.

Back

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings ETH::2._Semester::A&W::Minitests::2
Wahr oder falsch?

Ein (kardinalitäts-)maximale Matching in einem bipartiten Graphen kann in der Zeit \(O(\sqrt{|V|}(|V| + |E|))\) gefunden werden.
Wahr
Field-by-field Comparison
Field Before After
Front Wahr oder falsch?<br><br>Ein (kardinalitäts-)maximale Matching in einem bipartiten Graphen kann in der Zeit \(O(\sqrt{|V|}(|V| + |E|))\) gefunden werden.
Back Wahr
Tags: ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings ETH::2._Semester::A&W::Minitests::2

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

Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID: s!zsm$&sf}
added

Previous

Note did not exist

New Note

Front

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings ETH::2._Semester::A&W::Minitests::2
Wahr oder falsch?

Für einen vollständigen Graphen \(G\) mit gerader Anzahl von Knoten und positiven Gewichten \(\ell(x,y)\), der die Dreiecksungleichung erfüllt, sei \(M\) ein perfektes Matching mit minimalen Kosten und \(C\) die minimale Kosten-Reise des Handlungsreisenden (TSP-Tour). Dann ist \(\ell(M) \leq \ell(C)/2\).

Back

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings ETH::2._Semester::A&W::Minitests::2
Wahr oder falsch?

Für einen vollständigen Graphen \(G\) mit gerader Anzahl von Knoten und positiven Gewichten \(\ell(x,y)\), der die Dreiecksungleichung erfüllt, sei \(M\) ein perfektes Matching mit minimalen Kosten und \(C\) die minimale Kosten-Reise des Handlungsreisenden (TSP-Tour). Dann ist \(\ell(M) \leq \ell(C)/2\).
Wahr
Field-by-field Comparison
Field Before After
Front Wahr oder falsch?<br><br>Für einen vollständigen Graphen \(G\) mit gerader Anzahl von Knoten und&nbsp;positiven Gewichten \(\ell(x,y)\), der die Dreiecksungleichung erfüllt, sei \(M\) ein perfektes Matching mit minimalen Kosten und \(C\) die minimale Kosten-Reise des Handlungsreisenden (TSP-Tour). Dann ist \(\ell(M) \leq \ell(C)/2\).
Back Wahr
Tags: ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings ETH::2._Semester::A&W::Minitests::2

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

Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID: uf^.=Rr;Q]
added

Previous

Note did not exist

New Note

Front

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings ETH::2._Semester::A&W::Minitests::2
Wahr oder falsch?

Wenn \(G\) ein zusammenhängender Graph mit einem maximalen Grad von 100 ist, dann hat \(G\) eine korrekte Färbung mit 100 Farben, es sei denn, \(G\) ist ein vollständiger Graph.

Back

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings ETH::2._Semester::A&W::Minitests::2
Wahr oder falsch?

Wenn \(G\) ein zusammenhängender Graph mit einem maximalen Grad von 100 ist, dann hat \(G\) eine korrekte Färbung mit 100 Farben, es sei denn, \(G\) ist ein vollständiger Graph.
Wahr
Field-by-field Comparison
Field Before After
Front Wahr oder falsch?<br><br>Wenn \(G\) ein zusammenhängender Graph mit einem maximalen Grad von&nbsp;100 ist, dann hat \(G\) eine korrekte Färbung mit 100 Farben, es sei denn, \(G\) ist ein vollständiger Graph.
Back Wahr
Tags: ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings ETH::2._Semester::A&W::Minitests::2

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

Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID: uzC1We:u-n
added

Previous

Note did not exist

New Note

Front

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings ETH::2._Semester::A&W::Minitests::2
Wahr oder falsch?

Wenn \(G\) ein bipartiter Graph ist und \(M\) ein Matching in \(G\) ist, das nicht kardinalitätsmaximal ist, dann gibt es in \(G\) einen augmentierenden Pfad bezüglich \(M\).

Back

ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings ETH::2._Semester::A&W::Minitests::2
Wahr oder falsch?

Wenn \(G\) ein bipartiter Graph ist und \(M\) ein Matching in \(G\) ist, das nicht kardinalitätsmaximal ist, dann gibt es in \(G\) einen augmentierenden Pfad bezüglich \(M\).
Wahr
Field-by-field Comparison
Field Before After
Front Wahr oder falsch?<br><br>Wenn \(G\) ein bipartiter Graph ist und \(M\) ein Matching in \(G\) ist, das nicht kardinalitätsmaximal ist, dann gibt es in \(G\) einen augmentierenden Pfad bezüglich \(M\).
Back Wahr
Tags: ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings ETH::2._Semester::A&W::Minitests::2
↑ Top