Grundbegriffe der Graphentheorie 1

Wiki-Quelltext dieser Seite.

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:

[[Bild:Ghx8_;_Wege.png|center|400px]]
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


[[Bild:Ghx8 ;_Wegee.png|center|400px]]
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:

[[Bild:Ghx8 ;_KeinKreis.png|center|400px]]
Abb.: Ein nicht zusammenhängender Graph mit zwei Zusammenhangskomponenten; hier gibt es
beispielsweise zwischen Knoten 4 und Knoten 5 keinen Weg.

==Kreise==
Definition:

* Endknoten müssen verschieden sein, sonst erhält man Kreise 

* Kreise können auch Teilgraphen sein (Abb.???)

Beispiel:

[[Bild:Ghx8 ;_Kreise.png|center|400px]]
Abb.: Kreis als Teilgraph

=Operationen mit Graphen=
bla

==Entfernen von Knoten und Kanten==

* Entfernung einer Kante -> neuer Graph
* Entfernung eines Koten -> neuer Graph, hierbei das gleichzeitige Entfernen aller zu v inzident Kanten des Graphen ein.

==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:

<li>Die Kante e liegt auf dem st-Weg. Es sei

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.

<li>Liegt die Kante e nicht auf dem Weg von s nach t, so bleibt dieser Weg auch in G\e erhalten.

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:

[[Bild:Ghx8 ;_VollstaendigeGraphen.png|center|400px]]

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:


{| class="wikitable"
|-
! 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