Grundbegriffe der Graphentheorie 1

Wiki-Quelltext dieser Seite.

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:

[[Bild:Ghx8_;_Wege.png|center|400px]]

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:

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

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:

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

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

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

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

=Planare Graphen - die Eulersche Polyederformel=