Michael Gamer / 2015

Formale Grundlagen der InformatikMichael Gamer

Michael Gamer

Literatur

‣Algorithmische Graphentheorie • V. Turau • Oldenbourg Verlag • 2. Auflage2004

‣Graphentheorie • R. Diestel • Springer Verlag 2000

‣Algorithmen und Datenstrukturen • T. Ottmann, P Widmeyer • Spektrum Verlag, 4. Auflage, 2002

2

Michael Gamer

Literatur

‣Graphentheoretische Konzepte und Algorithmen • S.O. Krumke und H. Noltemeier • Teubner Verlag • 1. Auflage 2005

3

Michael Gamer

Definitionen und Begriffe

‣Ein Graph besteht aus einer Menge V von Ecken (Vertices) und Kanten E (Edges). Wird also durch ein Paar (V,E) definiert. ‣Beispielsweise wird durch folgende Definition ein

Graph beschrieben: • V := {1,2,3,4} • E := {(1,2),(1,3),(2,3),(3,4)}

‣Graphen werden üblicherweise graphisch (sic!) dargestellt. Für diesen Graphen erhält man die nebenstehende Darstellung:

4

1

3 4

2

Michael Gamer

Einfache GraphenUngerichteter Graph:

Keine Unterscheidung der Kanten (i,j) und (j,i)

gerichteter Graph: Unterscheidung zwischen (i,j)

und (j,i)

Für gerichtete Graphen ist die Kante (i,i) zulässig. Solche Kanten heißen Schlingen.

5

1

3 4

2

1

3 4

2

Michael Gamer

Vollständige Graphen und Teilgraphen

‣ Ein Graph heißt vollständig, wenn alle Knoten paarweise verbunden sind

‣ Ein Teilgraph oder auch Subgraph G1 = (V1,E1) eines Graphen G = (V,E) der aus einer Teilmenge der Knoten des Graphen G und der die Kanten

{{u,v} ∈ E | u,v ∈ V1} enthält. ‣ G1 heißt induzierter Teilgraph von G falls dieser alle Kanten

enthält die im Ausgangsgraphen zu diesen Knoten existieren.

‣ Eine k-Clique ist ein vollständiger Subgraph eines Graphen G der k Knoten enthält

6

Michael Gamer

Beispiele

K1

K2

K3

K4

P5

P3

P4

C3

C4

C5

7

Michael Gamer

Grundlegende Begriffe

•Definition gerichteter Graph • Ein Paar G = (V,E) mit

‣ V eine nichtleere Menge von Knoten ‣ E ⊆V x V eine Menge von Kanten

heißt gerichteter Graph. Ein Element aus E wird auch als Pfeil bezeichnet

• Für G definieren wir Abbildungen ‣ α: E→V mit α(u,v) := u (Anfangsecke) ‣ ω: E→V, mit ω(u,v) := v (Endecke)

8

Michael Gamer

Schlingen und Co

‣ Sei G = (V,E) ein Graph • Ein Element e∈E mit α(e) = ω(e) heißt Schlinge in G • Ein Graph in dem für alle e∈E gilt: α(e) ≠ ω(e) heißt

schlingenfrei • Zwei Elemente e,f ∈ E heißen parallel, falls

๏α(e) = α(f) und ω(e) = ω(f) gilt • Zwei Elemente e,f ∈ E heißen antiparallel, falls

๏α(e) = ω(f) und ω(e) = α(f) gilt • Ein Graph heißt einfach, wenn er schlingenfrei ist

und keine Parallelen enthält

9

Michael Gamer

Beispiele für Graphen

10

Schlinge

Doppelkante

Michael Gamer

Inzidenz, Adjazenz, Grade (1/2)

‣ Sei G = (V,E) ein Graph • v∈V heißt inzident zu (x,y)∈E, falls v=x oder v=y ist • Zwei Ecken u,v∈V heißen adjazent, falls (u,v)∈E oder

(v,u)∈E gilt • Für jedes v∈V bezeichnen

๏δ+(v):= {e∈E|α(e)=v}, das von v ausgehende Pfeilbüschel

๏δ-(v):= {e∈E|ω(e)=v}, das in v mündende Pfeilbüschel} ๏ N+(v):={ω(e)|e∈ δ+(v)}, die Nachfolgermenge von v} ๏ N-(v):={α(e)|e∈ δ-(v)}, die Vorgängermenge von v}

11

Michael Gamer

Inzidenz, Adjazenz, Grade (2/2)

‣Für jedes v∈V bezeichnen • g+(v):= |δ+(v)|, den Außengrad von v • g-(v):= |δ-(v)|, den Innengrad von v • g(v):= g+(v) + g-(v) den Grad von v

‣Mit Δ(G) := max{g(v)|v∈V} wird der Maximalgrad von G bezeichnet.

12

Michael Gamer

Beispiel

13

Δ(G)=6

g+(v)=5g(v)=6

g-(v)=3g-(v)=2g+(v)=1

g+(v)=1g-(v)=1

Michael Gamer

Bipartite Graphen

K3,4

Anwendungenbipar;terGraphensindinersterLinieZuordnungsproblemeArbeiteraufMaschinenTransportmiHelaufTransportwege,etc.

14

Michael Gamer

Isomorphien bei Graphen

K4

ist isomorph zu

Zwei Graphen G = (V,E) und G´ = (V`, E`) heißen isomorph, genau dann, wenn es eine bijektive Abbildung f : V → V` gibt, so daß für alle u,v ∈V

gilt: (u,v)∈E ⇔ (f(u), f(v)) ∈ E`

• Es ist nicht immer einfach zu erkennen, ob zwei Graphen identisch sind:

15

Michael Gamer

Isomorphie von Graphen

‣Die Isomorphie von Graphen ist oftmals nicht einfach zu erkennen. ‣Beispiel: Petersen-Graph

16

Michael Gamer

Zum Petersen-Graphen isomorphe Graphen:

17

Michael Gamer

Beispiel

§ Für jede Zahl zwischen 1 und 6 ist in diesem Graphen eine Kante

eingezeichnet, wenn die beiden Zahlen teilerfremd sind

§ Die vier Zahlen 1, 2, 3 und 5 bilden eine 4-

Clique § Die Zahlen 4, 2 und 6

bilden eine 3-Anticlique

18

Michael Gamer

Anwendungen für Cliquen

19

Gegeben ist folgende Straßenkreuzung

aus Krumke/Noltemeier

S1

S2

S3

S4

S5

S6S7

S8

Michael Gamer

Modellierung als Graphenproblem

‣Modellierung der Verkehrsströme als Graph G = (V,E) • Knoten: V = {S1, ... S8} • Kanten werden durch folgende Vorschrift

erzeugt

20

E={(Si,Sj)|SiundSjkönnensimultanundkollisionsfreiüberdieKreuzung

gehen}

Michael Gamer

Graph für das Kreuzungsproblem

21

S2

S7

S1

S5

S3

S6

S8 S4

Michael Gamer

Ergebnis

‣Jeder vollständige Teilgraph von G (Clique!) kann konfliktfrei die Kreuzung überqueren ‣Ziel: Bündelung zu möglichst großen Cliquen ‣z.B. ist folgende „Bündelung“ möglich

• C1 = {S1, S2, S6} C2 = {S2, S5, S6} • C3 = {S3, S5, S6} C4 = {S4, S5, S6} • C5 = {S1, S7} C6 = {S7, S8}

‣Rahmenbedingung: die Folge Ci1, Ci2,... wird periodisch wiederholt (Ampelschaltung) und überdeckt die relevanten Verkehrsströme

22

Michael Gamer

Begriffe im Zusammenhang mit Cliquen

‣Die Cliquenzahl eines Graphen G = (V,E) ist • ω(G) := max {|C| : C ist Clique in G}

‣Die Cliquenzerlegungszahl ist definiert als • χ(G) := min {k: C1⊍C2⊍...⊍Ck ist eine

Cliquenzerlegung von G} ‣Für jeden Graphen mit n Ecken gilt 1 ≤ χ(G) ≤n

• Jede natürliche Zahl kann als Cliquenzerlegungszahl auftreten, Beispiel: Gn = ({1,2,...,n},∅)

23

Michael Gamer

Wege und Spaziergänge

‣Ein Weg in einem Graphen G = (V,E) ist ein durch eine Folge von paarweise verschiedenen Knoten und Kanten verbundener Streckenzug, also eine Folge • u1, u2,… un ∈ V mit • (u1,u2) ∈ E, (u2,u3) ∈ E, … (un-1,un) ∈ E

‣Falls u1 = un gilt, so spricht man von einem geschlossenen Weg, Kreis oder auch Zykel. ‣Ein Spaziergang von v nach w ist eine alternierende

Folge von Knoten und Kanten ‣ (v=v0 , e1, v1 , e2, v3 , e3, …, vn = w)

24

Michael Gamer

Wege und Spaziergänge 1

‣ Ist M eine Menge so heißt eine Abbildung ‣ d: MxM ➝ R Metrik, genau dann wenn

folgende Bedingungen erfüllt sind: • d(x,y) ≧ 0 , für alle x, y ∈ M • d(x,y) = d(y,x) • d(x,y) = 0 ⇔ x=y

• d(x,y) ≦d(x,z)+ d(z,y), für alle x,y,z ∈ M

25

Michael Gamer

Wege und Spaziergänge 2

• Ein Weg, der jeden Knoten genau einmal enthält wird Hamilton-Pfad genannt.

• Ein geschlossener Weg der jeden Knoten des Graphen (mit Ausnahme des Startknotens) genau einmal enthält heißt Hamilton-Kreis.

• Gibt es in einem Graphen zwischen je zwei Knoten einen Weg, so heißt der Graph zusammenhängend.

• Ist G ein zusammenhängender Graph, so heißt die Länge des kürzesten Weges von v nach w Abstand von v und w, geschrieben: dist(v,w). Die Abstandsfunktion dist erfüllt als Abbildung die Eigenschaften einer Metrik.

26

Michael Gamer

Hamilton und Euler

‣Ein geschlossener Weg der jeden Knoten des Graphen (mit Ausnahme des Startknotens) genau einmal enthält heißt Hamilton-Kreis ‣Ein geschlossener Weg der jede Kante in einem

Graph genau einmal durchläuft heißt Euler-Kreis ‣Das Problem einen Hamilton-Kreis in einem Graphen

zu finden ist NP-vollständig!

27

Michael Gamer

Ein Graph ohne Hamilton-Kreis

28

DerPetersen-GraphenthältkeinenHamilton-Kreis!

Michael Gamer

Codierung von Graphen: Adjazenzmatrizen

Ist V = { v1, v2, … vn} die Knotenmenge eines Graphen G = (V,E), so heißt die Matrix: A = (ai,j) mit

29

Adjazenzmatrix von G

Michael Gamer

Codierung von Graphen: Inzidenzmatrizen

‣ Ist V = { v1, v2, … vn} die Knotenmenge eines Graphen G = (V,E), so heißt die Matrix: B = (bi,j) mit

30

Michael Gamer

Die Ordnung eines Knotens

31

5

2

4 3

3

5

Michael Gamer

Effiziente Algorithmen

‣Ein Algorithmus für ein Problem ist eine Abfolge wohldefinierter Regeln (Befehlen), die nach einer endlichen Anzahl von Schritten zu einer gegebenen Eingabe eine definierte Ausgabe erzeugt. Folgendes soll dabei gelten:

• Ein Algorithmus läßt sich mit einem Text endlicher Länge beschreiben

• Die Abfolge der Schritte ist in jeder Berechnung eindeutig

• Jeder Elementarschritt läßt sich mechanisch und effizient ausführen

• Der Algorithmus stoppt bei jeder Eingabe nach endlich vielen Schritten.

32

Michael Gamer

Zusammenhangskomponenten

‣ Ein Graph (V,E) heißt zusammenhängend von einem Knoten v ∈V aus genau dann, wenn es für jeden Knoten w∈V einen Weg von v nach W gibt, d.h es gilt:

33

∀v∈V

∀w∈V

∃v1,v2 ,…vn∈V

(v,v1),(v1,v2 ),…(vn ,w)∈E

Ein induzierter Teilgraph U eines Graphen heißt Zusammenhangskomponente von G, falls U

zusammenhängend ist.

Michael Gamer

Breitensuche (BFS) (1/2)

‣Gegeben ist ein Graph G = (V,E) und ein Startknoten s. Zu überprüfen ist, ob von s aus alle Knoten des Graphen G erreichbar sind (Bestimmung der Zusammenhangskomponente). ‣Vorgehensweise zur Lösung des Problems:

• Ausgehend von s betrachten wir alle Nachbarn von s • Danach die Nachbarn der Nachbarn • Usw.

‣Wurden alle Knoten durchlaufen so terminiert der Algorithmus und die Zusammenhangskomponente ist bestimmt. ‣Problem: Knoten dürfen nicht doppelt besucht werden

34

Michael Gamer

Breitensuche (2/2)

‣Algorithmus Breitensuche: ‣Aufgabe: Ausgehend vom Startknoten s ist die

Zusammenhangskomponente von s zu bestimmen ‣Lösung:

• Markiere den Startknoten s (Ausgabe s) • Bestimme alle Nachbarn von s und markiere diese und

speichere sie (Ausgabe Nachbarn) in einer Warteschlange Q

• Solange Q nicht leer ist: ๏ Füge unmarkierte Nachbarn aus Q an das Ende der Warteschlange an und markiere diese (Ausgabe Nachbarn)

35

Michael Gamer

Beispiel Breitensuche

36

1

2 3

54

6

7 8 9

Suchbaum1

2

45

3

9

6

7

8

Startknoten: 1

Michael Gamer

Tiefensuche (DFS)

‣ Statt, wie in der Breitensuche, erst alle Nachbarn der Nachbarn zu durchsuchen, behandelt die Tiefensuche für jeden gefundenen Nachbarknoten gleich dessen Nachbarn.

37

Michael Gamer

Tiefensuche Beispiel

38

1

2

45

3

9

6

7

8

Startknoten: 11

2

4

5

6

7

9

8

3

Suchbaum

Michael Gamer

Valenzsequenzen

‣ Ist v1, v2, … vn irgendeine Anordnung der Knoten eine Graphen G = (V,E), so heißt ‣ (deg(v1), deg(v2), … deg(vn)) Gradsequenz, oder

auch Valenzsequenz, von G. ‣Frage: kann man bei einem beliebigen Zahlentupel

(a1, a2, … an ) entscheiden, ob dies zu einem Graphen gehört oder nicht? ‣Folgen wie z.B. (3,3,3,2,2,2) kann man sofort

ausscheiden, denn es gilt die folgende Beziehung:

39

Michael Gamer

Das Handshake-Lemma

‣ In jedem Graphen G = (V,E) ist die Summe der Knotengrade gerade, es gilt:

40

(Anregung: Warum heißt diese Aussage „Handshake-Lemma“?) Die Folge (3,3,3,2,2,2) scheidet damit als Valenzsequenz eines Graphen aus.

Michael Gamer

Ein Algorithmus für Valenzsequenzen

Folgender Satz erlaubt es zu entscheiden, ob ein Zahlentupel die Valenzsequenz eines Graphen ist, oder nicht:

41

Ist D = (d1, d2, …. dn) eine Folge natürlicher Zahlen, n>1 und d1>= d2>= …. >=dn, dann ist D genau dann die Valenzsequenz eines einfachen Graphen, wenn d1+1≤n ist und die Folge D`= (d´2, d´3, …. d´n) definiert durch

Die Valenzsequenz eines einfachen Graphen ist.

Michael Gamer

Beispiel: Valenzsequenz

Wir betrachten die Sequenz: D = (5,5,4,4,3,3,2,2,1,1) Das Handshake-Lemma liefert die Aussage, daß es sich grundsätzlich um die Valenzsequenz eines Graphen handeln kann. Der zuvor definierte Algorithmus liefert: D` = (4,3,3,2,2,2,2,1,1) Danach erhält man direkt (da D´ bereits sortiert ist) D`` = (2,2,1,1,2,2,1,1) D´´ muß nun erst sortiert werden, dazu werden die Knotennummern mit aufgeführt

42

Michael Gamer

Beispiel Valenzsequenz 2/2

Da die Knoten 1 und 2 bereits entfernt wurden haben wir nun:

Sortieren liefert

43

3 4 5 6 7 8 9 102 2 1 1 2 2 1 1

3 4 7 8 5 6 9 102 2 2 2 1 1 1 1

Michael Gamer

Beispiel Valenzsequenz

Abtrennung des ersten Knotens liefert:

Und daraus

Sortieren

44

4 7 8 5 6 9 102 2 2 1 1 1 1

4 7 8 5 6 9 101 1 2 1 1 1 1

8 4 7 5 6 9 102 1 1 1 1 1 1

Michael Gamer

Beispiel Valenzsequenz

Erneutes Abspalten des ersten Knotens liefert:

Und dann

Damit kann der Graph rückwärts konstruiert werden.

45

4 7 5 6 9 101 1 1 1 1 1

4 7 5 6 9 100 0 1 1 1 1

Michael Gamer

Valenzsequenzen: Konstruktion des Graphen

56

9 104

78

46

4 7 5 6 9 100 0 1 1 1 1

8 4 7 5 6 9 102 1 1 1 1 1 1

45

6

7

9 10

Michael Gamer

Valenzsequenzen: Konstruktion des Graphen

5

6

9 104

7 8

3

910

47

3 4 7 8 5 6 9 102 2 2 2 1 1 1 1

2 3 4 5 6 7 8 9 104 3 3 2 2 2211 1

Achtung: ursprüngliche

Sortierung beachten!

5

62

4

7

3

8

Michael Gamer

Valenzsequenzen: Konstruktion des Graphen

48

1 2 3 4 5 6 7 8 9 105 5 4 4 3 3 2 2 1 1

5

6

2

4

7

3

8

1

910

Michael Gamer

Das war anstrengend!

Gehen wir spazieren… z.B. durch Königsberg

49

Michael Gamer

Königsberg – über sieben Brücken mußt Du gehen!

50

Michael Gamer

Die Lösung

51

Start

Ziel

1

22

2

3

Es darf maximal zwei Punkte geben in denen eine ungerade Anzahl von Strecken endet!

Michael Gamer

Nochmals Königsberg

52

C

F

B

A

Michael Gamer

Eulertouren

‣Ein Spaziergang v0e1v1e2...emv0 von v0 nach v0 heißt Eulertour, wenn er jede Kante genau einmal benutzt. ‣Der Graph G heißt eulersch, wenn er eine Eulertour

ausgehend von einem (und damit von jedem) Knoten v0 ∈ V hat.

53

Michael Gamer

Charakterisierung Eulerscher Graphen

‣ Sei G=(V,E) ein Graph, dann sind folgende Aussagen (paarweise) äquivalent • G ist eulersch • G ist zusammenhängend und alle Knoten haben

einen geraden Knotengrad • G ist zusammenhängend und E die disjunkte

Vereinigung von Kreisen

54

Michael Gamer

Gebiete

Die von einem zusammenhängenden, planaren Graphen eingeschlossenen Polyeder heißen Gebiete

55

1

2

4

3

7

6

5

G1G2

G3

G4

Michael Gamer

Die Eulersche Polyederformel

Sei G=(V,E) ein zusammenhängender, planarer Graph mit ‣ |V|=n ‣ |E|=m ‣ und G schließe g Gebiete ein

dann gilt:

56

n-m+g = 2

Michael Gamer

Beispiel Eulersche Polyederformel

57

|V| - |E| + g = 2

|V| = 7 |E| = 10 g = 51

2

4

3

7

6

5

G1G2

G3

G4

G5

Michael Gamer

Bäume

• Ein zykelfreier Graph heißt Baum:

58

Dies

ist

sehr einfacher

ein

Baum

Michael Gamer

Beispiele von Bäumen

59

Michael Gamer

Wurzelbäume

‣ Ein Wurzelbaum (auch orientierter Baum) ist ein • zykelfreier • gerichteter • zusammenhängender

‣Graph mit einem ausgezeichneten Knoten, der Wurzel. ‣ Jeder Knoten des Graphen ist von der Wurzel aus

auf genau einem Weg erreichbar.

60

Michael Gamer

Nomenklatur für (Wurzel)Bäume

61

Blätter

Wurzel

innere Knoten

Michael Gamer

Binäre Bäume und Codes

‣Ein Wurzelbaum mit der Eigenschaft, daß jeder Knoten genau zwei oder keinen Nachfolger hat heißt binärer Wurzelbaum ‣ Ist B ein Wurzelbaum, so definieren wir den Code

<B> dieses Baumes wie folgt: • Ist B ein einzelner Knoten (Blatt) so ist <B> := 01 • Hat B die Teilbäume B1, B2, … Bk so ist

<B> := 0<B1>< B2> … <Bk>1 Dabei werden die <Bi> lexikographisch (!) geordnet

62

Michael Gamer

Code eines Baumes

63

01 01

0101 001011

010010110 1

Michael Gamer

Isomorphie von Bäumen (Algorithmus)

‣Sind zwei Bäume gegeben, so ist auf den ersten Blick oft nicht ersichtlich, ob diese identisch (isomorph) sind. Folgendes Verfahren stellt die Isomorphie von Bäumen fest:

• Die Bäume werden in spezieller Weise mit dem eben dargestellten Algorithmus codiert:

• Wir entfernen alle Blätter des Baumes, so lange, bis entweder nur ein Knoten (Fall 1), oder aber zwei Knoten übrig sind (Fall 2).

• Fall 1: ๏ <B> ist der Code des Baumes

• Fall 2: ๏ Wir entfernen die (letzte) Kante und codieren die beiden Teilbäume B1 und B2

๏ Sei o.E. |B1| < |B2| ๏ Dann ist <B> =0<B1><B2>1

๏ Bäume mit gleichen Code sind isomorph

64