Grundbegriffe der Graphentheorie 1
Inhaltsverzeichnis |
Ralf Zücker, Frank Ehrlich
Definition eines Graphen
Knoten und Kanten
Adjazenz und Inzidenz
Isomorphie
Grad eines Knotens
Definition
Minimum, Maximum und Durchschnitt
Anzahl
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:
Man beachte, dass laut Definiton für den Weg Pn die Knotenmenge aus höchstens n+1 Knoten und die Kantenmenge aus n Kanten besteht. Bild 1.6 zeigt einige Darstellungen des Weges P4; hier wird auch klar, dass die Anzahl der Knoten kleiner sein kann als n +1.
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
Das Entfernen einer Kante e ??? E erzeugt aus G einen neuen Graphen G - e = (V,E\{e}). Wenn F ??? E eine Kantenteilmenge des Graphen G = (V,E) ist, so sei G - F der, der aus G durch Entfernen aller Kanten aus F hervorgeht. Die Reihenfolge des Entfernens der Kanten aus F spielt keine Rolle.
Für einen Knoten v ??? V wird G - v als der Graph definiert, der aus G durch Entfernen des Knotens v hervorgeht. Das Entfernen des Knotens v schließt hierbei das gleichzeitige Entfernen aller zu v inzident Kanten des Graphen ein. Diese Operation wird für eine Knotenteilmenge X???V. Der Graph, der durch Entfernen aller Knoten aus X aus dem Graphen G hervorgeht.
Fusion
Bei der Fusion verschmelzen zwei Knoten u und v eines Graphen G = (V,E). Dieser neue Knoten ist zu allen Kanten inzident, welche vorher einem dieser beiden Knoten als Endknoten hatten.
Beispiel:
Kontrakion
Die Kontraktion einer Kante e = {u,v} eines Graphen ist das Entfernen von e mit der anschließenden Fusion der Endknoten u und v. Der hervorgehende Graph wird als G\e bezeichnet.
Beispiel:
Aussage:
Es sei e = {u,v} eine Kante des Graphen G = (V,E) und s,t ???V. Wenn in G ein Weg von s nach t existiert, so existiert auch in G\e ein Weg von s nach t.
Nachweis:
s,...ej,u,e,v,ek,...,t
dieser Weg. Durch Kontraktion der Kante e fallen die beiden Endknoten u undd v zusammen, wobei der neue Knoten uv entsteht. Dieser ist ej und ek inzident, sodass der Weg in den kürzeren Weg
s,...,ej,uv,ek,...,t
übergeht. Wenn s und t mit u und v übereinstimmen und somit die Endknoten der Kante e sind, so besitzt der entstehende Weg die Länge null.
Folge:
Ein Graph G ist genau dann zusammenhängend, wenn G durch eine Folge von Kontraktionen in einen Graphen mit genau einem Knoten, deren Entfernen aus G den Zusammenhang zerstört.
Brücken und Artikulationen
Es sei c(G) die Anzahl der Komponenten eines Graphen G. Eine Kante e ??? E eines Graphen G = (V,E) mit der Eigenschaften c(G-e)>c(G) heißt eine Brücke von G. Ein Knoten v ??? V mit der Eigenschaft c(G-v)>c(G) heißt eine Artikulation von G. In einem zusammenhängendem Graphen G sind Brücken und Artikulationen genau solche Kanten und Knoten, deren Entfernen aus G den Zusammenhang zerstört.
Beispiel:
Operationen mit Graphen
Das Komplement
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:
| Thema (n) | Anzahl der Kanten des Kn |
|---|---|
| 2 | 1 |
| 3 | 1 + 2 = 3 |
| 4 | 1 + 2 + 3 = 6 |
| 5 | 1 + 2 + 3 + 4 = 10 |
| 6 | 1 + 2 + 3 + 4 + 5 = 15 |
| 7 | 1 + 2 + 3 + 4 + 5 + 6 = 21 |
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:
