Upload
marielies-boehme
View
213
Download
0
Embed Size (px)
Citation preview
Einführung in die Informationsverarbeitung Teil Thaller
Stunde V: Wege und warum man sie geht ...
... Graphen.
Köln 14. Januar 2016
Das Problem
2
A* Algorithmus: Schluß
3
Ausgangspunkt I
Möglichkeit möglichst vieler derartiger Probleme auf eine einzige Klasse von Vorgehensweisen zurück zu führen.
4
Ausgangspunkt II:
5
Abstraktion IV
6
„Ein Graph“
Knoten(Vertex, Nodes)
Kanten(Edges)
7
Definition des ProblemsEin Graph G heißt Eulerscher Graph, falls es einen geschlossenen einfachen Kantenzug gibt, der jede Kante von G enthält. Ein solcher Kantenzug heißt dann Eulerscher Kantenzug.
8
„Lösung“ des Problems
Sei G ein zusammenhängender Graph. Genau dann ist G ein Eulerscher Graph, wenn jeder Knoten von G geraden Grad hat.
9
Ziele der Graphentheorie in der Informatik
(1) Erlaube Aussagen über auf Graphen zurückführbare inhaltliche Probleme.
10
Kopf: (2) Beschreibe direkt die Eigenschaften von Listen, die wir am Tag 2 als eine der grundlegenden Datenstrukturen kennengelernt haben.
Schwanz:
Ziele der Graphentheorie in der Informatik Atom 1
Atom 2
Atom 3
11
Definitionen I
Einfacher, ungerichteter Graph.
Auch „schlichter Graph“.
12
Definitionen …Ist G ein Graph, so sagt man allgemein v ist Knoten (bzw. Ecke) von G, wenn v zu V(G) gehört. Ferner sagt man, falls G• ungerichteter Graph ohne Mehrfachkanten ist und e zu
E(G) gehört, e ist eine ungerichtete Kante von G, • gerichteter Graph ohne Mehrfachkanten ist und e zu
E(G) gehört, e ist eine gerichtete Kante von G, • ungerichteter Graph mit Mehrfachkanten ist und E(G)(e)
> 0, e ist eine ungerichtete Kante von G, • gerichteter Graph mit Mehrfachkanten ist und E(G)(e) >
0, e ist eine gerichtete Kante von G. 13
Definitionen II
Einfacher, gerichteter Graph.
Kanten hier: „gerichtete Kanten“, Bögen oder Dikanten.
14
Definitionen III
Ungerichteter Graph mit Mehrfachkanten, auch „Multigraph“.
15
Definitionen IV
Knotengefärbter Graph.
16
Definitionen V
Kantengefärbter Graph.
17
Definitionen VI
Ein verbundener - oderzusammenhängender - Graph.
18
Definitionen VII
Ein unverbundener -oder unzusammenhängender- Graph.
19
Definitionen VIII
Ein Graph mit einerSchleife
20
Definitionen IX
Ein Graph mit einem Zyklus.
21
Definitionen IX
Ein Graph mit einem Zyklus.
22
Beziehung: Graphen und Matrizen
K2
K3
K4K1
23
Beziehung: Graphen und Matrizen
K2
K3
K4K1
1 1 1 0 1 0 2 11 2 0 10 1 1 0
24
Konzept Isomorphie I
25
Konzept Isomorphie II
26
Konzept Isomorphie III
27
Konzept Isomorphie IV
Zwei Graphen G1 und G2 sind isomorph, wenn es eine umkehrbar eindeutige Beziehung zwischen den Ecken von G2 gibt derart, dass die Anzahl der Verbindungskanten zweier Ecken von G1 gleich der Anzahl von Verbindungskanten der entsprechenden Ecken von G2 ist.
28
Anwendung Isomorphie
Nachteil: Überschneidungen, Diagramm daher potentiell verwirrend.
29
Anwendung Isomorphie
Vorteil: Keine Überschneidungen, Diagramm daher klarer.
30
Weitere Begriffe
Grade: Anzahl der Kanten von und zu einem Knoten / allen Knoten.
Eingangsgrade und Ausgangsgrade.
Maximale / Minimale Eingangsgrade / Ausgangsgrade.
31
Weitere Begriffe
Verbundenheit:
Ein Graph ist n-verbunden, wenn n Kanten entfernt werden können, ohne dass er unzusammenhängend wird.
32
Beispiel
33
Verbindungen
34
Verbindungen
35
Verbindungen
36
Verbindungen
37
Verbindungen
38
Travelling salesman
39
Besuche jede Stadt, aber keine zweimal – auf möglichst kurzem Weg.
Travelling salesman
40“Brute force” Anzahl der Permutationen: (7-1)!/2 = 360
Travelling salesman
41“Branch and Bound” Anzahl der Permutationen < “Brute Force”
Travelling salesman
42“Nearest Neighbour” Ergebnis abhängig vom Startknoten
Weitere Begriffe
Durchmesser:
Ein Graph hat den Durchmesser n, wenn der längste nicht-zyklische Kantenzug zwischen zwei Knoten n Knoten durchläuft.
43
Weitere Begriffe
44
Ein ungerichteter, zusammenhängender Graphohne Zyklen heisst Baum.
D.h., die schwarzen Pfeile im nebenstehenden Diagramm definieren Zeiger nach unserer früheren Definition.
Die roten Linien repräsentieren die Kanten im repräsentierten Graphen.
Anwendungen …
45Semantisches Netz
Anwendungen …
46P2P Netzwerk
Anwendungen …
47www.stanford.edu/group/toolingup/rplviz/
Anwendungen …
48www.stanford.edu/group/toolingup/rplviz/
Anwendungen …
49http://informationandvisualization.de/blog/graphbased-visualization-topic-shifts
Anwendungen …
50http://mappingmetaphor.arts.gla.ac.uk
Literatur
Im empfohlenen Lehrbuch (Gumm / Sommer, Einführung in die Informatik, Oldenbourg, 82008) Kapitel 4.
http://www.mathematik.uni-marburg.de/~gumm/Buch/Dazu gehörige Programme (Kapitel 4) zum Download.
51
Vielen Dank!