Relevanz und Motivation

Entstehung von Theorien und Modellen

• Meist aus einem praktischen Problem heraus
• Zusammentragen aller Fakten die damit irgendwie zu tun haben
• Weglassen aller Dinge die keinen direkten Einfluss habe
• Verallgemeinerung / Abstraktion
• Finden von Ähnlichkeiten mit bekannten einfacheren Dingen
• Entwurf eines Modells mit diesen einfacheren Dingen
• Verhältnismäßig einfache Bestimmung von übertragbaren Eigenschaften und Konsequenzen

Leonard Euler 1737

• Problem der Königsberger Brücken
• Weglassen von Entfernungen und Ausmaßen
• Einfluss haben nur Stadtteile und Brücken
• Abstraktion zu Punkten mit Verbindungslinien
• Lösung des Problems mit Punkten und Verbindungen löst auch das Problem mit Stadtteilen und Brücken
• Entstehung des Graphenmodells

Die Graphentheorie als Modell

• Sehr minimalistisch, nur Punkte mit Verbindungen
• Dadurch übertragbar auf alle Arten von Beziehungen zwischen Objekten
  • Städte und Zugverbindungen
  • Freundschaften zwischen Menschen
  • Verlinkung von Internetseiten
• Viele praktische Probleme lassen sich zu einem Graphenproblem umformulieren
  • Ausfallwahrscheinlichkeit von Netzwerken
  • Routenermittlung bei der Navigation
  • Einstufung der Wichtigkeit von Einzelnen in einer Gruppe
• Graphentheorie stellt bereits Lösungen zur Verfügung
• Meist ist "nur noch" eine Interpretation erforderlich

Arbeiten mit dem Graphenmodell

• Mathematik des Modells ist gut dokumentiert
• Kritisch sind die Transformationen
  • Formulierung eines praktischen Problems im Graphenmodell
  • Interpretation des mathematischen Ergebnisse für die Praxis
• Falsche Formulierung oder falsche Interpretation liefert keine Problemlösung
• Zeitverteilung eines Softwareentwicklers: 10% tippen, 90% denken
• Gute Programmierer denken immer abstrakt (also in Modellen)
• Wenn man viele Modelle kennt, muss man sich selbst keine ausdenken
• Die Einfachheit der Graphentheorie macht sie zu einem Universalmodell

Knoten und Kanten

Definition Graph

G=(V,E)|V=\{v_i|i>0\}, E=\{(v_i,v_j)|v_i\in V, v_j \in V\}

Was ist ein Graph

Zur grafischen Darstellung bieten sich Punkte und Linien an:
Bilder: Punkt, nur Kante, Kante mit einem Punkt, Punkt mit Schlinge, 3 Punkte, 3 Punkte mit nur einer Kante, 2 Kanten mit Punkten nebeneinander, 2 Punkte die durch mehrere Kanten verbunden sind, Punkte die durch geschwungene Kanten verbunden sind

Konsequenzen

• Ein Graph muss mindestens einen Knoten enthalten
• Ein Graph muss nicht unbedingt Kanten haben
• Eine Kante muss immer durch 2 (nicht zwingend verschiedene) Knoten begrenzt sein
• Ein Knotenpaar kann durch mehrere Kanten verbunden sein
• Zwei Graphen sind gleich, wenn sie die gleichen Knoten enthalten, die durch die gleichen Kanten verbunden sind

In der Praxis

• Knoten und Kanten werden immer als Objekte mit Beziehungen interpretiert
• Dadurch werden die Konsequenzen intuitiv klar
• Erst wenn es ein Objekt gibt, kann man etwas darüber aussagen: "ist allein"
• Zwei Objekte ohne Verbindung sind auch sinnvoll: "nicht allein, aber isoliert"
• Eine Beziehung findet per Definition immer zwischen Objekten statt
• Objekte müssen dabei nicht zwingend verschieden sein (z.B. Besitzer\leftrightarrowEigentümer)

Modellierung

• Transformation einer Gegebenheit/eines Problems ins Graphenmodell
• Scheinbar offensichtlich (Computernetzwerke, Straßen, Schaltungen)
• In der Praxis: Immer abhängig von der Problemstellung!
  

z.B. Menschen mit Freundschaften

• • Über wie viele "Zwischen-Freunde" kennt ein beliebiger Mensch einen beliebigen anderen?
  • Gibt es eine Ur-Freundschaft aus der alle anderen entstanden sind
  • !!!!!!!!!Besseres Beispiel finden!!!!!!!!!

Isomorphie

Grad eines Knotens

Programmtechnische Verarbeitung