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]]


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

==Fusion und Kontraktion==
bla

==Brücken und Artikulationen==
bla

==Operationen mit Graphen==

=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

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

[[Bild:Ghx8 ;_Matrix.png|center|600px]]

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

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