Graphen

Question 1

Ungerichtete Graphen

Answer 1

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

Question 2

handshaking lemma

Answer 2

Für ungerichtete Graphen gilt:
Es gilt: (summezeichen)v∈V
deg(v) = 2 · | E | (Handshaking-Lemma).

Question 3

Schleife:

Answer 3

Eine Kante, die einen Knoten mit sich selbst

verbindet.

Question 4

Adjazenzmatrix:

Answer 4

• 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).

Question 5

Adjazenzlisten:

Answer 5

• 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)

Question 6

Kantenanzahl:

Answer 6

Ein Graph kann bis zu m =n(n−1)/2 =(n über 2) = Θ(n^2) viele Kanten enthalten

Question 7

Graphen sind dicht (dense)

Answer 7

falls m = Θ(n^2).

Question 8

Graphen sind licht (sparse)

Answer 8

falls m = O(n)

Question 9

Pfad

Answer 9

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.

Question 10

Graph ist zusammenhängend

Answer 10

Ein ungerichteter Graph ist zusammenhängend, wenn

jedes Paar von Knoten u und v von einander erreichbar ist.

Question 11

Pfade in gerichteten Graphen

Answer 11

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.

Question 12

Baum

Answer 12

Ein ungerichteter Graph ist ein Baum, wenn er

zusammenhängend ist und keinen Kreis enthält.

Question 13

Baum theorem

Answer 13

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.

Question 14

Breitensuche

Answer 14

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)

Question 15

Tiefensuche (Depth First Search, DFS)

Answer 15

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)

Question 16

Zusammenhang (Wiederholung)

Answer 16

Ein ungerichteter Graph ist
zusammenhängend, wenn fur jedes Paar von Knoten u und v ein
Pfad zwischen u und v existiert.

Question 17

Nicht zusammenhängend:

Answer 17

Gibt es zwischen einem Paar von Knoten

keinen Pfad, dann ist der Graph nicht zusammenhängend.

Question 18

Zusammenhangskomponente:

Answer 18

Einen maximalen
zusammenhängenden Teilgraphen eines beliebigen Graphen nennt
man Zusammenhangskomponente. Ein nicht zusammenhängender
Graph zerf¨allt in seine Zusammenhangskomponenten.

Question 19

Zusammenhangskomponenten zählen

Answer 19

Die Laufzeit liegt in O(n + m).

Question 20

Kürzester Pfad:

Answer 20

Kurzester Pfad = Pfad mit den geringsten Kosten, wobei
die Kosten eines Pfades die Summe der Gewichte seiner Kanten
sind

Question 21

Priority Queue:

Answer 21

• 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).

Question 22

Heap закономерность Nachfolger

Answer 22

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]