Mod-5.1 4. Modellierung mit Graphen Modellierung beschreibt Objekte und Beziehungen zwischen ihnen. Graphen eignen sich zur Modellierung für ein breites Aufgabenspektrum. Ein Graph ist eine Abstraktion aus Knoten und Kanten: * Knoten: Eine Menge gleichartiger Objekte * Kanten: Beziehung zwischen je zwei Objekten, 2-stellige Relation über Knoten Je nach Aufgabenstellung werden ungerichtete oder gerichtete Graphen verwendet. ungerichtet gerichtet Hannover Ziffer wählen Bielefeld abheben Kamen Paderborn Gespräch führen auflegen Kassel Unna Wünnenberg Beschränkung auf endliche Knotenmengen und 2-stellige Relation reicht hier aus. (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 501 Ziele: Intuitives Verständnis von Graphen in der Vorlesung: Erläuterung der Begriffe und Beispiele nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5 Verständnisfragen: * Geben Sie weitere Beispiele für Graphen an. -------------------------------------------------------------------------------- Mod-5.2 Themenübersicht 4.1 Grundlegende Definitionen gerichteter, ungerichteter Graph, Graphdarstellungen, Teilgraphen, Grad, Markierungen 4.2 Wegeprobleme Weg, Kreis, Rundwege, Zusammenhang 4.3 Verbindungsprobleme Spannbaum 4.4 Modellierung mit Bäumen gewurzelte Bäume, Entscheidungsbäume, Strukturbäume, Kantorowitsch-Bäume 4.5 Zuordnungsprobleme konfliktfreie Markierung, bipartite Graphen 4.6 Abhängigkeitsprobleme Anordnungen, Abfolgen (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 502 Ziele: Vielfalt der Anwendungen von Graphen in der Vorlesung: * Eindruck der Aufgabenbereiche vermitteln, * Beispiele skizzieren, * gerichtete und ungerichtete Graphen zuordnen. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5 -------------------------------------------------------------------------------- Mod-5.3 5.1 Grundlegende Definitionen Gerichteter Graph Ein gerichteter Graph G = (V, E) hat eine endliche Menge V von Knoten und eine Menge E gerichteter Kanten, mit E reflexsubset V multiply V. Die Kantenmenge E ist eine 2-stellige Relation über V. Beispiel: d c V = {a, b, c, d} E = {(a, b), (a, c), (a, d), (b, b), (b, c), (d, b), (d, c)} Eine Kante wird als (v, u) oder v -> u notiert. a b Eine Kante (v, v) heißt Schleife oder Schlinge. Die Definition von Graphen schränkt ein auf * endliche Graphen mit endlichen Knotenmengen, * einfache Kanten: - eine Kante verbindet nicht mehr als zwei Knoten, - von Knoten x nach Knoten y gibt es höchstens eine Kante Multigraph: Es kann mehr als eine Kante von Knoten x nach Knoten y geben (siehe Mod-5.7) (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 503 Ziele: Gerichteten Graph als Relation verstehen in der Vorlesung: Erläuterung der Begriffe. Synonyme: * Knoten: auch Ecke, engl. vertex * Kante: engl. edge * gerichtete Kante: engl. arc nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.1 -------------------------------------------------------------------------------- Mod-5.4 Ungerichteter Graph Ist die Kantenmenge E eines gerichteten Graphen eine symmetrische Relation, so beschreibt er einen ungerichteten Graphen: Zu jeder Kante x -> y aus E gibt es auch y -> x in E. d c d c Wir fassen zwei Kanten x -> y, y -> x zu einer ungerichteten Kante zusammen: {x, y} die Menge der Knoten, die die Kante verbindet. a b a b Ungerichtete Graphen werden auch direkt definiert: Ein ungerichteter Graph G = (V, E) hat eine endliche Menge V von Knoten und eine Menge E ungerichteter Kanten, mit E reflexsubset { {x, y} | x, y element V } Der abgebildete Graph mit ungerichteten Kanten: V = {a, b, c, d} E = { {a, b}, {a, c}, {a, d}, { b }, {b, c}, {d, b}, {d, c} } In dieser Notation ist eine Schleife eine 1-elementige Menge, z. B. { b } (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 504 Ziele: Zusammenhang zwischen gerichtetem und ungerichtetem Graph in der Vorlesung: * Zusammenhang erläutern, * Definition gegenüberstellen nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.1 -------------------------------------------------------------------------------- Mod-5.5 Darstellung von Graphen abstrakt: anschaulich: Knotenmenge V = {a, b, c, d} Graphik d c Kantenmenge E = {(a, b), (a, c), (a, d), (b, b), (b, c), (d, b), (d, c)} a b Datenstrukturen für algorithmische Berechnungen: Knotenmenge V Adjazenzmatrix AM mit n * n als Indexmenge Wahrheitswerten zur Darstellung Adjazenzlisten: zu jedem der (gerichteten) Kanten: Knoten i eine Folge von lineare Ordnung Knoten, zu denen er eine der Knoten AM(i, j) = (i, j) element E Kante hat (i, j) element E definieren a b c d a, b, c, d a (b, c, d) a f w w w b (b, c) b f w w f c () sei |V| = n c f f f f d (b, c) d f w w f Ungerichtete Graphen als gerichtete Graphen mit symmetrischer Kantenmenge darstellen (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 505 Ziele: Datenstrukturen für Graphen kennenlernen in der Vorlesung: Erläuterungen zu den beiden Darstellungen * Adjazenzmatrix: direkter Zugriff aber redundant * Adjazenzlisten: kompakt aber Suche nach Kanten. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.1 -------------------------------------------------------------------------------- Mod-5.6 Teilgraph Der Graph Gquotesingle = (Vquotesingle , Equotesingle ) ist ein Teilgraph des Teilgraph G' = (V', E') zu G Graphen G = (V, E), wenn Vquotesingle reflexsubset V und Equotesingle reflexsubset E. (Gilt für gerichtete und ungerichtete Graphen.) V' = {a, c, d} E' = {(a, d), (d, c)} Graph G = (V, E): d d c c V = {a, bV = {a, b, c, c, d}, d} E = {E = {(a,(a, b),b), (a,(a, c),c), (a,(a, d),d), (b(b, b), (b, b), (b, c),, c), (d, b), (d, c)}(d, b), (d, c)} a a b Teilgraph G'' zu G durch V'' = {a, c, d} induziert Zu einem Graphen G = (V, E) induziert eine Teilmenge der Knoten Vquotesingle reflexsubset V den Teilgraphen d c Gquotesingle = (Vquotesingle , Equotesingle ), wobei Equotesingle alle Kanten aus E enthält, deren Enden in Vquotesingle liegen. a (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 506 Ziele: Begriffe verstehen in der Vorlesung: Erläuterungen und Beispiele dazu nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.1 -------------------------------------------------------------------------------- Mod-5.6a Knotengrad Sei G = (V, E) ein ungerichteter Graph: v Der Grad eines Knotens v ist die Anzahl der Kanten {x, v}, die in v enden. 5 Sei G = (V, E) ein gerichteter Graph: v A: 3 Der Eingangsgrad eines Knotens v ist die E: 2 Anzahl der Kanten (x, v) element E, die in v münden. 5 Der Ausgangsgrad eines Knotens v ist die Anzahl der Kanten (v, x) element E, die von v ausgehen. Der Grad eines Knotens v ist die Summe seines Eingangs- und Ausgangsgrades. E:1 d c E:3 d c A:2 A:0 3 3 3 3 Der Grad eines gerichteten oder E:3 ungerichteten Graphen A:2 ist der maximale Grad 4 E:0 3 A:3 5 seiner Knoten. a b a b 3 Grad 5 Grad 4 (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 506a Ziele: Begriffe verstehen in der Vorlesung: Erläuterungen und Beispiele dazu nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.1 -------------------------------------------------------------------------------- Mod - 5.7 Markierte Graphen Ein Graph G = (V, E) modelliert eine Menge von Objekten V und die Existenz von Beziehungen zwischen ihnen. Viele Aufgaben erfordern, dass den Knoten und/oder den Kanten weitere Informationen zugeordnet werden. Dies leisten Markierungsfunktionen Knotenmarkierung MV : V arrowright WV, Hannover z.B. EinwohnerzahlTsnd: V arrowright Iota N Bielefeld 126 518 300 Kantenmarkierung ME :E arrowright WE, 77 30 Paderborn 163 Kamen 48 140 z.B. EntfernungKm: E arrowright Iota N 9 13 80 68 Kassel Unna 281 Wünnenberg 67 12 (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 507 Ziele: Markierungen verstehen in der Vorlesung: Begriffe und Beispiele erläutern nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.1 Verständnisfragen: Geben Sie weitere Beispiel für Markierungen -------------------------------------------------------------------------------- Mod - 5.7a Spezielle Kantenmarkierungen Ordnung von Kanten: E arrowright Iota N + e legt die Reihenfolge der Kanten fest, die von einem Knoten ausgehen, z. B. im Kantorowitsch-Baum von 1 2 links nach rechts. *d a 1 2 V := {a, b, c, d, e} x , +)} b c MV := {(a, x), (b, x), (c, y), (d,*), (e ME := {((e,a), 1), ((e,d), 2), ((d,b), 1), ((d,c),2)} x y Anzahl von Kanten: a E arrowright Iota N 1 modelliert mehrfache Verbindungen zwischen 2 c denselben Knoten. G ist dann ein Mehrfachgraph (Multigraph). 1 In der graphischen Darstellung schreibt man die b Anzahl an die Kante oder zeichnet mehrere Kanten. a c ME := {({a, b}, 2), ({a, c}, 1), ({b, c}, 1)} b (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 507a Ziele: Markierungen verstehen in der Vorlesung: Begriffe und Beispiele erläutern nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.1 Verständnisfragen: Geben Sie weitere Beispiel für Markierungen -------------------------------------------------------------------------------- Mod - 5.8 5.2 Wegeprobleme Beispiel: Königsberger Brückenproblem (Euler, 1736) a a d b d Pregel b c c Skizze von Königsberg Multigraph dazu a. Gibt es einen Weg, der jede der 7 Brücken genau einmal überquert und zum Ausgangspunkt zurückkehrt? b. Gibt es einen Weg, der jede der 7 Brücken genau einmal überquert? (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 508 Ziele: Berühmtes Modellierungsbeispiel in der Vorlesung: * Modellierung zeigen * Lösung erarbeiten nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.2 Verständnisfragen: Hinweis: * a: Begründen Sie Ihre Antwort mit dem Grad der Knoten auf solch einem Rundweg. * b: Für die Knoten, die nicht Endpunkte sind, gilt das Gleiche wie in (a). -------------------------------------------------------------------------------- Mod-5.9 Wege und Kreise Sei G = (V, E) ein ungerichteter Graph. Eine Folge von Knoten (v0, v1, ..., vn) mit {vi, vi+1} element E für i = 0,..., n-1 heißt ein Weg von v0 nach v a b n. Er hat die Länge n greaterequal 0. G1 Entsprechend für gerichtete Graphen: mit (vi, vi+1) element E für i = 0,..., n-1 c d a b Ein Weg (v0, v1, ..., vn) einer Länge n greaterequal 1 mit v0 = vn und paarweise verschiedenen Kanten (v0, v1), ..., (vn-1, vn) G2 heißt Kreis im ungerichteten Graphen und c d Zyklus im gerichteten Graphen. Ein gerichteter Graph der keinen Zyklus enthält heißt azyklischer Graph (engl. directed acyclic graph, DAG). (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 509 Ziele: Begriffe zu Wegen in der Vorlesung: Begriffe an Beispielen erläutern, nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.2 -------------------------------------------------------------------------------- Mod-5.10 Zusammenhang in Graphen Ein ungerichteter Graph G = (V, E) heißt zusammenhängend, wenn es für beliebige Knoten v, w element V einen Weg von v nach w gibt. Ein gerichteter Graph heißt unter derselben Bedingung stark zusammenhängend. Ein Teilgraph Gquotesingle = (Vquotesingle , Equotesingle ) eines ungerichteten (gerichteten) Graphen G = (V, E) heißt (starke) Zusammenhangskomponente, wenn * Gquotesingle (stark) zusammenhängend ist und wenn * G keinen anderen (stark) zusammenhängenden G3 Teilgraphen Gquotesingle quotesingle hat, der Gquotesingle als Teilgraph enthält. a b e f Zusammenhangskomponenten sind also c d g maximale Teilgraphen, die zusammenhängend sind. G a b 4 e f c d g (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 510 Ziele: Begriffe verstehen in der Vorlesung: Begriffe an Beispielen erläutern: * G3 ist nicht zusammenhängend. * G3 hat 2 Zusammenhangskomponenten. * Der durch {a,c,d} induzierte Teilgraph ist nicht Zusammenhangskomponente von G3. * G4 ist nicht stark zusammenhängend. * G4 hat 2 starke Zusammenhangskomponenten. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.2 -------------------------------------------------------------------------------- Mod-5.11 Spezielle Wege und Kreise Sei G = (V, E) ein ungerichteter, zusammenhängender, schleifenfreier Graph. Ein Euler-Weg bzw. ein Euler-Kreis in G ist ein Weg, der jede Kante aus E genau einmal enthält. a b a b a b c d c d c d (a, b, d, a, c, d) (a, b, d, c, a) (a, b, d, c, a) Euler-Weg Euler-Kreis Hamilton-Kreis G hat einen Euler-Kreis genau dann, wenn alle Knoten geraden Grad haben. G hat einen Euler-Weg, der kein Kreis ist, genau dann, wenn G genau 2 Knoten mit ungeradem Grad hat. Ein Hamilton-Kreis enthält jeden Knoten aus V genau einmal. (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 511 Ziele: Wege mit speziellen Eigenschaften in der Vorlesung: * Begriffe an Beispielen erläutern, * Königsberger Brückenproblem lösen nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.2 -------------------------------------------------------------------------------- Mod-5.12 Wegeprobleme mit Euler-Wegen 1. Königsberger Brückenproblem (Mod-5.8): Euler-Weg, Euler-Kreis 2. Kann man diese Figur in einem Zuge zeichnen? 3. Eine Inselgruppe mit n > 1 Inseln benötigt direkte Schiffsverbindungen zwischen allen Paaren von Inseln. Es gibt nur ein einziges Schiff. Kann es auf einer Tour alle Verbindungen genau einmal abfahren? Für welche n ist das möglich? 4. Planen Sie ein Gruselkabinett: Ein Haus mit n > 1 Räumen, 1 Eingangstür, eine Ausgangstür, beliebig vielen Innentüren. Jede Tür schließt nach Durchgehen endgültig. Die Besucher gehen einzeln durch das Haus. Es soll niemand E A eingesperrt werden. (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 512 Ziele: Aufgaben modellieren lernen in der Vorlesung: * Erläuterungen zu den Aufgaben. * Die Graphen zu den Aufgaben zeigen; * ihre Eigenschaften erkennen. * In (4) ist wird jeder Raum und die Umgebung als ein Knoten modelliert. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.2 -------------------------------------------------------------------------------- Mod-5.13 Wegeprobleme mit Hamilton-Kreisen 1. Traveling Salesmanquotesingle s Problem (Handlungsreisender): n Städte sind mit Straßen a 30 b bestimmter Länge verbunden. Gesucht ist eine kürzeste Rundreise durch alle Städte. 50 52 55 48 d 25 c 2. In einem n * n Gitter von Prozessoren soll eine Botschaft sequentiell von Prozessor zu Prozessor weitergegeben werden. Sie soll jeden Prozessor erreichen und zum Initiator zurückkehren. Für welche n ist das möglich? (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 513 Ziele: Aufgaben modellieren lernen in der Vorlesung: * Erläuterungen zu den Aufgaben. * Die Eigenschaften der Graphen erkennen. * In (1) wird die Entfernung als Kantenmarkierung modelliert. Allgemeine Hinweise zum Modellieren mit Graphen: * Rolle der Kanten sorgfältig klären, gerichtet, ungerichtet, markiert. * Häufig wird der Graph selbst nicht gebraucht, sondern nur bestimmte Eigenschaften, wie Knotengrad. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.2 -------------------------------------------------------------------------------- Mod-5.14 5.3 Verbindungsprobleme Modellierung durch Graphen wie bei Wegeproblemen (Abschnitt 5.2), aber hier interessiert die Existenz von Verbindungen (Wegen) zwischen Knoten, die Erreichbarkeit von Knoten, nicht bestimmte Knotenfolgen. Bäume Sei G = (V, E) ein G ungerichteter, zusammenhängender Graph 1 G2 G3 für alle folgenden Begriffe: Wenn G keine Kreise enthält, heißt er (ungerichteter) Baum. In Bäumen heißen Knoten mit Grad 1 Blätter. Für jeden ungerichteten Baum G = (V, E) gilt | E | = |V| - 1 G G 4 4 Ein zusammenhängender Teilgraph von G, der jeden Knoten aus V enthält und ein Baum ist, heißt Spannbaum zu G. 2 Spannbäume zu demselben Graphen G4 (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 514 Ziele: Begriff Spannbaum verstehen in der Vorlesung: Erläuterungen und Beispiele zu den Begriffen. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.3 -------------------------------------------------------------------------------- Mod-5.15 Modellierung mit Spannbäumen zu Graphen Ein Spannbaum ist ein zusammenhängender Teilgraph mit der kleinsten Anzahl Kanten. Er modelliert kostengünstigen Zusammenhang. 1. Aufständische Gefangene wollen eine 2. Alle Agenten A, ..., H sollen direkt minimale Anzahl von Gefängnistüren oder indirekt miteinander sprengen, so dass alle Gefangenen kommunizieren. Die Risikofaktoren freikommen: jeder paarweisen Verbindung sind: 4 A G 8 9 3 3 5 7 E C H 5 10 B 3 4 6 6 6 F D Es soll ein Netz mit geringstem Risiko gefunden werden. (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 515 Ziele: Anwendung von Spannbäumen erkennen in der Vorlesung: Erläuterungen zu den Modellierungen. * zu 1: Knoten modellieren Räume und Umgebung, Kanten modellieren die Türen. * zu 2: Graph mit Kantenmarkierung aufstellen; Spannbaum mit minimaler Kantensumme suchen. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.3 -------------------------------------------------------------------------------- Mod-5.16 Verbindung und Zusammenhang Sei G = (V, E) ein ungerichteter, zusammenhängender Graph. v ist ein Schnittknoten in G, wenn G ohne v nicht mehr zusammenhängend ist. e ist eine Brückenkante in G, wenn G ohne e nicht mehr zusammenhängend ist. G heißt orientierbar, wenn man für jede Kante eine Richtung so festlegen kann, dass der entstehende gerichtete Graph stark zusammenhängend ist. G ist genau dann orientierbar, wenn G keine Brückenkante hat. 1. In der Innenstadt sollen zur Hauptverkehrszeit alle Straßen zu Einbahnstraßen werden. Bleiben alle Plätze von überall erreichbar? 2. In einer Stadt sollen einzelne Straßen zur Reparatur gesperrt werden. Bleiben alle Plätze von überall erreichbar? Schnittknoten Brückenkante (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 516 Ziele: Zusammenhang zerstören in der Vorlesung: Erläuterungen zu den Begriffe und Modellierungen. * zu 1, 2: Gerichtete Brückenkante zerstört den Zusammenhang. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.3 --------------------------------------------------------------------------------