1 Graphentheorie Prof. Dr. Dörte Haftendorn, Leuphana Universität Lüneburg, 2012 Gibt es in...

Graphentheorie

Prof. Dr. Dörte Haftendorn, Leuphana Universität Lüneburg, 2012 http://www.leuphana.de/matheomnibus

Gibt es in Königsberg einen Spaziergang, bei dem man jede der sieben Pregelbrücken genau einmal überquert?

Königsberger Brückenproblem

Gibt es in Königsberg einen Spaziergang, bei dem man jede der sieben Pregelbrücken genau einmal überquert?

Im Jahre 1736 Leonhard Euler löste das Problem allgemein

Was ist ein Graph?

und begründete damit die Graphentheorie

Ein Graph besteht aus einer Eckenmengeund einerKantenmenge

( , )G E K

Jede Kante verläuft von Ecke zu Ecke.

Ecken=verticesKanten=edges

E Mindestens eine Ecke

Gundbegriffe

Die Adjazenz-Matrix gibt an,durch wie viele Kanten die Ecken verbunden sind.

Der Grad einer Ecke ist die Anzahl der abgehenden Kanten.

Eulersche Begriffe

In einem Eulerschen Weg kommt jede Kante genau einmal vor.

Ein geschlossener Eulerscher Weg heißtEulerscher Kreis.

Kanten, die zu ihrer Startecke zurückkehren, heißen Schlingen.

Eulersche Begriffe

Ein geschlossener Eulerscher Weg heißtEulerscher Kreis.

Eulers Lösung:

Eulerscher Satz:

Einen Eulerschen Kreis gibt es genau dann, wenn alle Ecken einen geraden Grad haben.

Im Königs-berg-Graphen gibt es keinen Eulerschen Kreis.

Das Haus des Nikolaus

Eulerscher Satz:

Einen offenen Eulerschen Weg gibt es genau dann, wenn genau zwei Ecken einen ungeraden Grad haben.

Graphen in unserer Welt

Mit Graphen schafft man sichein

Modell der Wirklichkeit,

das einen bestimmten Zusammenhang deutlich macht und andere Aspekte der Wirklichkeit ausblendet.

Die geometrische Lage und Form spielt bei Graphen eigentlich gar keine Rolle.

Bei Streckenplänen wird allerdings ganz grob die gegenseitige Lage wiedergegeben.

Mit Graphen schafft man sichein

Modell der Wirklichkeit,

das einen bestimmten Zusammenhang deutlich macht und andere Aspekte der Wirklichkeit ausblendet.

Die geometrische Lage und Form spielt bei Graphen

eigentlich gar keine Rolle.

Bei Streckenplänen wird allerdings ganz grob die gegenseitige Lage wiedergegeben.

Routenplaner und Graphen

Die Routenplanerarbeiten mit

bewertetenGraphen

Routenplaner und Graphen

Die Routenplanerarbeiten mit bewertetenGraphenDie Bewertung kann Entfernung,Zeit, Kosten ....bedeuten.

Erstmal leichtereProbleme:

Stadtplanung und Graphen

die Bewertung Baukostenbedeuten.

Für das Stadt-bauamt kann

Optimierung und Graphen

Bewertung BaukostenRadwegbelag möglichst billig so erneuern, dass jede Kreuzung auf neuem Belag erreichbar ist.

Greedy-AlgorithmusProtokoll

greedy=gierig

Bewertung Baukosten

Eine Kante davon

wählen.

Nicht nehmen,

sonst wirdes ein Kreis. Radwegbelag

möglichst billig so erneuern, dass jede Kreuzung auf neuem Belag erreichbar ist.

Greedy-AlgorithmusProtokoll

Bewertung BaukostenRadwegbelag möglichst billig so erneuern, dass jede Kreuzung auf neuem Belag erreichbar ist.

Protokoll

Greedy-AlgorithmusEntstanden

ist ein „minimaler

Spannbaum“

Bewertung Baukosten

Ein Baum ist ein zusammenhängender Graph ohne Kreise.

Radwegbelag möglichst billig so erneuern, dass jede Kreuzung auf neuem Belag erreichbar ist.

Entstanden ist ein

„minimaler Spannbaum“

Bewertung Baukosten

Leitungsnetz verlegen, so dass jeder Knoten erreicht wird. Minimiere die Baukosten.

Greedy-Algorithmus

Übrigens: gibt es hier einen Eulerschen Weg?

Markiere solange die billigstenKanten, solange kein Kreisentsteht. Mache dann mit einer nächst teureren Kante weiter, bis ein Spannbaum entsteht.

ProtokollSelber machen

Bewertung Baukosten

Greedy-Algorithmus

Eulerschen Weg? Ja, denn genau zwei Ecken haben ungeraden Grad.

Markiere solange die billigstenKanten, solange kein Kreisentsteht. Mache dann mit einer nächst teuren Kante weiter, bis ein Spannbaum entsteht.

Protokoll

Bewertung Baukosten

Greedy-Algorithmus

Eulerschen Weg? Ja, denn genau zwei Ecken haben ungeraden Grad.

Markiere solange die billigstenKanten, solange kein Kreisentsteht. Mache dann mit einer nächst teuren Kante weiter, bis ein Spannbaum entsteht.

Protokoll

Graphen-Theorie

ist eins der spannendstenund dynamischsten mathematischen Themen zur Zeit.

Zwei Mathematikergreifen die Idee von „Sofies Welt“ auf…….

http://www-m9.ma.tum.de/Ruth/WebHome

Kürzeste-Wege-Bäume

Das ist das Routenplaner-Problem.

Dijkstra-Algorithmus.Wir suchen die kürzesten Wege von A aus zu allen anderen Ecken

Fertige Ecken: A

Unfertige Ecken:

Unbetretene Ecken Ecken: B C D E F G H I

Der „Wert“ einer Ecke ist seine Entfernung von A.

Aktive Ecke: A

Niederländischer Mathematiker Edsger Dijkstra, 1960

Sprich ij wie ei

Lassen Sie sich im Folgenden lediglich auf den Grundgedanken ein.

Es ist schwieriger zu lösen.

Dijkstra-Algorithmus.Wir suchen die kürzesten Wege von A aus zu allen anderen Ecken

Fertige Ecken: A

Unfertige Ecken:

Unbetretene Ecken Ecken: B C D E F G H I

Aktive Ecke: A

Niederländischer Mathematiker Edsger Dijkstra, 1960

Sprich ij wie ei

Lassen Sie sich im Folgenden lediglich auf den Grundgedanken ein.

Es ist schwieriger zu lösen.

Dijkstra-Algorithmus.Wir notieren an jeder Ecke Wert und Vorgänger.

Fertige Ecken: A

Unfertige Ecken: B1A, E9A, D2A,

Unbetretene Ecken Ecken: C F G H I

Aktive Ecke wird: B

Eine Ecke mit minimalem Wert wird neue aktive Ecke.

Fertige Ecken: A, B1A,

Unfertige Ecken: E9A, E8B, D2A, C7B,

Unbetretene Ecken Ecken: F G H I

Aktive Ecke wird: D

Die aktive Ecke ist fertig.

Fertige Ecken: A0, B1A, D2A,

Unfertige Ecken: E9A, E8B, C7B, E7D, H5D,

Unbetretene Ecken Ecken: F G I

Aktive Ecke wird: H

Fertige Ecken: A0, B1A, D2A, H5D

Unfertige Ecken: E9A, E8B, C7B, E7D, E6H, I9H

Unbetretene Ecken Ecken: F G

Aktive Ecke wird: E

Fertige Ecken: A0, B1A, D2A, H5D, E6H

Unfertige Ecken: C7B, I9H, I8E, F11E

Unbetretene Ecken Ecken: G

Aktive Ecke wird: C

Fertige Ecken: A0, B1A, D2A, H5D, E6H, C7B

Unfertige Ecken: I9H, I8E, F11E, F9C, G13 C,

Unbetretene Ecken Ecken:

Aktive Ecke wird: I

Eine Ecke mit minimalem Wert wird neue aktive

Fertige Ecken: A0, B1A, D2A, H5D, E6H, C7B, I8E

Unfertige Ecken: F11E, F9C, G13 C, G12I,

Aktive Ecke wird: F

Eine Ecke mit minimalem Wert wird neue aktive

Dijkstra-Algorithmus.Mit Wert und Vorgänger für jede Ecke haben wir den gesuchten Baum.

Fertige Ecken: A0, B1A, D2A, H5D, E6H, C7B, I8E, F9C, G10F

Unfertige Ecken: G13 C, G12I, G10F

Aktive Ecke wird: G

Die letzte aktive Ecke ist fertig.

Dijkstra-Algorithmus.

Fertige Ecken: A0, B1A, D2A, H5D, E6H, C7B, I8E, F9C, G10F

Das ist nun ein kürzeste-Wege-Baum.

Mit Wert und Vorgänger für jede Ecke haben wir den gesuchten Baum.

http://www-m9.ma.tum.de/Allgemeines/DijkstraApplet

Das ist das Routenplaner-Problem. Es wird gelöst vom Dijkstra-Algorithmus.

http://www-m9.ma.tum.de/Allgemeines/DijkstraApplet

InteraktiveVersion an der TU München

Dies ist Aufgabenblatt 6 bei der TUM

Logistik

1.Modellierung des Problems mit Graphen2.Bewertung des Graphen mit

1.Fahrzeiten oder2.Fahrkosten3.Streckenlänge….

Lösung des Kürzeste-Wege-Problems

Landkarten färben

Wie viele Farben brauchtman, wenn benachbarte Länder verschieden gefärbt sein sollen?

Modellierung desProblems mit Graphen:

Landkarten färben mit Graphentheorie

Wie viele Farben brauchtman, wenn benachbarte Hauptstädteverschieden gefärbt sein sollen?

Landkarten färben mit Graphentheorie

Wie viele Farben brauchtman, wenn benachbarte Hauptstädteverschieden gefärbt sein sollen?

Vier-Farben-SatzEs reichen immer vier Farben

Erst 1976 mit Computereinsatzbewiesen (Appel, Haken)

Eckenfärbung von Graphen

Die Ecken sollen so gefärbt werden, dassbenachbarte Ecken verschiedene Farbenhaben

Achtung: Der 4-Farbensatz gilt nur für Graphen ohne Kantenkreuzungen.

Mobilfunk-Konfliktgraphen

Überlappende Handybereiche brauchen verschiedene Sendefrequenzen. Eine Eckenfärbung des Konflikt-graphen zeigt, wie man Frequenzen zuordnen kann.

Mobilfunk-Konfliktgraphen

Überlappende Handybereiche brauchen verschiedene Sendefrequenzen. Eine Eckenfärbung des Konflikt-graphen zeigt, wie man Frequenzen zuordnen kann.

Konflikt-Graphen

Die Verkehrsströme werden Ecken.Wenn zwei in Konflikt geraten, werden sie durch eine Kante verbunden.

Konflikt-Graphen

Die Verkehrsströme werden Ecken.Wenn zwei in Konflikt geraten, werden sie durch eine Kante verbunden.

Konflikt-Graphen

Die Verkehrsströme werden Ecken. Wenn zwei in Konflikt geraten,werden sie durch eine Kante verbunden.Eine zulässige Eckenfärbung des Graphen zeigt: Verkehrsströme mit der gleichen Farbe dürfen gleichzeitig „Grün“ an ihrer Ampel haben.

Adjazenzmatrix dazu

Mehr dazu im Buch Nitzsche: Graphentheorie, tw.moodle Kap 11

Konflikt-Graphen

Die Verkehrsströme werden Ecken. Wenn zwei in Konflikt geraten,werden sie durch eine Kante verbunden.Eine zulässige Eckenfärbung des Graphen zeigt: Verkehrsströme mit der gleichen Farbe dürfen gleichzeitig „Grün“ an ihrer Ampel haben.

Adjazenzmatrix dazu

Mehr dazu im Buch Nitzsche: Graphentheorie, tw.moodle Kap 11

Graphentheorie in Büchern

Kombinatorische Optimierung erleben: Im Studium und Unterricht Stephan Hußmann (Autor), Brigitte Lutz-Westphal (Autor)

Manfred Nitzsche

Fuzzy-Logik

„weiche Logik“

www.mathematik-verstehen.de Bereich Algebra, Logik

Knotentheorie

www.mathematik-verstehen.de Bereich Knotentheorie, moodle Kap. 11

Zöpfe

Fraktale, Chaostheorie

www.mathematik-verstehen.de Bereich Fraktale

www.mathematik-verstehen.de Bereich Fraktale, moodle Kap.10

1 Graphentheorie Prof. Dr. Dörte Haftendorn, Leuphana Universität Lüneburg, 2012 Gibt es in...

Documents

Prof. Dr. Dörte Haftendorn, Leuphana Universität Lüneburg, 2013 Ein Blick ----- Einblick Wie wir in Mathematik für

Mathematik hat Geschichte Teil 4 Ägypter Prof. Dr. Dörte Haftendorn Leuphana Universität Lüneburg Folie 1

Kombinatorik und Graphentheorie - Fachrichtung Mathematik · PDF fileKombinatorik und Graphentheorie Skript nach der Vorlesung von Ernst-Ulrich Gekeler im SS 2009 (im Wesentlichen

Bauinformatik Vertiefte Grundlagen Graphentheorie

Probestudium Graphentheorie Die Mathematik von FACEBOOK Konstantinos Panagiotou

Klausur Mathematik für alle Aufgaben und Lösungen Prof. Dr. Dörte Haftendorn, Leuphana Universität Lüneburg, 07/08

Bernhard Riemann Prof. Dr. Dörte Haftendorn, Leuphana Universität Lüneburg, --> Geschichte --> Riemann Seinen Namen trägt das

Kurs3:ÜberRoutenplaner,eingefärbteLandkar ...€¦ · KURS3-GRAPHENTHEORIE Isomorphie Katharina Börsig Beispiel DenGraphG 1 kannmanauchsozeichnen: Dasheißt,dassdieseGraphengenaudasselbe

GeoGebra als universales dynamisches Werkzeug Prof. Dr. Dörte Haftendorn, Leuphana Universität Lüneburg, , Hannover 2008

Elternbefragung 2008 Grundschule am Königsberg Wolfstein Olaf Radolak 2008

Algebraische Kurven Prof. Dr. Dörte Haftendorn, Universität Lüneburg, Reisen in ein vergessenes und unerforschtes Land

Noch mehr Funktionen 1 Prof. Dr. Dörte Haftendorn, Leuphana Universität Lüneburg, 2013

1 Funktionen als zentrales Werkzeug Prof. Dr. Dörte Haftendorn, Leuphana Universität Lüneburg, 2015 Scheinwerfer Antenne

Mathematik hat Geschichte Prof. Dr. Dörte Haftendorn Universität Lüneburg

Vorlesung 1: Graphentheorie - ETH Z · Graphentheorie Markus Püschel David Steurer Algorithmen und Datenstrukturen, Herbstsemester 2018, ETH Zürich. Plan für die ersten Vorlesungen

Behandlung Singulärer Subsysteme mittels Graphentheorie

Einführung in die Graphentheorie - prof-dr-berger.de · 4 Berger: Graphentheorie senken und nicht zuletzt die Wartezeiten für Kunden und Personal verkürzen. Ohne die Algorithmen

DER KÖNIG VON KÖNIGSBERG - MIT KANT IN DIE … · "Wir sind froh, Sie hier zu ... floh er von dort und kehrte nach Königsberg zurück." Sprecherin ... ohne den Wirt in Moskau gemacht,

Mathematik hat Geschichte Prof. Dr. Dörte Haftendorn Universität Lüneburg Teil2 Mittelalter Leonardo von Pisa Fingerzahlen

Prof. Dr. Dörte Haftendorn Universität Lüneburg