close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Konzert Musikschule - Webseiten der Schule Strengelbach

EinbettenHerunterladen
2. Repr¨asentationen von Graphen in Computern
Kapitelinhalt
2. Repr¨
asentationen von Graphen in Computern
• Matrizen- und Listendarstellung von Graphen
• Berechnung der Anzahl der verschiedenen Kantenzu
¨ge zwischen zwei
Knoten
• Eigenwertprobleme und lineare Differenzengleichungen
• Anwendung von Differenzengleichungen fu
¨r Graphen
Graphentheorie — HS Bonn-Rhein-Sieg, WS 2014/15
69
2. Repr¨asentationen von Graphen in Computern
Matrizen- und Listendarstellung von Graphen
Adjazenzmatrix
Definition 2.1. Gegeben sei ein Graph G = (V, E) mit V =
{v1, . . . , vn}, n ≥ 1. Dann kann E in Form einer n × n-Matrix repr¨asentiert
werden. Es sei
1 falls {vi, vj } ∈ E
aij =
0 sonst
AG = (aij )i,j∈{1,...,n} heißt die Adjazenzmatrix (adjacency matrix) von G.
Bemerkung 2.1. AG ist symmetrisch und aii = 0, 1 ≤ i ≤ n.
Analog kann die Adjazenzmatrix fu
¨r die Darstellung gerichteter Graphen
verwendet werden. Sie ist dann i.d.R. nicht symmetrisch.
Graphentheorie — HS Bonn-Rhein-Sieg, WS 2014/15
70
2. Repr¨asentationen von Graphen in Computern
Matrizen- und Listendarstellung von Graphen
Adjazenzmatrix (2)
v3
v2
v4
G=
v1
Graphentheorie — HS Bonn-Rhein-Sieg, WS 2014/15



AG = 


0
1
0
0
1
1
0
1
1
0
0
1
0
1
0
0
1
1
0
1
1
0
0
1
0






v5
71
2. Repr¨asentationen von Graphen in Computern
Matrizen- und Listendarstellung von Graphen
Adjazenzmatrix (3)
• Es kann in Zeit O(1) u
¨berpru
¨ft werden, ob zwei Knoten vi und vj
adjazent sind.
• deg(vi) ist gleich der Zeilensumme der i-ten Zeile (bzw. der Spaltensumme der i-Spalte). Aufwand: O(|V |)
• Ermittlung der Nachbarn zu einem Knoten vi : Suche in der i-ten Zeile/Spalte
• notwendiger Speicherplatz: O(|V |2)
• Platzverbrauch ineffizient fu
¨r bestimmte Graphklassen, z.B. B¨aume, planare Graphen (siehe Kapitel 6)
Graphentheorie — HS Bonn-Rhein-Sieg, WS 2014/15
72
2. Repr¨asentationen von Graphen in Computern
Matrizen- und Listendarstellung von Graphen
Beispiel: Adjazenzmatrix fu
¨r gerichtete Graphen




A=



Graphentheorie — HS Bonn-Rhein-Sieg, WS 2014/15
0
0
1
0
0
0
1
0
0
0
0
1
1
0
0
1
0
0
0
0
1
0
0
0
1
1
1
1
0
0
0
0
0
1
1
0








73
2. Repr¨asentationen von Graphen in Computern
Matrizen- und Listendarstellung von Graphen
Adjazenzmatrix fu
¨r nicht schlichte Graphen
• Fu
¨r nicht schlichte Graphen gibt aij die Anzahl der Kanten zwischen vi
und vj an.
• Wenn Schlingen vorliegen, sind die Diagonalelemente der entsprechenden
Knoten ungleich 0. Das Element aii gibt dann die Anzahl der Schlingen
am Knoten vi an.
• Bei der Gradermittlung mu
¨ssen die Diagonalelemente doppelt gez¨ahlt
werden:
n
deg(vi ) = 2 · aii +
aik
k=1,k=i
Graphentheorie — HS Bonn-Rhein-Sieg, WS 2014/15
74
2. Repr¨asentationen von Graphen in Computern
Matrizen- und Listendarstellung von Graphen
Beispiel: Adjazenzmatrix fu
¨r nicht schlichte Graphen




A=



Graphentheorie — HS Bonn-Rhein-Sieg, WS 2014/15
0
1
0
0
2
1
1
0
1
0
1
0
0
1
1
1
1
0
0
0
1
0
1
0
2
1
1
1
0
2
1
0
0
0
2
0








75
2. Repr¨asentationen von Graphen in Computern
Matrizen- und Listendarstellung von Graphen
Adjazenzmatrix: gerichtet und nicht schlicht
• Prinzipiell k¨onnen natu
¨rlich auch gerichtete Graphen nicht schlicht sein,
• d.h. an Knoten existieren Schlingen oder
• zwischen zwei Knoten a und b gibt es mehrere Kanten mit der gleichen
Richtung (von a nach b).
Graphentheorie — HS Bonn-Rhein-Sieg, WS 2014/15
76
2. Repr¨asentationen von Graphen in Computern
Matrizen- und Listendarstellung von Graphen
Beispiel: gerichtet und nicht schlicht




A=



Graphentheorie — HS Bonn-Rhein-Sieg, WS 2014/15
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
3
1
0
1
0
1
0
1
1
1
0
0
0
0
1
0
0
0
0








77
2. Repr¨asentationen von Graphen in Computern
Matrizen- und Listendarstellung von Graphen
Adjazenzliste
Definition 2.2. Gegeben sei ein Graph G = (V, E) mit V =
{v1, . . . , vn}, n ≥ 1. Dann kann E in Form einer Liste von n-Listen Ai
repr¨asentiert werden. Fu
¨r 1 ≤ i ≤ n seien vi1 , vi2 , . . . , vni die mit vi ∈ V
adjazenten Knoten. Die Liste
Ai = (vi1 , vi2 , . . . , vni )
heißt die Adjazenzliste von vi ∈ V .
Die Liste LG = (A1, . . . , An) ist die Adjazenzlistendarstellung von G.
Fu
¨r einen gerichteten Graphen G = (V, A) enth¨alt die Adjazenzliste Ai die
Knoten w ∈ V , fu
¨r die (vi, w) ∈ A gilt.
Graphentheorie — HS Bonn-Rhein-Sieg, WS 2014/15
78
2. Repr¨asentationen von Graphen in Computern
Matrizen- und Listendarstellung von Graphen
Adjazenzliste (2)
v1
v2
v5
v2
v1
v3
v3
v2
v4
v4
v2
v3
v5
v1
v4
v3
LG =
v2
v4
v4
v5
G=
v1
Graphentheorie — HS Bonn-Rhein-Sieg, WS 2014/15
v5
79
2. Repr¨asentationen von Graphen in Computern
Matrizen- und Listendarstellung von Graphen
Adjazenzliste (3)
• Um zu u
¨berpru
¨fen, ob zwei Knoten vi und vj adjazent sind, muss die
Adjazenzliste von vi durchsucht werden.
• Dies ist nicht in O(1) m¨oglich, der genaue Aufwand h¨angt von der
Implementierung der Adjazenzliste ab.
• Der Knotengrad entspricht der L¨ange der Adjazenzliste.
• Die Nachbarn zu einem Knoten liegen direkt in der Adjazenzliste vor.
• notwendiger Speicherplatz: O(|V | + |E|)
Graphentheorie — HS Bonn-Rhein-Sieg, WS 2014/15
80
2. Repr¨asentationen von Graphen in Computern
Anzahl der Kantenz¨
uge zwischen zwei Knoten
Beispiel: Anzahl Wege zwischen zwei Knoten (1)
Wir betrachten als Beispiel den folgenden gerichteten Graphen G mit seiner
Adjazenzmatrix:





A=




Graphentheorie — HS Bonn-Rhein-Sieg, WS 2014/15
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
0










81
2. Repr¨asentationen von Graphen in Computern
Anzahl der Kantenz¨
uge zwischen zwei Knoten
Beispiel: Anzahl Wege zwischen zwei Knoten (2)
Wir bilden die Potenzen der Adjazenzmatrix A:





2
A =




0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
1
0
0
0
0
Graphentheorie — HS Bonn-Rhein-Sieg, WS 2014/15
0
0
0
2
0
0
0















3
A =




0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
2
0
0
0
0
0
0
0
2
2
0
0
0
0










82
2. Repr¨asentationen von Graphen in Computern





4
A =




0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Anzahl der Kantenz¨
uge zwischen zwei Knoten
4
0
0
0
0
0
0















k
A =




0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0





 fu
 ¨r k ≥ 5



• Das Element ai,j der Matrizen Ak gibt hier die Anzahl der (einfachen)
Wege der L¨ange k von i nach j an.
Graphentheorie — HS Bonn-Rhein-Sieg, WS 2014/15
83
2. Repr¨asentationen von Graphen in Computern
Anzahl der Kantenz¨
uge zwischen zwei Knoten
Anzahl der Kantenzu
¨ge zwischen zwei Knoten
Satz 2.1. Es sei G = (V, E) ein Graph mit der Adjazenzmatrix A = (aij ).
(r)
Dann gibt das Element aij der Matrix Ar die Anzahl der Kantenz¨uge der
L¨ange r von vi nach vj an.
Beweis: Induktion u
¨ber r.
r = 1 : Damit gilt Ar = A. Die Adjazenzmatrix gibt genau die Kantenzu
¨ge
der L¨ange 1 an.
r → r + 1:
• Jeder Kantenzug der L¨ange r +1 zwischen zwei Knoten vi und vj besteht
Graphentheorie — HS Bonn-Rhein-Sieg, WS 2014/15
84
2. Repr¨asentationen von Graphen in Computern
Anzahl der Kantenz¨
uge zwischen zwei Knoten
aus einem Kantenzug der L¨ange r zwischen vi und einem Knoten vk
sowie der Kante {vk , vj }.
• Nach I.V. gibt Ar die Anzahl der Kantenzu
¨ge der L¨ange r zwischen zwei
Knoten an.
• Es gilt
|V |
(r+1)
aij
(r)
=
aik · akj
k=1
• Da akj = 1 gdw. zwischen vi und vj eine Kante ist, beschreibt diese
Formel die Anzahl der M¨oglichkeiten, einen Kantenzug der L¨ange r + 1
zwischen vi und vj aus einem Kantenzug der L¨ange r zwischen vi und
einem Knoten vk sowie der Kante {vk , vj } zu bilden.
Graphentheorie — HS Bonn-Rhein-Sieg, WS 2014/15
85
2. Repr¨asentationen von Graphen in Computern
Anzahl der Kantenz¨
uge zwischen zwei Knoten
Korollar 2.2. Es sei G = (V, E) ein Graph mit der Adjazenzmatrix A =
(aij ).
Dann gibt das Element bij der Matrix
B = A + A2 + · · · + Ap
die Anzahl der Kantenz¨uge mit einer L¨ange ≤ p von vi nach vj an.
Korollar 2.3. Es sei G = (V, E) ein Graph mit der Adjazenzmatrix A =
(aij ) und es sei
B = A + A2 + · · · + A|V |−1
ur alle i = j
Dann gilt: G ist genau dann zusammenh¨angend, wenn bij > 0 f¨
gilt.
Beweis: Wenn G zusammenh¨angend ist,
Graphentheorie — HS Bonn-Rhein-Sieg, WS 2014/15
86
2. Repr¨asentationen von Graphen in Computern
Anzahl der Kantenz¨
uge zwischen zwei Knoten
• gibt es zwischen zwei beliebigen Knoten vi und vj mindestens einen Weg,
• damit auch mindestens einen einfachen Weg.
• Ein einfacher Weg hat eine L¨ange ≤ |V | − 1.
• Damit liefert der einfache Weg (als Kantenzug) einen Beitrag zu bij .
• Also folgt bij > 0.
Andererseits folgt aus bij > 0,
• dass es mindestens einen Kantenzug und damit auch einen Weg von vi
nach vj gibt.
Graphentheorie — HS Bonn-Rhein-Sieg, WS 2014/15
87
2. Repr¨asentationen von Graphen in Computern
Anzahl der Kantenz¨
uge zwischen zwei Knoten
• Somit folgt aus bij > 0 fu
¨r alle i = j, dass es zwischen je zwei Knoten
von G einen Weg gibt.
• Damit ist G zusammenh¨angend.
Graphentheorie — HS Bonn-Rhein-Sieg, WS 2014/15
88
2. Repr¨asentationen von Graphen in Computern
Anzahl der Kantenz¨
uge zwischen zwei Knoten
Bemerkungen
• Weil in Dags jeder Kantenzug ein gerichteter einfacher Weg ist, liefert
Ar dort sogar die Anzahl der einfachen Wege der L¨ange r.
• Auch k¨onnen wir mit diesem Ansatz prinzipiell testen, ob ein gerichteter
Graph kreisfrei ist (fu
¨r p = |V | mu
¨ssen die bii alle ungleich 0 sein).
• Sowohl fu
¨r die Kreisfreiheit als auch fu
¨r den Zusammenhang sind diese
Berechnungsans¨atze aber ineffizient.
• Im n¨achsten Kapitel werden wir effizientere Algorithmen fu
¨r diese Probleme kennenlernen.
Graphentheorie — HS Bonn-Rhein-Sieg, WS 2014/15
89
Document
Kategorie
Gesundheitswesen
Seitenansichten
5
Dateigröße
93 KB
Tags
1/--Seiten
melden