View
108
Download
2
Category
Preview:
Citation preview
1
Graphen
Ein Graph ist eine Kollektion von Knoten und Kanten. Knoten sind einfache Objekte. Sie haben Namen und können Träger von Werten, Eigenschaften etc. sein. Kanten sind Verbindungen zwischen Knoten
2
Definition und Beispiele
Mathematisch ist ein Graph G eine zweistellige Relation auf einer beliebigen Menge V. Jede beliebige Teilmenge
G ⊆ V x V ist ein Graph. Ein Graph ist Menge von Paaren der
Form (v,w) mit v є V und w є V.
3
Beispiele
V= Menge aller Flughäfen in DeutschlandG= {(x,y) є V x V | Es gibt einen Direktflug
zwischen x und y}.Sei G ⊆ V x V. Die Elemente von V sind die Knoten
des Graphen. Sie können als Kreise dargestellt werden.
Die Elemente (x,y) є G sind die Kanten. Sie können als Pfeil von x nach y dargestellt werden:
A
4
Ein Graph
5
Symetrischer Graph
Ist G⊆ V x V ist symmetrisch, dann ist der Graph ungerichtet. Bei
einem solchen Graphen gehört zu jedem Pfeil von x nach y auch ein Pfeil von y nach x:
A A↹↹
6
Gewichteter Graph
Bewerteter Graph Jeder Kante ist ein Wert zu geordnet Dieser Wert kann ganzzahlig oder
reel sein
7
Wege und Zusammenhang
Ein Weg(Pfad) in einem Graphen ist eine Folge
x=Ka,Kb,….Kn=y von Knoten, in der es jeweils Kanten
von Ka nach Kb usw. Bis Kn gibt. Man spricht von einem Weg von x nach y. Auf einem einfachen Weg kommt kein Knoten doppelt vor.
8
Zyklus
Ein einfacher Weg von x nach x heißt Zyklus.
Bsp:B,C,A,D,A Weg von B nach A Zyklus A,D,A
C,A,B,E einfacher Weg) F,F,F,G (kein einfacher)Weg A,B,C,A Zyklus A,B,E,A kein Weg, kein Zyklus
9
Graph oder Baum?
G heißt zusammenhängend, wenn es zwischen zwei Knoten einen Weg gibt.
Ist G nicht zusammenhängend, so zerfällt er in eine Vereinigung zusammenhängender Komponenten.
Ein zusammenhängender, zyklusfreier Graph ist ein Baum.
10
Teilgraph
Ist G auf V ein zusammenhängender, zyklusfreier Graph und R ein zyklenfreier zusammenhängender Teilgraph von G auf V, dann ist R ein Spannbaum(erzeugender baum).
Jeder zusammenhängende Graph besitzt einen erzeugenden Baum.
11
Graph und Spannbaum
Solange es einen Zylus gibt, entferne eine Kante aus diesem Zyklus.
12
Repräsentationen von GraphenAdjazenzmatrix(speicheraufwendig)
boolesche Matrixboolean [] [] Graph;
13
Repräsentationen von Graphen2
Ein Beispiel aus dem Bereich der Verkehrsnetze
14
Speicherung als Array
Einträge sind keine boolesche Werte sondern, Bewertungen der Kanten
15
Graphendarstellung (weniger Speicheraufwendige Methode)
Zu jeden Knoten ist eine Liste zu definieren, in der die unmittelbaren Nachbarn samt ihrer Entfernungen enthalten sind.
16
Eine Alternative:
-spart Platz -im gegensatz zu Adjazenzmatrix
kein direkter Zugriff auf den Wért einer Kante möglich
17
Tranversierungen
Viele Algorithmen auf Graphen beruhen darauf, dass man alle Knoten(bzw. alle Kanten) des Graphen durchwandert (traversiert).
Entspricht der Baumwanderung Es besteht die Gefahr, in die
Endlosschleife zu geraten, wenn der Graph Zyklen hat.
18
Strategien zur Traversierung
Tiefensuche(Preorder-Baumtraversierung) Dieser Allgorithmus besucht alle Knoten,
die von einem Ausgangsknoten k aus erreichbar sind, und markiert jeweils die besuchten Knoten. Zu Beginn müssen alle Markierungen gelöscht werden.Dept-Fist-Visit
Breitensuche(Levelorder-Baumtraversierung)
Es wird eine Warteschlange als Hilfsspeicher benötigt.
19
Transitive Hülle
Eine tweistellige Relation R auf einer Menge V ist transitiv, falls gilt:
∏x,y,z єV: (x,y) єR und (y,z) є R→(y,z) є R
Die transitive Hülle t(R) einer zweistelligen Relation R auf V ist die kleinste transitive Relation.
Es gibt einen Weg von x nach y genau dann, wenn es eine Kante von x nach y gibt.
20
Transitive Hülle
Beispiel:
21
Kürzeste Wege
In einem bewerteten Graphen ist kürzester Weg zwischen zwei Knoten u und v minimal, wenn die Summe der zwischenliegenden Kanten minimal ist.
Statt A[x][z] = true setzt man; A[x][z]= min(A[x][y] + A[y][z] Es wird eine Menge S aller Knoten k definiert; für welche
die kürzeste Entfernung zu u bereits bekannt ist. dist(u,k) Zu Beginn der Algorithmus gilt: S ={u} In jedem Schritt erweitert der Algorithmus die Menge S
um ein neues Element. es muss gelten: vєS
Recommended