Grundbegriffe der Graphentheorie 1
Inhaltsverzeichnis |
Ralf Zücker, Frank Ehrlich
Wege und Kreise
Was ist ein Weg?
- aneinander gehängten Kanten, welche zwei Endknoten besitzen
- Kanten dürfen nicht zweimal durchlaufen werden
- Knoten dürfen hingegen mehrfach vorkommen
- die Knotenabzahl ist dabei um 1 höher als die Kantenanzahl (siehe Abb.???)
Beispiel:
- besonders wichtig sind die Wege als Teilgraphen eines größeren Graphen (siehe Abb.???)
- Beschreibung des Weges durch Benennung der Knoten
Abb.??? (3,2,1,4,5)
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
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:
