Video-Server

Angewandte Graphentheorie

von Dr. Markus Nieß

Beschreibung

4.2013

Vorlesungsaufzeichnungen

Autoplay
04.04.201301:30:301.336
Soziale Netzwerkanalyse
1.1 Grundlegende Definitionen:
1.1.1 Definition eines Graphen
1.1.2 Adjazenz- und Inzidenzmatrix
1.1.3 Soziale Netzwerke - Dichte und Kohäsion
1.2 Positionsanalyse - Zentralitätsmaße:
1.2.1 Gradzentralität
05.04.201301:33:27389
Soziale Netzwerkanalyse
1.2 Positionsanalyse - Zentralitätsmaße:
1.2.2 Wege, Erreichbarkeit und Nähebasierte Zentralität:
1.2.2.1 Wege, Erreichbarkeit, Pfaddistanzen
1.2.2.2 Nähebasierte und Proximity-Zentralität
1.2.3 Betweenness-Zentralität
1.2.4 Clusterkoeffizient
10.04.201301:34:10269
Soziale Netzwerkanalyse
1.3 Eigenvektorzentralität - Sätze von Perron-Frobenius:
1.3.1 Vorbereitungen
1.3.2 Positive Matrizen - Satz von Perron
12.04.201301:34:45206
Soziale Netzwerkanalyse
1.3 Eigenvektorzentralität - Sätze von Perron-Frobenius:
1.3.3 Unzerlegbare nicht-negative Matrizen:
1.3.3.1 Definition - Satz von Perron-Frobenius
1.3.3.2 Charakterisierung unzerlegbarer Matrizen
1.3.4 Eigenvektorzentralität
19.04.201301:36:17202
Soziale Netzwerkanalyse
1.3 Eigenvektorzentralität - Sätze von Perron-Frobenius:
1.3.5 PageRank-Algorithmus
1.4 Gruppenkonzepte:
1.4.1 Distanz-/Erreichbarkeitsbasierte Konzepte
25.04.201301:30:22216
Soziale Netzwerkanalyse --- Suchverfahren und Kürzeste Wege in Graphen
1. Soziale Netzwerkanalyse:
1.4 Gruppenkonzepte:
1.4.2 Gradbasierte Konzepte
2. Suchverfahren und Kürzeste Wege in Graphen:
2.1 Bäume und Wälder
2.2 Theorie kürzester Weg
26.04.201301:48:57193
Suchverfahren und Kürzeste Wege in Graphen
2. Suchverfahren und Kürzeste Wege in Graphen:
2.3 Suchverfahren
2.4 Das A*-Suchverfahren
03.05.201301:40:13203
Suchverfahren und Kürzeste Wege in Graphen --- Zusammenhang und Flussoptimierung
2. Suchverfahren und Kürzeste Wege in Graphen:
2.4 Das A*-Suchverfahren
3. Zusammenhang und Flussoptimierung:
3.1 Bestimmung von Zusammenhangskomponenten:
3.1.1 (Reflexiv-)Transitive Hülle
3.1.2 Tripelalgorithmus
10.05.201301:39:18184
Zusammenhang und Flussoptimierung
3. Zusammenhang und Flussoptimierung:
3.1 Bestimmung von Zusammenhangskomponenten:
3.1.2 Tripelalgorithmus
3.1.3 Reduzierte Graphen
Exkurs - Lineare Optimierung und Dualität
3.2 Maximale Flüsse:
3.2.1 Beispiel und Definition
3.2.2 Der \"max-flow = min-cut\" Satz
17.05.201301:28:51188
Zusammenhang und Flussoptimierung
3. Zusammenhang und Flussoptimierung:
3.2 Maximale Flüsse:
3.2.2 Der \"max-flow = min-cut\" Satz
3.2.3 Der Algorithmus von Ford-Fulkerson
3.2.4 Matching und Cover in bipartiten Graphen
31.05.201301:34:17239
Zusammenhang und Flussoptimierung
3. Zusammenhang und Flussoptimierung:
3.2 Maximale Flüsse:
3.2.4 Matching und Cover in bipartiten Graphen
3.3 Flüsse mit minimalen Kosten:
3.3.1 Beispiel und Definition
3.3.2 Netzwerk-Simplex-Verfahren
04.06.201301:34:05207
Zusammenhang und Flussoptimierung
3. Zusammenhang und Flussoptimierung:
3.3 Flüsse mit minimalen Kosten:
3.3.2 Netzwerk-Simplex-Verfahren
07.06.201301:49:13154
Zusammenhang und Flussoptimierung
3. Zusammenhang und Flussoptimierung:
3.3 Flüsse mit minimalen Kosten:
3.3.2 Netzwerk-Simplex-Verfahren
3.4 Kanten- und Knotenzusammenhang
21.06.201301:43:21122
Signierte Graphen
4. Signierte Graphen:
4.1 Balance
4.2 Cluster
26.06.201301:42:09129
Signierte Graphen --- Planare Graphen und Färbungen
4. Signierte Graphen:
4.2 Cluster
5. Planare Graphen und Färbungen:
5.1 Planare Graphen
5.2 Färbungen
27.06.201301:42:22107
Planare Graphen und Färbungen
5. Planare Graphen und Färbungen
28.06.201301:44:42117
Graphoptimierung
6. Graphoptimierung:
6.2 Greedy-Algorithmus
6.3 Minimale Spannbäume
6.4 Überdeckungen
6.5 Heuristiken
03.07.201301:16:4278
Graphoptimierung
6. Graphoptimierung:
6.6 Optimale Zentren: Das p-Zentren-Problem