Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Definitionen zu Graphen

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 heißt 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}$ .