Graphen Flashcards
Ungerichtete Graphen
G = (V, E) V = Menge der Knoten (vertices, nodes). E = Menge der Kanten zwischen Paaren von Knoten (edges). Parameter fur Größen: n = |V |, m = |E| n - knoten m - kanten
handshaking lemma
Für ungerichtete Graphen gilt:
Es gilt: (summezeichen)v∈V
deg(v) = 2 · | E | (Handshaking-Lemma).
Schleife:
Eine Kante, die einen Knoten mit sich selbst
verbindet.
Adjazenzmatrix:
- Zwei Einträge fur jede ungerichtete Kante.
- Fur gewichtete Graphen: Reele Matrix statt Boolesche Matrix
- Platzbedarf in Θ(n^2).
- Uberprüfen, ob (u, v) eine Kante ist, hat Laufzeit Θ(1).
- Aufzählen aller Kanten hat eine Laufzeit von Θ(n^2).
Adjazenzlisten:
- Zwei Einträge fur jede Kante
- Fur gewichtete Graphen: Speichere Gewicht in Liste
- Platzbedarf in Θ(m + n).
- Uberprüfen, ob (u, v) eine Kante ist, hat eine Laufzeit von
O(deg(u)). - Aufzählen aller Kanten hat eine Laufzeit von Θ(m + n)
Kantenanzahl:
Ein Graph kann bis zu m =n(n−1)/2 =(n über 2) = Θ(n^2) viele Kanten enthalten
Graphen sind dicht (dense)
falls m = Θ(n^2).
Graphen sind licht (sparse)
falls m = O(n)
Pfad
Ein Pfad in einem ungerichteten Graphen G = (V, E)
ist eine Folge von Knoten v1, v2, . . . , vk−1, vk, k ≥ 1, mit der Eigenschaft, dass jedes aufeinanderfolgende Paar vi
, vi+1 durch
eine Kante in E verbunden ist. Die L¨ange des Pfades ist k − 1.
Graph ist zusammenhängend
Ein ungerichteter Graph ist zusammenhängend, wenn
jedes Paar von Knoten u und v von einander erreichbar ist.
Pfade in gerichteten Graphen
Ein Pfad in einem gerichteten Graphen G = (V, E) ist eine
Folge von Knoten v1, v2, . . . , vk−1, vk, k ≥ 1, mit der Eigenschaft,
dass jedes aufeinanderfolgende Paar vi
, vi+1 durch eine gerichtete
Kante (vi, vi+1) in E verbunden ist.
Baum
Ein ungerichteter Graph ist ein Baum, wenn er
zusammenhängend ist und keinen Kreis enthält.
Baum theorem
Sei G ein ungerichteter Graph. G ist ein Baum genau
dann wenn es fur jedes Paar von Knoten ¨ u und v genau eine Pfad
von u nach v gibt.
Beweis: G ist zusammenhängenden genau dann wenn es fur jedes ¨
Paar von Knoten u und v mindestens einen Pfad von u nach v
gibt. G enthält keinen Kreis, genau dann wenn es fur jedes Paar ¨
von Knoten u und v maximal einen Pfad von u nach v gibt.
Breitensuche
BFS Ansatz: Untersuche alle Knoten von einem Startknoten s
ausgehend in alle m¨oglichen Richtungen, wobei die Knoten Ebene
fur Ebene abgearbeitet werden.
BFS hat eine Laufzeit von O(m + n)
Tiefensuche (Depth First Search, DFS)
DFS Ansatz: Von einem besuchten Knoten u wird zuerst immer zu
einem weiteren noch nicht besuchten Nachbarknoten gegangen
(DFS-Aufruf), bevor die weiteren Nachbarknoten von u besucht
werden.
DFS hat eine Laufzeit von O(m + n)
Zusammenhang (Wiederholung)
Ein ungerichteter Graph ist
zusammenhängend, wenn fur jedes Paar von Knoten u und v ein
Pfad zwischen u und v existiert.
Nicht zusammenhängend:
Gibt es zwischen einem Paar von Knoten
keinen Pfad, dann ist der Graph nicht zusammenhängend.
Zusammenhangskomponente:
Einen maximalen
zusammenhängenden Teilgraphen eines beliebigen Graphen nennt
man Zusammenhangskomponente. Ein nicht zusammenhängender
Graph zerf¨allt in seine Zusammenhangskomponenten.
Zusammenhangskomponenten zählen
Die Laufzeit liegt in O(n + m).
Kürzester Pfad:
Kurzester Pfad = Pfad mit den geringsten Kosten, wobei
die Kosten eines Pfades die Summe der Gewichte seiner Kanten
sind
Priority Queue:
- Eine Priority Queue ist eine Datenstruktur, die eine Menge S
von Elementen verwaltet. - Jedes Element v ∈ S hat einen dazugehörigen Wert i, der die
Priorität von v beschreibt.
*Kleinere Werte repräsentieren höhere Prioritäten.
Operationen: Alle mit Laufzeit in O(log n).
* Einfugen eines Elements in die Menge S.
* Löschen eines Elements aus der Menge S.
* Finden eines Elements mit dem kleinsten Wert (höchster
Priorität).
Heap закономерность Nachfolger
Linkenachfolger это всегда индекс актуального элемента умноженный на два
Rechtenachfolger это индекс актуального элемента умноженный на два плюс 1
Elternknoten befindet sich an der Position [k/2]
*Damit obige Rechnung immer funktioniert, wird das Array ab
Index 1 belegt.
*Wurde man bei Index 0 anfangen, dann würden sich die Berechnungen folgendermaßen ändern: Nachfolger links auf
2k + 1, Nachfolger rechts auf 2k + 2, Elternknoten auf [k−1/2]
