Anki Deck Changes

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

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: Ks|I@*|WS;

added

Note did not exist

New Note

Front

Die um die Berechnung von $low[]$ ergänzte Tiefensuche berechnet in einem zusammenhängenden Graphen alle Artikulationsknoten und Brücken in Zeit $O(m)$.

Back

Die um die Berechnung von $low[]$ ergänzte Tiefensuche berechnet in einem zusammenhängenden Graphen alle Artikulationsknoten und Brücken in Zeit $O(m)$.

Field-by-field Comparison

Field	Before	After
Text		Die um {{c1::die Berechnung von $low[]$}} ergänzte {{c2::Tiefensuche}} berechnet in einem zusammenhängenden Graphen alle Artikulationsknoten und Brücken in Zeit $O({{c3::m}})$.

Tags: ETH::2._Semester::A&W::1._Graphentheorie::4._Zusammenhang::2._Brücken

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

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: Q~K)`dx(P@

added

Note did not exist

New Note

Front

Eine Baumkante $e = (v,w)$ ($v$ Elternknoten, $w$ Kindknoten) ist genau dann eine Brücke, wenn $low[w] > dfs[v]$.

Back

Eine Baumkante $e = (v,w)$ ($v$ Elternknoten, $w$ Kindknoten) ist genau dann eine Brücke, wenn $low[w] > dfs[v]$.

Field-by-field Comparison

Field	Before	After
Text		Eine Baumkante $e = (v,w)$ ($v$ Elternknoten, $w$ Kindknoten) ist genau dann {{c1::eine Brücke}}, wenn ${{c2::low[w] > dfs[v]}}$.
Extra		<img src="paste-d0b2f5eb5710c3ee59abdb8b8a1f6ed0c325ee1f.jpg">

Tags: ETH::2._Semester::A&W::1._Graphentheorie::4._Zusammenhang::2._Brücken

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

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

added

Note did not exist

New Note

Front

Wie modelliert man einen d-dimensionalen Hyperwürfel $H_d$?

Knotenmenge: ${{c1::\{0,1\}^d}}$
Kantenmenge: alle Knotenpaare, die sich in genau einer Koordinate unterscheiden

Back

Wie modelliert man einen d-dimensionalen Hyperwürfel $H_d$?

Knotenmenge: ${{c1::\{0,1\}^d}}$
Kantenmenge: alle Knotenpaare, die sich in genau einer Koordinate unterscheiden

Field-by-field Comparison

Field	Before	After
Text		Wie modelliert man einen d-dimensionalen Hyperwürfel $H_d$? <br><ul><li>Knotenmenge: ${{c1::\{0,1\}^d}}$</li><li>Kantenmenge: {{c2::alle Knotenpaare, die sich in genau einer Koordinate unterscheiden}}</li></ul>
Extra		<img src="paste-a4a94c08725e48b529706d587d12a7d331ce2a2c.jpg">

Tags: ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::3._Spezialfälle

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

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

added

Note did not exist

New Note

Front

$v$ ist genau dann Artikulationsknoten, wenn:

$v \neq root$, und $v$ hat ein Kind $u$ im DFS-Baum mit $low[u] \geq dfs[v]$ oder
$v = root$, und $v$ hat mindestens zwei Kinder im DFS-Baum.

Back

$v$ ist genau dann Artikulationsknoten, wenn:

$v \neq root$, und $v$ hat ein Kind $u$ im DFS-Baum mit $low[u] \geq dfs[v]$ oder
$v = root$, und $v$ hat mindestens zwei Kinder im DFS-Baum.

Field-by-field Comparison

Field	Before	After
Text		$v$ ist genau dann Artikulationsknoten, wenn:<br><ol><li>{{c1::$v \neq root$, und $v$ hat ein Kind $u$ im DFS-Baum mit $low[u] \geq dfs[v]$}} <i>oder</i> </li><li>{{c2::$v = root$, und $v$ hat mindestens zwei Kinder im DFS-Baum.}}<br></li></ol>
Extra		<img src="paste-ea1deb937e7e6a87bdef6130ce4e9a344a3e384c.jpg"><img src="paste-e55675aff465182d263d2d6fe17068ece68c323b.jpg">

Tags: ETH::2._Semester::A&W::1._Graphentheorie::4._Zusammenhang::1._Artikulationsknoten

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

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: f(`$#-y9=

added

Note did not exist

New Note

Front

Seien $m,n \geq 2$.

Ein $n \times m$ Gitter enthält einen Hamiltonkreis genau dann, wenn $n \cdot m$ gerade ist.

Back

Seien $m,n \geq 2$.

Ein $n \times m$ Gitter enthält einen Hamiltonkreis genau dann, wenn $n \cdot m$ gerade ist.

Field-by-field Comparison

Field	Before	After
Text		Seien $m,n \geq 2$. <br><br>Ein $n \times m$ Gitter enthält {{c2::einen Hamiltonkreis}} genau dann, wenn{{c1:: $n \cdot m$ gerade ist}}.
Extra		<img src="paste-809e1abac0edcfbe87da0c65863e0b50f5f8f34c.jpg">

Tags: ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::3._Spezialfälle

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

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: fg@9M$8tQu

added

Note did not exist

New Note

Front

$low[v] := $ kleinste dfs-Nummer, die man von $v$ aus durch einen gerichteten Pfad aus (beliebig vielen) Baumkanten und maximal einer Restkante erreichen kann.

Back

$low[v] := $ kleinste dfs-Nummer, die man von $v$ aus durch einen gerichteten Pfad aus (beliebig vielen) Baumkanten und maximal einer Restkante erreichen kann.

Field-by-field Comparison

Field	Before	After
Text		$low[v] := $ {{c1::kleinste dfs-Nummer, die man von $v$ aus durch einen gerichteten Pfad aus (beliebig vielen) Baumkanten und maximal einer Restkante erreichen kann.}}
Extra		<img src="paste-a980ee9bc4ecd58e7f3cc1325b72e98237fe76ba.jpg">

Tags: ETH::2._Semester::A&W::1._Graphentheorie::4._Zusammenhang::1._Artikulationsknoten

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

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: fo)WAx?|,)

added

Note did not exist

New Note

Front

Formale Definition der low-Werte:

$low[v] = {{c1::\min \left( dfs[v], \min_{(v,w) \in E} \begin{cases} dfs[w], & \text{falls } (v,w) \text{ Restkante} \\ low[w], & \text{falls } (v,w) \text{ Baumkante} \end{cases} \right)}}$

Back

Field-by-field Comparison

Field	Before	After
Text		Formale Definition der low-Werte:<br><br>$low[v] = {{c1::\min \left( dfs[v], \min_{(v,w) \in E} \begin{cases} dfs[w], & \text{falls } (v,w) \text{ Restkante} \\ low[w], & \text{falls } (v,w) \text{ Baumkante} \end{cases} \right)}}$
Extra		<img src="paste-79da13aca3f345c42c6580661cde2b76fdfaf3df.jpg">

Tags: ETH::2._Semester::A&W::1._Graphentheorie::4._Zusammenhang::1._Artikulationsknoten

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

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: o#3J@N=o8V

added

Note did not exist

New Note

Front

Alle low-Werte sind in Zeit $O(|V| + |E|)$ berechenbar.

Back

Alle low-Werte sind in Zeit $O(|V| + |E|)$ berechenbar.

Field-by-field Comparison

Field	Before	After
Text		Alle low-Werte sind in Zeit  $O({{c1::\|V\| + \|E\|}})$ berechenbar.

Tags: ETH::2._Semester::A&W::1._Graphentheorie::4._Zusammenhang::1._Artikulationsknoten

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

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: rn*.g&Oq!H

added

Note did not exist

New Note

Front

Berechnung der low-Werte:

Initialisierung mit dfs-Wert
ggf update, wenn Restkanten gefunden werden
ggf update, wenn Algorithmus während des backtracks zum Knoten zurückkehrt

Back

Berechnung der low-Werte:

Initialisierung mit dfs-Wert
ggf update, wenn Restkanten gefunden werden
ggf update, wenn Algorithmus während des backtracks zum Knoten zurückkehrt

Field-by-field Comparison

Field	Before	After
Text		Berechnung der low-Werte:<br><ol><li>{{c1::Initialisierung mit dfs-Wert}}</li><li>{{c2::ggf update, wenn Restkanten gefunden werden}}</li><li>{{c3::ggf update, wenn Algorithmus während des backtracks zum Knoten zurückkehrt}}</li></ol>
Extra		<img src="paste-a82fcf67dde33bdb9bdd711c0fc03917fc5276bf.jpg">

Tags: ETH::2._Semester::A&W::1._Graphentheorie::4._Zusammenhang::1._Artikulationsknoten

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

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

u{i


            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::3._Spezialfälle
  
  
    Enthält ein d-dimensionaler Hyperwürfel \(H_d\) einen Hamiltonkreis?
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::3._Spezialfälle
  
  
    Enthält ein d-dimensionaler Hyperwürfel \(H_d\) einen Hamiltonkreis?
    
    Ja.


  






                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Front
                            
                            Enthält ein d-dimensionaler Hyperwürfel \(H_d\)&nbsp;einen Hamiltonkreis?
                        
                        
                        
                            Back
                            
                            Ja.<br><br><img src="paste-67449c1e553f7b87cc589014a8b9a32173b50c69.jpg">
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::3._Spezialfälle

Field	Before	After
Front		Enthält ein d-dimensionaler Hyperwürfel \(H_d\) einen Hamiltonkreis?
Back		Ja.<br><br><img src="paste-67449c1e553f7b87cc589014a8b9a32173b50c69.jpg">


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

                Note Type: Horvath Cloze

                GUID: v&jb;-4MR2
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::1._Graphentheorie::4._Zusammenhang::2._Brücken
  
  
    Restkanten sind niemals Brücken.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::1._Graphentheorie::4._Zusammenhang::2._Brücken
  
  
    Restkanten sind niemals Brücken.
    
    
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            Restkanten sind {{c1::niemals::immer/manchmal/niemals}} Brücken.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::1._Graphentheorie::4._Zusammenhang::2._Brücken
                    
                
            
            
        
        
        
            Note 12: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Classic

                GUID: v6dJ77=3Bk
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::3._Spezialfälle
  
  
    Hat ein Petersengraph einen Hamiltonkreis?
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::3._Spezialfälle
  
  
    Hat ein Petersengraph einen Hamiltonkreis?
    
    Nein.


  






                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Front
                            
                            Hat ein Petersengraph einen Hamiltonkreis?
                        
                        
                        
                            Back
                            
                            Nein.<br><br><img src="paste-ddce853b58c8706546b0a3a9f555ce59dfd885f4.jpg">
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::3._Spezialfälle
                    
                
            
            
        
        
        
            Note 13: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Classic

                GUID: vH2CI}z;H`
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::3._Spezialfälle
  
  
    Hat ein Ikosaeder einen Hamiltonkreis?
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::3._Spezialfälle
  
  
    Hat ein Ikosaeder einen Hamiltonkreis?
    
    Ja.


  






                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Front
                            
                            Hat ein Ikosaeder einen Hamiltonkreis?
                        
                        
                        
                            Back
                            
                            Ja.<br><br><img src="paste-2f1376a5ccd3c273c1a4306f3f19a7950c13bdc3.jpg">
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::3._Spezialfälle

Field	Before	After
Text		Eine Baumkante \(e = (v,w)\) (\(v\) Elternknoten, \(w\) Kindknoten) ist genau dann {{c1::eine Brücke}}, wenn \({{c2::low[w] > dfs[v]}}\).
Extra		<img src="paste-d0b2f5eb5710c3ee59abdb8b8a1f6ed0c325ee1f.jpg">

Field	Before	After
Text		\(v\) ist genau dann Artikulationsknoten, wenn:<br><ol><li>{{c1::\(v \neq root\), und \(v\) hat ein Kind \(u\) im DFS-Baum mit \(low[u] \geq dfs[v]\)}} <i>oder</i> </li><li>{{c2::\(v = root\), und \(v\) hat mindestens zwei Kinder im DFS-Baum.}}<br></li></ol>
Extra		<img src="paste-ea1deb937e7e6a87bdef6130ce4e9a344a3e384c.jpg"><img src="paste-e55675aff465182d263d2d6fe17068ece68c323b.jpg">

Field	Before	After
Text		Seien \(m,n \geq 2\). <br><br>Ein \(n \times m\) Gitter enthält {{c2::einen Hamiltonkreis}} genau dann, wenn{{c1:: \(n \cdot m\) gerade ist}}.
Extra		<img src="paste-809e1abac0edcfbe87da0c65863e0b50f5f8f34c.jpg">

Field	Before	After
Text		\(low[v] := \) {{c1::kleinste dfs-Nummer, die man von \(v\) aus durch einen gerichteten Pfad aus (beliebig vielen) Baumkanten und maximal einer Restkante erreichen kann.}}
Extra		<img src="paste-a980ee9bc4ecd58e7f3cc1325b72e98237fe76ba.jpg">

Field	Before	After
Front		Hat ein Petersengraph einen Hamiltonkreis?
Back		Nein.<br><br><img src="paste-ddce853b58c8706546b0a3a9f555ce59dfd885f4.jpg">

Field	Before	After
Front		Hat ein Ikosaeder einen Hamiltonkreis?
Back		Ja.<br><br><img src="paste-2f1376a5ccd3c273c1a4306f3f19a7950c13bdc3.jpg">