Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Graphentheorie

Graphentheorie für die Lösung von Problemen am Beispiel des Damenproblems
by

on 25 May 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Graphentheorie

Graphen
endliche Menge an Jungen mit jeweils einer oder mehreren Freundinnen
Frage: Kann jeder der Jungen eine seiner Freundinnen heiraten?
Das Heiratsproblem
Färbung
platziere 8 Damen auf einem Schachbrett, ohne dass sie sich bedrohen
Frage: Wie viele unterschiedliche Lösungen sind möglich?
Strategie: Spaltenweise neue Damen hinzufügen
übertragbar auf alle Schachbrettgrößen (nxn)
Weltrekord seit 2009: alle Lösungen für n=26 -> 22.317.699.616.364.044
Das Damenproblem
Graphentheorie für die Lösung von Problemen am Beispiel des Damenproblems
Aufbau
Was ist ein Graph?
Das Heiratsproblem - Matchingtheorie
Kartenfärbung - Knotenfärbung
Das Damenproblem
verleihen Sachverhalten eine Struktur, um sie systematisch zu bearbeiten
bestehen aus Knoten (V) und Kanten (E)
Endknoten = Knoten, die eine Kante verbindet
Knotengrad d(v) = Anzahl indizenter Kanten
Matchingtheorie
Matching = Paarung
Kanten deren Endknoten unterschiedlich sind
"klassisches Matching": maximale Anzahl an Dingen soll einander zugeordnet werden
gesättigter Knoten ist ein Endknoten einer Kante des Matchings
perfektes Matching, wenn alle Knoten gesättigt sind
graphentheoretisch: Existiert ein perfektes Matching im Graphen?
Phillip Halls Heiratssatz (1935)

Problem beruht auf Francis Guthrie (1852): Vier-Farben-Vermutung
Graphentheoretisch:
Knoten = Länder, Kanten = gemeinsame Grenze
Knoten werden Farben zugeordnet
Satz von Brooks (1941): Die minimale Farbanzahl ist maximal so groß, wie der höchste Knotengrad in einem Graphen.
kein Algorithmus zur Berechnung der minimalen Farbanzahl
www.math.kit.edu/iag3/lehre/topgraph2006s/media/deutschland.gif
Quellen
Bodendiek, Rainer/Lang, Rainer: Lehrbuch der Graphentheorie, Spektrum Akademischer Verlag, Berlin 1995.

Clark, John/Holton, Derek Allan: Graphentheorie. Grundlagen und Anwendung, Spektrum Akademischer Verlag, Heidelberg 1994.

Gallenbacher, Jens: Abenteuer Informatik. IT zum Anfassen – von Routenplaner bis Online-Banking, Spektrum Akademischer Verlag, 2. Auflage, Heidelberg 2008.

Klüver, Jürgen/Schmidt, Jörn/Stroica, Christina: Mathematisch-logische Grundlagen der Informatik, W3L-Verlag, Bochum 2006.

Nägler, Günter/Stopp, Friedmar: Graphen und Anwendungen. Eine Einführung für Studierende der Natur-, Ingenieur- und Wirtschaftswissenschaften, B.G. Teubner Verlagsgesellschaft, Leipzig 1996.

Hußmann, Stephan/Lutz-Westphal, Brigitte (Hrsg): Kombinatorische Optimierung erleben. In Studium und Unterricht, Friedr. Vieweg und Sohn Verlag, Wiesbaden 2007.
Full transcript