1© L. Plümer

VRS Liniennetzplan der Bonner Innenstadt

2© L. Plümer

Kartogramm des Liniennetzplanes

3© L. Plümer

Graphen

Knoten

4© L. Plümer

Graphen

Knoten

Kanten

2

24

1

3

2

3

2

3

1

5© L. Plümer

Graphen

Knoten

Kanten

Pfad

B

A 2

24

1

3

2

3

2

3

1

6© L. Plümer

Graphen

Knoten

Kanten

Pfad

kürzester Pfad

B

A 2

24

1

3

2

3

2

3

1

7© L. Plümer

Graphen

Gerichteter Graph

8© L. Plümer

Graphen

Nicht zusammenhängend

9© L. Plümer

Graphen

ZusammenhängendTrennende Kante (Isthmus)

10© L. Plümer

Graphen

Trennender Knoten

11© L. Plümer

Isomorphe Graphen

J

M

L

K

J

M

L

K J

M

L

K

A

B

CD

AB

C

DA

B

CD

12© L. Plümer

Vereinfachung von Netzwerken

Beispiel: Eisenbahnnetz

a) Karte mit geographischen Koordinaten

b) Generalisieren von Verbindungen

c) Entfernung des Kontextes

d) Entzerren von Verbindungen

a) b)c) d)

13© L. Plümer

Definitionen I

• Ein ungerichteter Graph G(V,E) ist eine Menge V von Knoten zusammen mit einer Menge E von Kanten. Eine Kante ist eine Menge (ungeordnetes Paar) von je 2 Knoten.

e = {x,y} x Vy V

• Wenn e = {x,y} dann sind x und e bzw. y und e inzident.

• Zwei Kanten {x,y} und {y,z} sind adjazent.• Ein Pfad ({a1,a2},{a2,a3},{a3,a4}, ... ,{an-1,an}) von a1

nach an ist ein Folge von adjazenten Kanten.

14© L. Plümer

Definitionen II

• Ein Graph heißt zusammenhängend, wenn man zu jedem Paar von Knoten einen Pfad findet; sonst nicht zusammenhängend.

• Ein Pfad von a nach a heißt Zyklus.• Ein Graph heißt zyklenfrei, wenn er keine Zyklen

besitzt. Beispiel: Baum (zyklenfrei + zusammenhängend)

• Grad eines Knotens: Zahl der inzidenten KantenBeispiel: In Landkarten haben Knoten mindestens den Grad 2.

15© L. Plümer

Definitionen III

• Trennende Kante e eines zusammenhängenden Graphen G: Entfernung von e würde G nicht zusammenhängend machen. Beispiel: Sylt + Hindenburg-Damm

• Trennender Knoten v eines zusammenhängenden Graphen G: Entfernung von v würde G nicht zusammenhängend machen.Beispiel: Attentat auf das World Trade Center in New York

16© L. Plümer

Definitionen IV

• Gerichtete Graphen unterscheiden sich von ungerichteten dadurch, daß die Kanten nicht Mengen (ungerichtet) sondern Paare (gerichtet) sind.

C

BA

zusammenhängend

C

BA

zusammenhängend

C

BA

nicht zusammenhängendkein Pfad von A nach B

A nach CC nach B

17© L. Plümer

Definitionen V

• Isomorphie zweier GraphenG = (V,E)G‘= (V‘,E‘)G G‘ gilt, wenn V V‘ es existieren bijektive

E E‘ (eineindeutige) Abbildungen

• Ebener Graph: • Jeder Knoten hat Koordinaten • Die (geraden) Kanten sind paarweise kreuzungsfrei

kein ebener Graph ebener Graph

18© L. Plümer

Anwendungsbeispiel

• Routenplanung für Autofahrer (Taxifahrer) in der Kölner Innenstadt und Umland auf Basis von Graphen• Ziel: UML-Diagramm• Frage: Reichen die heute diskutierten Begriffe für diesen

Zweck aus?Was fehlt?

• Szenario: Sylvester/Karneval, Kunde von Kneipe x in Krankenhaus y fahren.