Datenstrukturen III

Question 1

Pfadsuchprobleme

Answer 1

Suche nach

• geschlossenem Pfad durch gegebene Knoten
• billigsten Pfad - “ -
• billigster Rundreise

Question 2

Eulerscher Pfad

Answer 2

• Pfad, der alle Kanten umfasst und jede genau einmal durchläuft

Question 3

Eulerscher Zyklus

Answer 3

• Eulerscher Pfad, bei dem Start- und Endknoten identisch sind

⇒ gdw. Grad jedes Knotens durch 2 teilbar ist und Graph zusammenhängend ist

Question 4

Hamiltonscher Zyklus/Kreis

Answer 4

• Zyklus, der jede Ecke genau einmal enthält
• komplexer als Eulerkreisproblem (O(m!))

Question 5

Kürzeste Pfade

Answer 5

• Pfadlänge durch Summe der Kantengewichte
• Dijkstra Algorithmus
• Bellman-Ford

Question 6

Dijkstras Algorithmus (1959) - Allgemeines

Answer 6

• basiert auf Greedy-Prinzip (immer das nächstbeste nehmend) und auf
• Weiterentwicklung der Breitensuche
• Iterative Vorgehensweise: Nehme immer die am “billigsten” zu erreichende Kante

Question 7

Dijkstras Algorithmus - Voraussetzngen

Answer 7

• Gerichtete Graphen; falls ungerichtet, ersetze jede Kante durch zwei gerichtete Kanten
• Positive Kantengewichte
• In gerichteten Graphen gilt, dass der kürzeste Pfad von v nach w der gleiche ist, wie der von w nach v.

Question 8

Dijkstras Algorithmus (1959) - Vorgehensweise

Answer 8

• Startknoten mit D(j)=0, Rest D(j)=∞
• Greedy-Prinzip
• wenn mehrere Knoten mit gleichem D(j), wähle Knoten mit kleinstem Index

⇒ nur bei positiven Kantengewichten

⇒ ermittelt nur die Distanz

Question 9

Bellman-Ford Algorithmus - Allgemeines

Answer 9

• Kürzeste Pfade zu allen anderen Knoten
• auch negative Kantengewichte
• negativer Zyklus → Algo terminiert nicht

Question 10

Bellman-Ford Algorithmus - Vorgehensweise

Answer 10

• Startknoten s, #Interationsschritte = |N| −1
• Startknoten mit D(j)=0, Rest D(j)=∞
• Ausgehend von s Betrachtung aller Pfade der Länge 1,2,…,|N|-1
• Pfade der Länge i werden in Iterationsschritt i betrachtet.
• nehme bei allen Pfade einer Länge kürzeste Weglänge zu Endstück
• Der längste Pfad ohne Zyklus hat maximal eine Länge von |N|-1

Question 11

Minimaler Spannbaum

Answer 11

• Gegeben: Ein ungerichteter Graph mit Kantengewichten
• Gesucht: Zusammenhängender Teilgraph, der alle Knoten enthält und Summe der Kantengewichte ist minimal
• Eigenschaft: Der gesuchte Teilgraph ist azyklisch → Baum
• Spannbaum (spannender Baum): Teilgraph in Form eines Baums, der alle Knoten des Graphen enthält
• Bsp.: Wassernetz
• Kruskal-Algorithmus

Question 12

Algorithmus von Kruskal

Answer 12

• für (min.) Spannbaum
• sortierten Kantenliste in aufsteigender Reihenfolge
• Kante = Lösung, wenn sie zwei verschiedene Bäume verbindet (keinen Zyklus enthält)
• nacheinander betrachten und entscheiden, ob Kante = Lösung

Question 13

Überprüfen, ob Pfad beliebiger Länge vorhanden ist, sodass zwei Elemente verbunden sind

Answer 13

⇒ Matrizenmultiplikation (u.U. wiederholen, aber maximal bis Knotenanzahl)