07: Algorithmen II, Vorlesung, WS 2018/19, 05.11.2018
1 hour 26 minutes Posted Nov 6, 2018 at 10:50 am.
Start
Tiefensuchschema
Starke Zusammenhangskomponenten
Schrumpfgraph
Konkreter: SCCs mittels DFS
Invarianten von G
Lemma: Abgeschlossene SCCs von G sind SCCs von G
Repräsentation offener Komponenten
Beispiel
Zusammenfassung: SCC Berechnung
2-zusammenhängende Komponenten
Mehr DFS-basierte Linearzeitalgorithmen
Maximum Flows and Matching
Definitions: Network
Definition: Flows
Definition: Minimum s-t Cuts
Duality between flows and cuts
Applications
Applications in our group
Option 1: Linear programming
Algorithms 1956 now
Augmenting paths
Example
Residual Graph
Ford Fulkerson Algorithm
A bad example for Ford Fulkerson
An even worse example
Average case Analyse für MST
0:00
1:26:23
Show notes
07 |
Watch Video
