Lecture: Efficient Graph Algorithms: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
 
(7 intermediate revisions by the same user not shown)
Line 2: Line 2:
{{#ev:youtube|https://www.youtube.com/watch?v=nw5hkRdrdb8|500|right|
{{#ev:youtube|https://www.youtube.com/watch?v=nw5hkRdrdb8|500|right|
|frame}}
|frame}}
<gallery>
<gallery widths=250px>
File:V1 dial 01.jpg|dial 01
File:V1 dial 01.jpg|dial 01
</gallery>
</gallery>
Line 8: Line 8:
{{#ev:youtube|https://www.youtube.com/watch?v=Evt8f8kQPiY|500|right|
{{#ev:youtube|https://www.youtube.com/watch?v=Evt8f8kQPiY|500|right|
|frame}}
|frame}}
<gallery>
<gallery widths="250px">
File:V2 Dijkstra bidirectional Idee.jpg|Dijkstra bidirectional Idee
File:V2 Dijkstra bidirectional Idee.jpg|Dijkstra bidirectional Idee
File:V2 Dijkstra bidirectional Korrektheit.jpg|Dijkstra bidirectional Korrektheit
File:V2 Dijkstra bidirectional Korrektheit.jpg|Dijkstra bidirectional Korrektheit
Line 16: Line 16:
</gallery>
</gallery>
=Lecture recording 3=
=Lecture recording 3=
<gallery>
{{#ev:youtube|https://www.youtube.com/watch?v=Lbnwwl93mHs|500|right|
|frame}}
<gallery widths="250px">
File:V3 BFS Queue.jpg|BFS Queue
File:V3 BFS Queue.jpg|BFS Queue
File:V3 DFS lax-kleinst.jpg|DFS lax-kleinst
File:V3 DFS lax-kleinst.jpg|DFS lax-kleinst
Line 25: Line 27:
</gallery>
</gallery>
=Lecture recording 4=
=Lecture recording 4=
<gallery>
{{#ev:youtube|https://www.youtube.com/watch?v=nlIh-hR4T9M|500|right|
|frame}}
<gallery widths="250px">
File:V4 starke Zusammenhangskomponenten.jpg|starke Zusammenhangskomponenten
File:V4 starke Zusammenhangskomponenten.jpg|starke Zusammenhangskomponenten
</gallery>
</gallery>
=Lecture recording 5=
=Lecture recording 5=
<gallery>
{{#ev:youtube|https://www.youtube.com/watch?v=SJWdFA-b53E|500|right|
|frame}}
<gallery widths="250px">
File:V5 Artikulationspunkt.jpg|Artikulationspunkt
File:V5 Artikulationspunkt.jpg|Artikulationspunkt
File:V5 Bruecke.jpg|Bruecke
File:V5 Bruecke.jpg|Bruecke
Line 43: Line 49:
</gallery>
</gallery>
=Lecture recording 6=
=Lecture recording 6=
<gallery>
{{#ev:youtube|https://www.youtube.com/watch?v=7VHBczAZ1tU|500|right|
|frame}}
<gallery widths="250px">
File:V6 Branching Terminologie.jpg|Branching Terminologie
File:V6 Branching Terminologie.jpg|Branching Terminologie
File:V6 Branching Zykelschrumpfung.jpg|Branching Zykelschrumpfung
File:V6 Branching Zykelschrumpfung.jpg|Branching Zykelschrumpfung
Line 50: Line 58:
</gallery>
</gallery>
=Lecture recording 7=
=Lecture recording 7=
<gallery>
{{#ev:youtube|https://www.youtube.com/watch?v=TtAXbP49VJI|500|right|
|frame}}
<gallery widths="250px">
File:V7 Branching Beweis 1.jpg|Branching Beweis 1
File:V7 Branching Beweis 1.jpg|Branching Beweis 1
File:V7 Branching Beweis 2.jpg|Branching Beweis 2
File:V7 Branching Beweis 2.jpg|Branching Beweis 2
File:V7 Branching falsches Beispiel.jpg|Branching falsches Beispiel
File:V7 Branching falsches Beispiel.jpg|Branching falsches Beispiel
File:V7_branching_Beitrag_Hoehn.pdf|Branching Beitrag Hoehn
</gallery>
</gallery>
=Lecture recording 8=
=Lecture recording 8=
<gallery>
{{#ev:youtube|https://www.youtube.com/watch?v=BZIZTig1fKc|500|right|
|frame}}
<gallery widths="250px">
File:V8 anti-symmetric.jpg|anti-symmetric
File:V8 anti-symmetric.jpg|anti-symmetric
File:V8 augmenting path.jpg|augmenting path
File:V8 augmenting at a node.jpg|V8 augmenting at a node
File:V8 Cut 1.jpg|Cut 1
File:V8 Cut 1.jpg|Cut 1
File:V8 Cut 2.jpg|Cut 2
File:V8 Cut 2.jpg|Cut 2
Line 64: Line 79:
File:V8 neuer augmentierender Pfad einfach.jpg|neuer augmentierender Pfad einfach
File:V8 neuer augmentierender Pfad einfach.jpg|neuer augmentierender Pfad einfach
</gallery>
</gallery>
=Lecture recording 9=
=Lecture recording 9=
<gallery>
{{#ev:youtube|https://www.youtube.com/watch?v=eUGnz-yfPco|500|right|
|frame}}
<gallery widths="250px">
File:V9 Ahuha-Orlin Beweis.jpg|Ahuha-Orlin Beweis
File:V9 Ahuha-Orlin Beweis.jpg|Ahuha-Orlin Beweis
File:V9 Complexity Edmonds-Karp.jpg|Complexity Edmonds-Karp
File:V9 Complexity Edmonds-Karp.jpg|Complexity Edmonds-Karp
Line 73: Line 91:
</gallery>
</gallery>
=Lecture recording 10=
=Lecture recording 10=
<gallery>
{{#ev:youtube|https://www.youtube.com/watch?v=SaPIhRYg5Q4|500|right|
|frame}}
<gallery widths="250px">
File:V10 three indians.jpg|three indians
File:V10 three indians.jpg|three indians
File:V10 valid distance labeling.jpg|valid distance labeling
File:V10 valid distance labeling.jpg|valid distance labeling
</gallery>
</gallery>
=Lecture recording 11=
=Lecture recording 11=
<gallery>
{{#ev:youtube|https://www.youtube.com/watch?v=o9RcytmMCZs|500|right|
|frame}}
<gallery widths="250px">
File:V11 saturierter Schnitt.jpg|saturierter Schnitt
File:V11 saturierter Schnitt.jpg|saturierter Schnitt
</gallery>
</gallery>
=Lecture recording 12=
=Lecture recording 12=
<gallery>
{{#ev:youtube|https://www.youtube.com/watch?v=aqen34eNfs8|500|right|
|frame}}
<gallery widths="250px">
File:V12 negative Kostenfaktoren Beispiel.jpg|negative Kostenfaktoren Beispiel
File:V12 negative Kostenfaktoren Beispiel.jpg|negative Kostenfaktoren Beispiel
File:V12 negative Kostenfaktoren konzeptionell.jpg|negative Kostenfaktoren konzeptionell
File:V12 negative Kostenfaktoren konzeptionell.jpg|negative Kostenfaktoren konzeptionell
Line 88: Line 112:
File:V12 negativer Zykel Skizze.jpg|negativer Zykel Skizze
File:V12 negativer Zykel Skizze.jpg|negativer Zykel Skizze
</gallery>
</gallery>
=Lecture recording 13=
=Lecture recording 13=
<gallery>
{{#ev:youtube|https://www.youtube.com/watch?v=HAQwxvxVbPw|500|right|
|frame}}
<gallery widths="250px">
File:V13 negative cycle initialization.jpg|negative cycle initialization
File:V13 negative cycle initialization.jpg|negative cycle initialization
File:V13 succ shortest paths no neg clcly general.jpg|succ shortest paths no neg clcly general
File:V13 succ shortest paths no neg clcly general.jpg|succ shortest paths no neg clcly general
Line 96: Line 123:
</gallery>
</gallery>
=Lecture recording 14=
=Lecture recording 14=
{{#ev:youtube|https://www.youtube.com/watch?v=Qk4iHtTNz-E|500|right|
|frame}}
=Lecture recording 15=
<gallery widths="250px">
File:V15 Hungarian Algorithm 1.jpg|Hungarian Algorithm 1
File:V15 Hungarian Algorithm 2.jpg|Hungarian Algorithm 2
</gallery>

Latest revision as of 09:07, 13 February 2016

Lecture recording 1

  • dial 01

Lecture recording 2

  • Dijkstra bidirectional Idee

  • Dijkstra bidirectional Korrektheit

  • Dijkstra goaloriented Details

  • Dijkstra goaloriented Idee

  • Dijkstra goaloriented Korrektheit

Lecture recording 3

  • BFS Queue

  • DFS lax-kleinst

  • DFS lexikographische Knotenreihung

  • nichtlexikographische Ausgabereihung

  • DFS Rueckwaertsgehen

  • Murmelbeweis

Lecture recording 4

  • starke Zusammenhangskomponenten

Lecture recording 5

  • Artikulationspunkt

  • Bruecke

  • DFS 2-fache Zshkomp 1

  • DFS 2-fache Zshkomp 2

  • DFS 2-fache Zshkomp 3

  • DFS 2-fache Zshkomp 4

  • DFS 2-fache Zshkomp 5

  • Euler-Algo schematisch

  • Haus vom Nikolaus 1

  • Haus vom Nikolaus 2

  • Haus vom Nikolaus 3

Lecture recording 6

  • Branching Terminologie

  • Branching Zykelschrumpfung

  • Euler-Algo Beweis

  • max-flow multi-source multi-target

Lecture recording 7

  • Branching Beweis 1

  • Branching Beweis 2

  • Branching falsches Beispiel

  • Branching Beitrag Hoehn

Lecture recording 8

  • anti-symmetric

  • augmenting path

  • V8 augmenting at a node

  • Cut 1

  • Cut 2

  • Cut 3

  • neuer augmentierender Pfad Bsp

  • neuer augmentierender Pfad einfach

Lecture recording 9

  • Ahuha-Orlin Beweis

  • Complexity Edmonds-Karp

  • neuer augmentierender Pfad komplex

  • residual network 1

  • residual network 2

Lecture recording 10

  • three indians

  • valid distance labeling

Lecture recording 11

  • saturierter Schnitt

Lecture recording 12

  • negative Kostenfaktoren Beispiel

  • negative Kostenfaktoren konzeptionell

  • negative Zykel Rechnung

  • negativer Zykel Skizze

Lecture recording 13

  • negative cycle initialization

  • succ shortest paths no neg clcly general

  • succ shortest paths no neg cylce simple

  • successive shortest paths iteration

Lecture recording 14

Lecture recording 15

  • Hungarian Algorithm 1

  • Hungarian Algorithm 2

Retrieved from "https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Lecture:_Efficient_Graph_Algorithms&oldid=3751"