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