Institut für Kartographie und Geoinformation Prof. Dr. Lutz Plümer Geoinformation I Vorlesung 8 WS 2000/2001 Graphen

Institut für Kartographie und GeoinformationProf. Dr. Lutz Plümer

Geoinformation IVorlesung 8

WS 2000/2001

Graphen

Lutz Plümer - Geoinformation - 1./5. Semester - WS 00/01 - Vorlesung 8 Lutz Plümer - Geoinformation - 1./5. Semester - WS 00/01 - Vorlesung 8

2 2

Übersicht

• VRS Liniennetzplan der Bonner Innenstadt

• Kartogramm des Liniennetzplanes

• GraphenIsomorphe

• Graphen

• Vereinfachung von Netzwerken

• Definitionen

• Anwendungsbeispiel


3 3

VRS Liniennetzplan der Bonner Innenstadt


4 4

Kartogramm des Liniennetzplanes


5 5

Graphen

Knoten


6 6

Graphen

Knoten

Kanten

2

24

1

3

2

3

2

3

1


7 7

Graphen

Knoten

Kanten

Pfad

B

A 2

24

1

3

2

3

2

3

1


8 8

Graphen

Knoten

Kanten

Pfad

B

A 2

24

1

3

2

3

2

3

1


9 9

Graphen

Knoten

Kanten

Pfad

B

A 2

24

1

3

2

3

2

3

1


10 10

Graphen

Knoten

Kanten

Pfad

A 2

24

1

3

2

3

2

3

1

B


11 11

Graphen

Knoten

Kanten

Pfad

B

A 2

24

1

3

2

3

2

3

1


12 12

Graphen

Knoten

Kanten

Pfad

B

A 2

24

1

3

2

3

2

3

1


13 13

Graphen

Knoten

Kanten

Pfad

kürzester Pfad

B

A 2

24

1

3

2

3

2

3

1


14 14

Graphen

Knoten

Kanten

Pfad

kürzester Pfad

B

A 2

24

1

3

2

3

2

3

1


15 15

Graphen

Knoten

Kanten

Pfad

kürzester Pfad

B

A 2

24

1

3

2

3

2

3

1


16 16

Graphen

Knoten

Kanten

Pfad

kürzester Pfad

A 2

24

1

3

2

3

2

3

1

B


17 17

Graphen

Gerichteter Graph


18 18

Graphen

Nicht zusammenhängend


19 19

Graphen

ZusammenhängendTrennende Kante (Isthmus)


20 20

Graphen

Trennender Knoten


21 21

Isomorphe Graphen

J

M

L

K

J

M

L

K J

M

L

K

A

B

CD

AB

C

DA

B

CD


22 22

Graphisomorphie - Definition

• Zwei Graphen sind isomorph, wenn eine bijektive Abbildung existiert, die die Knoten-Kanten-Adjazenzen respektiert.


23 23

Vereinfachung von Netzwerken

Beispiel: Eisenbahnnetz

Karte mit geographischen Koordinaten

Generalisieren von Verbindungen

Entfernung des Kontextes

Entzerren von Verbindungen


24 24

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.


25 25

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.


26 26

Definitionen III

• Trennende Kante e eines zusammenhängenden Graphen G („Isthmus“): 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


27 27

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


28 28

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


29 29

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.

Documents

Institut für Kartographie und Geoinformation Prof. Dr. Lutz Plümer Geoinformation I Vorlesung 8 WS 2000/2001 Graphen