Kurs:Algorithmen und Datenstrukturen/Vorlesung/Definitionen zu Graphen

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

Definitionen

Hier werden allgemeine Definitionen bezüglich der Graphen behandelt. Dazu werden immer wieder Beispiele gebracht, die sich auf folgende Graphen beziehen. Dabei gilt je nach Beispiel G=(V,E) entweder für den ungerichteten oder den gerichteten Graphen.

Adjazenz

Ungerichteter Graph

Zwei Knoten $v,w\in V$ heißen adjazent, falls $\{v,w\}\in E$.

Hier heißt v auch Nachbar von w.

Beispiel:

• Knoten 1 und 3 sind adjazent

Gerichteter Graph

Zwei Knoten $v,w\in V$ heißen adjazent, falls $(v,w)\in E$ oder $(w,v)\in E$.

Für $(v,w)\in E$ heißt w Nachfolger von v und v Vorgänger von w.

Beispiele:

• Knoten 1 ist Vorgänger zu Knoten 3
• Knoten 4 ist Nachfolger zu Knoten 6

Inzidenz

Ungerichteter Graph

Eine Kante $\{v,w\}\in E$ ist inzident zu einem Knoten $z\in V$, falls $v=z$ oder $w=z$.

Gerichteter Graph

Eine Kante $(v,w)\in E$ ist inzident zu einem Knoten $z\in V$, falls $v=z$ oder $w=z$.

Grad

Ungerichteter Graph

Der Grad (engl. degree) eines Knotens $v\in V$ ist die Anzahl seiner inzidenten Kanten, das heißt: $degree(v)=|\{\{w,x\}\in E|w=v{\text{ oder }}x=v\}|$.

Beispiel:

• Der Grad von Knoten 4 ist 3

Gerichteter Graph

Der Eingangsgrad (engl. in-degree) eines Knotens $v\in V$ ist die Anzahl seiner Vorgänger: $indeg(v)=|\{(w,v)\in E\}|$.

Der Ausgangsgrad (engl. out-degree) eines Knotens $v\in V$ ist die Anzahl seiner Nachfolger: $outdeg(v)=|\{(v,w)\in E\}|$.

Beispiele:

• Der Eingangsgrad von Knoten 3 ist 2
• Der Ausgangsgrad von Knoten 3 ist 3

Weg

Ungerichteter Graph

Ein Weg W ist eine Sequenz von Knoten $W=(v_{1},...,v_{n})$ mit $v_{1},...,v_{n}\in V$ für die gilt: $\{v_{i},v_{i+1}\}\in E{\text{ für alle }}i=1,...,n-1$

Beispiel:

• (1,3,5,6,3,4) ist ein Weg

Gerichteter Graph

Ein (gerichteter) Weg W ist eine Sequenz von Knoten $W=(v_{1},...,v_{n}){\text{ mit }}v_{1},...,v_{n}\in V{\text{, für die gilt: }}(v_{i},v_{i+1})\in E{\text{ für alle }}i=1,...,n-1$.

Beispiel:

• (1,3,6,5,5,3,1) ist ein (gerichteter) Weg

Pfad

Ein Weg W heißt Pfad, falls zusätzlich gilt $v_{i}\neq v_{j}{\text{ für alle }}i,j=1,...,n{\text{ mit }}i\neq j$. Das heißt, der Weg enthält keine doppelten Knoten. Diese Definition gilt sowohl für ungerichtete als auch gerichtete Graphen.

Beispiel:

• (1,4,6,5) ist ein Pfad

Kreis

Ein Weg P heißt Kreis, falls $v_{1}=v_{n}$. Dazu ist ein Kreis K elementar, falls $v_{i}\neq v_{j}{\text{ für alle }}i,j=1,...,n-1{\text{ mit }}i\neq j$. Der Kreis enthält also keine doppelten Knoten bis auf den Anfangs- und den Endpunkt. Diese Definition gilt sowohl für ungerichtete als auch gerichtete Graphen.

Beispiel:

• (1,3,4,6,3,4,1) ist ein Kreis
• (3,4,6,3) ist ein elementarer Kreis

Länge

Die Länge eines Weges ist die Anzahl der durchlaufenen Kanten. Die Länge eines Pfades ist also n-1. Diese Definition gilt sowohl für ungerichtete als auch gerichtete Graphen.

Beispiel:

• Die Länge von (3,4,6,3,4,1) ist 4
• Die Länge von (1,3,6) ist 2

Teilgraph

Ungerichteter Graph

Ein Graph $G'=(V',E')$ heißt Teilgraph von G, falls $V'\subseteq V{\text{ und }}E'\subseteq E\cap (V'\times V')$.

Beispiel:

• G'=({3,4,6},{{3,4},{4,6}}) ist ein Teilgraph von G

Gerichteter Graph

Ein Graph $G'=(V',E')$ heißt Teilgraph von G, falls $V'\subseteq V$ und $E'\subseteq E\cap (V'\times V')$.

Beispiel:

• $G'=(\{1,3,4\},\{(1,3),(4,1)\})$ ist ein Teilgraph von $G_{g}$.

Erreichbarkeit

Ungerichteter Graph

Ein Knoten $w\in V$ heißt erreichbar von einem Knoten $v\in V$, falls ein Weg $W=(v_{1},...,v_{n})$ existiert mit $v_{1}=v$ und $v_{n}=w$.

Beispiele:

• Knoten 6 ist erreichbar von Knoten 1
• Knoten 7 ist nicht erreichbar von Knoten 1

Gerichteter Graph

Ein Knoten $w\in V$ heißt erreichbar von einem Knoten $v\in V$, falls ein Weg $W=(v_{1},...,v_{n})$ existiert mit $v_{1}=v$ und $v_{n}=w$.

Beispiele:

• Knoten 6 ist erreichbar von Knoten 1
• Knoten 5 ist nicht erreichbar von Knoten 2

Zusammenhang

Ungerichteter Graph

G heißt (einfach) zusammenhängend, falls für alle $v,w\in V$ gilt, dass w von v erreichbar ist

Ein Teilgraph $G'=(V',E')$ von G heißt Zusammenhangskomponente von G, falls G' zusammenhängend ist und kein Teilgraph $G''=(V'',E'')$ von G existert mit $V'\subset V''$.

Beispiele:

• G ist nicht zusammenhängend
• Der Teilgraph $G''=(V'',E''){\text{ mit }}V''=\{1,2,3,4,5,6\}{\text{ und }}E''=\{\{1,2\},\{1,3\},\{1,4\},\{2,6\},\{3,4\},\{3,5\},\{3,6\},\{4,6\},\{5,6\}\}$ ist eine Zusammenhangskomponente von G
• Der Teilgraph $G'''=(\{7\},\emptyset )$ ist eine Zusammenhangskomponente von G

Gerichteter Graph

G heißt (stark) zusammenhängend, falls für alle $v,w,\in V$ gilt, dass w von v und v von w erreichbar ist.

Ein Teilgraph $G'=(V',E')$ von G heißt starke Zusammenhangskomponente von G, falls $G'$ stark zusammenhängend ist und kein Teilgraph $G''=(V'',E'')$ von G existiert mit $V'\subset V''$.

Beispiel:

• Der Teilgraph $G''=(V'',E'')$ mit $V''=\{1,3,4,5,6\}$ und $E''=\{(1,3),(3,1),(3,4),(3,6),(4,1),(5,3),(5,5),(6,4),(6,5)\}$ ist eine starke Zusammenhangskomponente von $G_{g}$.