Kurs:Algorithmen und Datenstrukturen/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 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\ne v_j\text{ für alle }i,j=1,...,n\text{ mit }i\ne 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\ne v_j\text{ für alle }i,j=1,...,n-1\text{ mit }i\ne 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^{\prime }=(V^{\prime },E^{\prime })$ heißt Teilgraph von G, falls $V^{\prime }\subseteq V\text{ und }{E}^{\prime }\subseteq E\cap (V^{\prime }\times V^{\prime })$.

Beispiel:

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

Gerichteter Graph

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

Beispiel:

• $G^{\prime }=(\{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^{\prime }=(V^{\prime },E^{\prime })$ von G heißt Zusammenhangskomponente von G, falls G' zusammenhängend ist und kein Teilgraph $G^{″}=(V^{″},E^{″})$ von G existert mit $V^{\prime }\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\},\mathrm{\varnothing })$ 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^{\prime }=(V^{\prime },E^{\prime })$ von G heißt starke Zusammenhangskomponente von G, falls $G^{\prime }$ stark zusammenhängend ist und kein Teilgraph $G^{″}=(V^{″},E^{″})$ von G existiert mit $V^{\prime }\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$.