Ralf Zücker, Frank Ehrlich

Wege und Kreise

bla

Was ist ein Weg?

Ein Weg ist ein Graph, der aus aneinander gehängten Kanten besteht. Damit gibt es bei einem Weg zwei ausgezeichnete Knoten.

Definition:

Für n ≥ 2 nennt man einen Graphen Pn mit der Knotenmenge V (Pn) = {v0,v1,...,vn} und der Kantenmenge E(Pn) = {{v0,v1},{v1,v2},...,{vn−1,vn}} einen Weg (oder Pfad) der Länge n, sofern keine Kante mehrfach durchlaufen wird. Knoten hingegen dürfen bei einem Weg mehrfach vorkommen (d. h. die Knoten vi müssen nicht notwendig paarweise verschieden sein). Lässt man auch mehrfach durchlaufene Kanten zu, so spricht man von einem Kantenzug. Eine häufig genutzte Notation für einen solchen Weg ist die Tupelschreibweise seiner Knoten mithilfe runder Klammern: Pn = (v0,v1,...,vn). Meist fordert man zusätzlich explizit, dass v0 = vn gelten muss, der Weg also offen ist.

Beispiel:

Zusammenhängend

Definition:

Ein Graph G ist zusammenhängend, wenn es zwischen zwei verschiedenen Knoten v,w ∈ V (G) einen Weg auf G mit v und w gibt. Ein maximaler zusammenhängender Teilgraph von G heißt Zusammenhangskomponente von G.

Beispiel:

Wege fassen wir in der Regel immer als offen auf, was bedeutet, dass ihre Endpunkte stets verschieden sind. Lässt man diese Bedingung fallen, so erhält man geschlossene Wege oder Kreise.

Kreise

Definition:

Für n ≥ 3 heißt der Graph Cn mit V (Cn) = {v0,v1,...,vn = v0} und E(Cn) = {{v0,v1},{v1,v2},...,{vn−1,v0}} Kreis der Länge n.

Kreise können auch Teilgraphen anderer Graphen G sein. Die untere Abbildung zeigt eine Darstellung des C4 und eine Darstellung eines C4 auf einem größeren Graphen (fett dargestellt).

Beispiel:

Operationen mit Graphen

bla

Entfernen von Knoten und Kanten

bla

Fusion und Kontraktion

bla

Brücken und Artikulationen

bla

Operationen mit Graphen

Vollständige Graphen

Der vollständige Graph bildet bei einer Reihe von Problemen die Grundlage der Modellierung.

Definition:

Ein Graph, bei dem je zwei Knoten benachbart sind, heißt vollständig. Für n ≥ 2 bezeichnen wir den vollständigen Graphen auf n Knoten mit Kn.

Beispiel:

Der Übergang von Kn−1 zu Kn erfordert n − 1 neue Kanten, denn der hinzugefügte Knoten ist mit jedem der bisher n − 1 vorhandenen Knoten zu verbinden. Damit erhält man für die Kantenanzahl des Kn die Summe der Zahlen bis n −1:

Anzahl der Kanten eines vollständigen Graphen wächst damit quadratisch in der Knotenanzahl.

Kantenanzahl

xkdkf

Matrix

Die Information, welche Kanten und Knoten eines Graphen inzident sind, wodurch der Graph ja vollständig beschrieben ist, kann man sehr einfach in Matrizen kodieren. Man spricht dannvon der Adjazenzmatrix bzw. von der Inzidenzmatrix eines Graphen.

Die jeweils genaue Gestalt der Matrizen hängt von der Nummerierung der Knoten und Kanten ab.

Beispiel:

Adjazenzmatrix

Definition:

Bei einem Graph mit der Knotenmenge V = {v1,...,vn} und der Kantenmenge E = {e1,...,em} verstehen wir unter der Adjazenzmatrix von G die (n × n)-Matrix A(G), deren Eintrag an der Stelle (i, j) gleich der Anzahl der Kanten zwischen den Knoten vi und vj ist.

Beispiel:

Die Adjazenzmatrix eines Graphen

bla

Potenzen der Adjazenzmatrix

bla

Zerlegbare Matrizen

bla

Inzidenzmatrix

Definition:

Bei einem Graph mit der Knotenmenge V = {v1,...,vn} und der Kantenmenge E = {e1,...,em} verstehen wir unter der Inzidenzmatrix von G die (n × m)-Matrix I(G), deren Eintrag an der Stelle (i, j) gleich 1 ist, wenn der Knoten vi zur Kante ej gehört, und andern- falls gleich 0.

Beispiel:

Gradmatrix

bla

Abstände in Graphen

bla

Radius, Durchmesser und Zentrum

bla

Die Abstandsmatrix

bla

Gerüste

bla

Die Anzahl der Gerüste

bla

Die Admittanzmatrix und der Satz von Kirchhoff

bla

Teilgraph

Definition:

Es sei G = (VG ,EG ) ein Graph. Ein Teilgraph von G ist ein Graph H = (VH ,EH ), dessen Kno- tenmenge VH eine Teilmenge von VG und dessen Kantenmenge EH eine Teilmenge von EG ist. Wir nennen einen Teilgraphen H ⊆ G darüber hinaus induziert, falls mit jedem Knoten v von H auch sämtliche mit v inzidenten Kanten zu H gehören.

Beispiel: