Kapitel 7: Graphen Flashcards
Definition Graph
Ein Graph G=(V,E) besteht aus einer menge von Knoten (vertices) V und einer Menge von Kanten (edges) E, die jeweils zwei Knoten miteinander verbinden.
Was bedeutet V bei Graphen ?
Vertices / Knoten
Was bedeutet E bei Graphen ?
Edges / Kanten
Was bedeutet gerichtet bei Graphen ?
Graphen bestehen aus Kanten aus geordneten Paaren (v,w) != (w,v)
Was bedeutet gewichtet bei Graphen ?
Die Kantenverbindungen der Graphen sind bewertet (mit einer Zahl)
Wann ist ein Knoten adjazent ?
Ein Knoten w ist adjazent (benachbart) zu v genau dann, wenn (v,w) existiert.
Was ist IVI bei Graphen ?
Anzahl der Knoten
Was ist IEI bei Graphen ?
Anzahl der Kanten
Was bedeutet adjazent ?
benachbart
Was ist eine reflexive Kante ?
Eine reflexive Kante (self-loop), auch Schlinge genannt, ist eine Kante, die einen Knoten mit sich selbst verbindet.
Wie nennt man auch Self-loops bei Graphen ?
reflexive Kanten
Was charakterisiert Multigraphen ?
parallele Kanten sind vorhanden
Was charakterisiert einfache Graphen ?
Graphen ohne parallele oder reflexive Kanten
Was ist ein Pfad bei Graphen ?
Ein Pfad in einem Graphen besteht aus einer Folge von Knoten, die durch Kanten verbunden sind. In einem einfachen Pfad kommt jeder Knoten nur einmal vor.
Was ist ein Zyklus ?
Ein Zyklus ist ein Pfad, der im selben
Knoten beginnt und endet.
Was ist ein einfacher Zyklus ?
Als einfachen Zyklus wird ein Zyklus bezeichnet, bei dem sich keine Kanten und Knoten wiederholen (bis auf den ersten und den letzten Knoten).
Was ist die Länge eines Pfades oder eines
Zyklus ?
die Anzahl der Kanten.
Wann ist ein Graph zusammenhängend ?
wenn es von jedem Knoten aus einen
Pfad zu allen anderen Knoten im
Graphen gibt.
Wann ist ein Graph stark zusammenhängend ?
wenn im
Graphen von jedem Knoten zu jedem
anderen Knoten eine Kante existiert.
Wie heißt ein Graph ohne Zyklen ?
azyklischer Graph
Welche Graphen-Eigenschaften werden durch einen Baum repräsentiert ?
- azyklischer Graph
- zusammenhängender graph
Was ist ein Spannbaum eines
zusammenhängenden Graphen ?
ein Teilgraph, der alle Knoten des
Graphen enthält und ein Baum ist.
(aber nicht alle Kante)
Was charakterisiert einen Wald ?
eine disjunktive (einander ausschließende) Menge von Bäumen
Was ist ein Spannwald eines nicht (!)
zusammenhängenden Graphen
die Vereinigung der Spannbäume
seiner Zusammenhangskomponenten.
Was gibt die Dichte eines Graphen an ?
wie viele der möglichen Knotenpaare
tatsächlich durch Kanten verbunden sind.
Was ist ein dünner Graph ?
hat wenige der möglichen Kanten miteinander verbunden
Was ist ein dichter Graph ?
fehlen nur wenige der
möglichen Kanten
Was ist ein bipartiter Graph ?
ein Graph, dessen Knoten in zwei Mengen aufgeteilt werden können, wobei jede Kante jeweils einen Knoten der einen Menge mit einem Knoten der anderen Menge verbindet.
(Rot Schwarz)
Was ist die Speicherung der Kantenliste ?
G[0] = lVl
G[1] = lEl
anschließend kommen die paare
z.b. { 6,11,1,2,1,3..}
Kantenliste interpetieren
{ 6,11,1,2,1,3..}
- 6 Knoten
- 11 Kanten und einer
- Verbindung von 1-2
- Verbindung von 1-2 1-3
Was ist bei der Speicherung in Form einer Kantenliste bei unterrichteten Graphen zu achten
die Kante von v zu w muss doppelt gespeichert werden
v,w) und (w,v
Speicheraufwand Kantenliste
2+2*E
Was ist die Speicherung der Knotenliste ?
G[0] = lVl
G[1] = lEl
zudem
- Anzahl ausgehend Kanten
- Und Zile der Kanten
z.b. { 6,11,2,2,3,0,3,1,4,6}...Knotenliste interpetieren
z.b. { 6,11,2,2,3,0,3,1,4,6}…
- 6 Knoten
- 11 Kanten und einer
- 2 Verbindung vom 1. Knoten zu K2 und K3
- 0 Verbindung vom 2. Knoten
- 3 Verbindung vom 3. Knoten zu K1, K4 und K6
Speicheraufwand Knotenliste
2 + lVl + lEl
Bei dichten Graphen benötigt welche Datenstruktur weniger Speicher ?
Knotenliste
Wie liest man die Adjazenzmatrix ?
Zeilen = von Knoten
Spalten = nach Knoten
Dort wo eine 1 steht gibt es die Verbindung
Eigenschaft der Adjazenzmatrix bei ungerichteten Graphen ?
Symmetrische Matrix (gespiegelt da G(v,w) = G(w,v))
Speicheraufwand Adjazenzmatrix
lVl * lVl
Für wann ist die Adjazenzmatrix geeignet ?
für dichte Graphen
Was ist die Adjazenzliste ?
Vector der Knoten: jedes Element enthält einen weiteren Vector der die adjazenzten Knoten enthält
Speicheraufwand Adjazenzliste
lVl + lEl
Was ist der Grad (bzw. die Valenz) eins Knotens ?
Dabei ist dG(v) in Graphen ohne Mehrfachkanten und Hypergraphen die Anzahl der Nachbarn von v, Graphen mit Mehrfachkanten die Summe der Vielfachheiten aller mit v inzidenten Kanten.
Welche Grade gibt es noch bei Graphen ?
Minimalgrad, Maximalgrad , Durchschnittsgrad
Formel Durchschnittsgrad eines Graphen
2 * lEl / lVl
Mit welchem Aufwand kann eine Kante (v,w) bei einem Graph hinzugefügt werden ?
1
Aufwand : prüfen ob w Nachbar von v ist : Kantenliste
E
Aufwand : prüfen ob w Nachbar von v ist : Adjazenzmatrix
1
Aufwand : prüfen ob w Nachbar von v ist : Adjazenzliste
degree(v)
Aufwand : Über Nachbarknoten von v iterieren: Kantenliste
E
Aufwand : Über Nachbarknoten von v iterieren: Adjazenzmatrix
V
Aufwand : Über Nachbarknoten von v iterieren: Adjazenzliste
degree(v)
Was ist die Methode von Tremaux ?
Erkunde alle Wege eines Labyrinths - Rolle Faden hinterher - markiere alle Kreuzungen und Wege, wenn sie das erste Mal betreten werden - gehe mithilfe des Fadens zurück, wenn man an eine markierte Kreuzung kommt. - Gehe noch weiter zurück, wenn man beim Zurückgehen an eine Kreuzung kommt, deren Wege bereits alle besucht wurden.
Verfahren der Tiefensuche
- Markiere alle Knoten v E V als nicht besucht.
- Wähle einen nicht besuchten Knoten v E V und markiere diesen als besucht.
- Besuche (rekursiv) alle benachbarten Knoten w von v, die noch nicht markiert sind und führe für diesen Knoten die Tiefensuche durch.
Conncected Components: Wie überprüfe ich ob v und w verbunden sind ?
id[v] == id[w]
Connected Components: was bedeutet
id[2] = 0 und id[3] = 1
der dritte Knoten ist in einem anderen Teilgraphen als der vierte Knoten (unzusammenhängende Graphen)
Connected Components: Aus wie vielen Zusammenhangskomponenten besteht der Graph?
count +1
Vorteil Breitensuche
Die Breitensuche liefert für alle verbundenen Knoten die kürzesten Pfade. Der Suchbaum hat somit die geringste Höhe.
was bedeutet MST ?
minimum spanning tree
Definition Minimaler Spannbaum
Der minimale Spannbaum eines kantengewichteten Graphen ist ein Spannbaum, dessen Summe seiner Kantengewichte minimal ist gegenüber irgendeines anderen Spannbaums.
(möglichst wenig Kanten um alle Knoten miteinander zu verbinden)
Was ist der Prim Algorithmus ?
- Startknoten für MST auswählen
- immer günstigste Kante auswählen (erweitern)
- nach lVl-1 Kanten ist der MST gefunden
Welche DS benutzt der Prim Algorithmus ?
Knoten: knotenindiziertes boolsches Array
Kanten : Warteschlange mst und Array
Randkanten: Prioritätswarteschlange
Was sind Randkanten ?
Randkanten sind die Menge der adjazenten Kanten, die den Baum um einen nicht besuchten Knoten erweitern. Dafür wird eine
Aufwand Prim Algorithmus
ungefähr O(E*logE)
Was ist der Algorithmus von Kruskal ?
- Sortiere die Kanten nach ihren Gewichten.
- Verarbeite die Kanten in der Reihenfolge ihrer Gewichte (vom kleinsten zum größten).
- Nehme immer eine Kanten zum MST hinzu, wenn dadurch kein Zykel im Baum entsteht.
- Nach V - 1 Kanten ist der MST gefunden.
Definition (Gerichteter Graph (Digraph))
besteht aus
- einer Menge von Knoten
- einer Menge von gerichteten Kanten
Jede gerichtete Kante verbindet ein geordnetes Paar von Knoten.
Definition (Kürzester Pfade mit einem Startknoten)
Ein Kürzester Pfad von einem Knoten s zu einem Knoten t in einem kantengewichteten Digraphen ist ein gerichteter Pfad von s zu t mit der Eigenschaft, dass kein anderer Pfad ein niedrigeres Gewicht hat.
Was ist ein Digraph ?
Ein Gerichteter Graph
Definition (Kürzeste Pfade Baum)
Ein Kürzester-Pfade-Baum für einen Startknoten s ist ein Teilgraph, der s und alle von s aus erreichbaren Knoten enthält, die einen gerichteten Baum mit der Wurzel s bilden, so dass jeder Baumpfad ein kürzester Pfad im Digraphen ist.
Was ist eine Kantenrelaxation ?
Eine Kante v -> w wird relaxiert, wenn der kürzeste Weg von s nach w über die Kante von v nach w verläuft.
Alternative: Ein Knoten w wird relaxiert, wenn der kürzeste Weg von s über die Kante v -> w zum Knoten w verläuft.
Was berechnet der Dijkstra Algorithmus?
einen Kürzeste-Pfade-Baum (SPT)
Laufzeit Dijkstra
ungefähr O(ElogV)
Speicher Dijkstra und Prim
Ungefähr O(V)
