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:
Abb.: Verschiedene Darstellungen des Weges.
- besonders wichtig sind die Wege als Teilgraphen eines größeren Graphen (siehe Abb.???)
- Beschreibung des Weges durch Benennung der Knoten
Abb.??? Teilgrap (3,2,1,4,5).
Zusammenhang bei Graphen
Definition:
- zwischen zwei verschiedenen Knoten/Endknoten gibt es einen Weg
- Endknoten müssen verschieden sein, sonst erhält man Kreise
Beispiel:
Kreise
Definition:
- Endknoten müssen verschieden sein, sonst erhält man Kreise
- Kreise können auch Teilgraphen sein (Abb.???)
Beispiel:
Abb.: Kreis als Teilgraph
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:
