Graphen Flashcards
(23 cards)
Tafelübung
Beispiel für Verwendung von Graphen
- Landkarten
- Raumplanung
- Segmentierung von Bildern
- Google (PageRank-Algorithmus)
Tafelübung
Definitionen
(einfacher) Pfad
Folge von Knoten, um von einem Knoten vi
nach Knoten vj zu kommen (bei dem jeder Knoten höchstens
einmal vorkommt = einfach).
Tafelübung
Definitionen
Zyklus
Pfad von vi nach vi
Tafelübung
Definitionen
stark zusammenhängend
In einem gerichteten Graphen kann
jeder Knoten von jedem Knoten aus erreicht werden
Tafelübung
Definitionen
schwach zusammenhängend
In einem gerichteten Graphen
kann jeder Knoten von jedem Knoten aus erreicht werden, wenn
jede gerichtete durch eine ungerichtete Kante ersetzt wird.
Tafelübung
Definitionen
Spannbaum
Ein zusammenhängender, zyklenfreier Teilgraph,
der alle Knoten des Graphen enthält.
Tafelübung
Nachteile Adjazenzmatrix
Kann ziemlich groß werden, nicht sehr effizient bei vielen Knoten und
wenigen Kanten
Tafelübung
Darstellungsformen
Adjazenzmatrix
Adjazenzliste
Kantenliste
Einbettung in ein Feld
Tafelübung
2 Varianten der kürzesten Wege
Single Source Shortest Path, -> Dijkstra
All Pairs Shortest Path
Tafelübung
Zwei Algorithmen für Spannbäume
Algorithmus von Prim:
Der Spannbaum wächst von einem Startknoten aus, indem immer wieder die billigste Kante gewählt wird, die den bisherigen Baum verlässt.
Algorithmus von Kruskal:
Dieser Algorithmus betrachtet den Graphen »von oben« und
wählt immer die billigste Kante, die bisher noch nicht verbundene Teilgraphen verbindet.
KLAUSURAUFGABE SS18
Welche Datenstruktur verwendet man für das Traversieren eines Graphen in Breitensuche?
eigene Lösung
Baum?
KLAUSURAUFGABE WS17
Welche Aussage(n) trifft/treffen auf gerichtete Graphen zu?
- Die Tiefensuche in einem gerichteten Graphen benötigt keine (Hilfs)-
Datenstruktur zur ihrer Implementierung, sondern nutzt implizit den
Aufrufstapel zur Verwaltung der rekursiven Aufrufe. - Das Problem der Ermittlung der kürzesten Rundreise in einem gerichteten
Graphen kann nur mit einen effektiven, aber ineffizienten graphbasierten
Algorithmus gelöst werden. - Der minimale Spannbaum eines gerichteten Graphen ist nie eindeutig,
d. h. es gibt keine gerichteten Graphen, bei denen nur exakt eine Lösung existiert.
- richtig
- falsch
- richtig
KLAUSURAUFGABE SS17
Welche Aussagen zum Thema Graphen sind korrekt?
Der Spannbaum eines Graphen ist eindeutig.
Spannbäume sind immer zyklenfrei.
Der Pfad zwischen zwei Knoten vi und vj heißt einfach, wenn es keinen weiteren Pfad
zwischen vi und vj gibt.
Die Adjazenzmatrix von ungerichteten Graphen ist immer symmetrisch.
- falsch
- richtig
- falsch
- richtig
KLAUSURAUFGABE WS16
Welche Aussagen zum Thema Graphen sind korrekt?
Der Spannbaum eines Graphen ist eindeutig.
Spannbäume sind immer zyklenfrei.
Der Pfad zwischen zwei Knoten vi und vj heißt einfach, wenn es keinen weiteren Pfad
zwischen vi und vj gibt.
Die Adjazenzmatrix von ungerichteten Graphen ist immer symmetrisch.
- falsch
- richtig
- falsch
- richtig
KLAUSURAUFGABE SS16
Woran kann man an einer Adjazenzliste erkennen, ob der damit dargestellte Graph ein (ungerichteter)
einfacher Graph ist, d. h. keine mehrfachen Kanten (zwischen denselben Knoten)
enthält?
eigene Lösung
indem die gleiche Referenz nicht mehrfach in einem Listenteil steht
KLAUSURAUFGABE SS16
Skizzieren Sie (in Worten) einen Algorithmus, der auf möglichst einfache Art überprüft, ob ein
Graph, der mittels Adjazenzlisten gespeichert ist, ein (ungerichteter) einfacher Graph ist, d. h.
keine mehrfachen Kanten enthält.
Ihnen steht O(#knoten) zusätzlicher Speicherplatz zur Verfügung.
Versuchen Sie, mit O(#knoten+#kanten) Zeit auszukommen!
(#knoten ist die Anzahl der Knoten, #kanten die Anzahl der Kanten.)
Hinweis: Auch eine Lösung, deren Laufzeit nicht mehr linear ist, wird gewertet, allerdings nicht
mit der vollen Punktzahl
eigene Lsg
eventuell mit boolean für jede Kante der sich umstellt sobald die Kante das erste Mal gefunden wurde?
Vorlesung
Speicherbedarf von Kantenlisten
explizite Speicherung aller Kanten in einem 2 * m-Feld K (3*m mit Gewichtung)
Speicherbedarf: 2m (3m mit Gewichtung)Speicherplätze
dynamische Anwendungen: Realisierung über verkettete Listen
Vorlesung
Speicherbedarf von Kantenlisten
geringer Speicherbedarf: n + m Einträge
noch kompakter als verkettete Listen: kein Speicherplatz für Zeiger
notwendig
Einfügen und Löschen: aufwändige Änderungen des Feldes notwendig
Vorlesung
Speicherbedarf von Kantenlisten
geringer Speicherbedarf: n + m Einträge
noch kompakter als verkettete Listen: kein Speicherplatz für Zeiger
notwendig
Einfügen und Löschen: aufwändige Änderungen des Feldes notwendig
KLAUSURAUFGABE SS15
Welche Aussage(n) trifft/treffen auf gerichtete Graphen zu?
- Die Tiefensuche in einem gerichteten Graphen benötigt keine (Hilfs)-
Datenstruktur zur ihrer Implementierung, sondern nutzt implizit den
Aufrufstapel zur Verwaltung der rekursiven Aufrufe. - Das Problem der Ermittlung der kürzesten Rundreise in einem gerichteten
Graphen kann nur mit einen effektiven, aber ineffizienten graphbasierten
Algorithmus gelöst werden. - Der minimale Spannbaum eines gerichteten Graphen ist nie eindeutig,
d. h. es gibt keine gerichteten Graphen, bei denen nur exakt eine Lösung existiert.
eigene Lösung
- richtig
- richtig?
- falsch
KLAUSURAUFGABE SS15
Welche Aussage(n) trifft/treffen auf gerichtete Graphen zu?
- Die Tiefensuche in einem gerichteten Graphen benötigt keine (Hilfs)-
Datenstruktur zur ihrer Implementierung, sondern nutzt implizit den
Aufrufstapel zur Verwaltung der rekursiven Aufrufe. - Das Problem der Ermittlung der kürzesten Rundreise in einem gerichteten
Graphen kann nur mit einen effektiven, aber ineffizienten graphbasierten
Algorithmus gelöst werden. - Der minimale Spannbaum eines gerichteten Graphen ist nie eindeutig,
d. h. es gibt keine gerichteten Graphen, bei denen nur exakt eine Lösung existiert.
- richtig
- falsch
- richtig
KLAUSURAUFGABE SS15
Welche Aussage(n) trifft/treffen auf gerichtete Graphen zu?
- Die Tiefensuche in einem gerichteten Graphen benötigt keine (Hilfs)-
Datenstruktur zur ihrer Implementierung, sondern nutzt implizit den
Aufrufstapel zur Verwaltung der rekursiven Aufrufe. - Das Problem der Ermittlung der kürzesten Rundreise in einem gerichteten
Graphen kann nur mit einen effektiven, aber ineffizienten graphbasierten
Algorithmus gelöst werden. - Der minimale Spannbaum eines gerichteten Graphen ist nie eindeutig,
d. h. es gibt keine gerichteten Graphen, bei denen nur exakt eine Lösung existiert.
- richtig
- falsch
- richtig
KLAUSURAUFGABE SS14
Führe den folgenden Schritt so oft wie möglich aus: Wähle unter den noch nicht ausgewählten
Kanten von G (dem Graphen) die kürzeste Kante, die mit den schon gewählten
Kanten keinen Kreis bildet.
- Nach wem ist dieser Algorithmus benannt?
- Ist das Ergebnis des Algorithmus zwingend eindeutig? Begründen Sie Ihre Antwort.
- Welche Laufzeitkomplexität hat der Algorithmus? Begründen Sie Ihre Antwort.
Eigene Lösung
- Kruskal
- nein
- n log n??
