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 haben
• 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\}|V \neq \emptyset

E=\{(v_a,v_b)|v_a, v_b \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
• Adjazenz = Nachbarschaft = Es gibt etwas trennendes dazwischen
  • Nur zwischen Knoten und Knoten bzw. zwischen Kante und Kante
  • Dazwischen ist immer eine Kante oder ein Knoten
• Inzidenz = Angrenzung = Es gibt direkten Kontakt
  • Nur zwischen Knoten und Kante

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, Facebook-Freundschaften)
• In der Praxis: Immer abhängig von der Problemstellung!
• z.B. Kabelverlegung in einem Haus
  • Wie verlegt man die Kabel, sodass die verwendete Gesamtkabellänge minimal ist?
  • Wie teile ich eine 50m Kabelrolle auf, sodass der Verschnitt möglichst gering ist?
• Kein Patentrezept um von der konkreten Problemstellung zum abstrakten Graphenmodell zu gelangen
• Hilfreiche Fragen die man sich stellen kann
  • Welches Ergebnis wird gebraucht?
  • Welches Ergebnis der Graphentheorie soll genutzt werden?
• Oft helfen Zwischen-Abstraktionen anstatt direkt zu Knoten und Kanten zu abstrahieren
  • Zustände und deren Übergänge
  • Situationen und deren Änderung
• Grafische Darstellung von Graphen kann geometrische Körper ergeben

Programmiertechnische Verarbeitung

• Wie bilde ich das gestellte Problem programmtechnisch ab?
  1. Mathematische Analyse (\rightarrow mathematische Grundalgorithmus)
  2. Verbesserung des Algorithmus (dynamic programming, divide & conquer, ...)
  3. Definition der Datenstruktur zur effizienten Unterstützung des Algorithmus
• Wahl der Datenstruktur immer nach Anforderungen des Algorithmus
  • Soll der Graph variabel sein? (Array vs. Hashset)
  • Gibt es isolierte Knoten? (Redundanz erforderlich)
  • Welche Operationen sollen durchgeführt werden? (Zugriff, Suche, Manipulation)
• Speicherbedarf vs. Effizienz

Naive Herangehensweise

• Streng nach Definition: Menge von Knoten + Menge von Kanten (zwischen Knoten)
  
  class Graph{ int[] vertices; Edge[] edges; } class Edge{ int from; int to; }
• Kante von a nach b vorhanden? \mathcal{O}(m)
• Anzahl anliegender Kanten am Knoten? \mathcal{O}(m)
• Speicherbedarf \mathcal{O}(n+2m)

Adjazenzmatrix

• Matrix der Größe n\times n, 0 oder 1 für jedes Punkte-Paar
  !!!!!!!!!!Bild: Graph + Matrix!!!!!!!!
• Kante von a nach b vorhanden? \mathcal{O}(1)
• Anzahl anliegender Kanten am Knoten? \mathcal{O}(n)
• Speicherbedarf \mathcal{O}(n^2) (oder doch etwas weniger möglich?)
• Codebeispiel:
  
  class Graph<T>{ T[][] adjacency; }
• Speicherbedarf unabhängig von der Kantenanzahl
• Bei großen Graphen nicht mehr möglich

Adjazenzliste

• Weglassen der Nullen in der Adjazenzmatrix
• Liste der Knoten mit deren Nachbarn
  !!!!!!!!!!Bild: Graph + Liste!!!!!!!!
• Kante von a nach b vorhanden? \mathcal{O}(n)
• Anzahl anliegender Kanten am Knoten? \mathcal{O}(1)
• Speicherbedarf \mathcal{O}(n+m)
• Codebeispiel:
  
  class Graph<T>{ int[] neighborIndex; T[] neighbors; }
  • Für jeden Knoten ein neighborIndex wo in neighbors seine adjazenten Knoten abgelegt sind
    !!!!!!Bild der Felder mit Pfeilen
  • Knoten ohne Nachbar erkennbar wenn der Folgeknoten den gleichen neigborIndex hat
    Achtung! Sonderbehandlung des letzten Knotens
• weniger Speicherbedarf als Adjazenzmatrix wenn Graph nicht vollständig

Kantenliste

• Nur die Kanten (zwischen 2 Knoten) werden gehalten
  !!!!!!!!!!Bild: Graph + Kantenliste!!!!!!!!
• Kante von a nach b vorhanden? \mathcal{O}(m)
• Anzahl anliegender Kanten am Knoten? \mathcal{O}(m)
• Speicherbedarf \mathcal{O}(m)
• Codebeispiel:
  
  class Graph<T>{ T[][] edges; // second dimension is 2 }
• Speicherbedarf unabhängig von der Knotenanzahl
• keine Unterstützung isolierter Knoten

In der Praxis

• Knoten und Kanten sind meist komplexere Datenstrukturen (beliebige Klassen)
• Bei Algorithmenimplementation generics bzw. templates benutzen
• Hilfsdatenstrukturen richtig verwenden (HashMap, HashSet)
• Redundanz vermeiden (Speicherbedarf minimieren), oder auch explizit nutzen (Effizienzsteigerung)

Die Qual der Wahl

• Gegenüberstellung

Grad eines Knotens

Definition

d(v)=|\{\{v, w\}|\{v, w\} \in E\}|

!!!!!!!!Bild verschiedener Graphen mit Knotenanzahl !!!!!!!!!! !!!!!!Popup mit dem gleichen Bild und markierung der stark regulären!!!!!!

• Einzelner Knoten ohne anliegende Kanten hat Grad 0 (isolierter Knoten)
• Schleife an einem Knoten erhöht den Grad um 2
• Haben alle Knoten den gleichen Grad ist der Graph regulär
  genauer: bei Grad k \rightarrow k-regulär
• Stark regulär:
  • Benachbarte Knoten haben gleich viele gemeinsame Knoten und
  • Nicht benachbarte Knoten haben auch gleich viele Knoten
• Ein Graph hat: Minimalgrad, Maximalgrad, Durchschnittsgrad
• Wichtig: \sum_{i=1}^n d(v_i)=2\cdot m
  • Summe aller Grade entspricht doppelter Kantenanzahl im Graph
  • Da jede Kante den Grad ihrer 2 angrenzenden Knoten um 1 erhöht
• Daraus folgt: Anzahl der Knoten mit ungeradem Grad muss gerade sein

• Praktisch: schnelle Überprüfbarkeit einer Aussage
  Unter 7 Unternehmen unterhält jedes Geschäftsbeziehungen zu genau 3 anderen Unternehmen. Möglich?

Isomorphie

• Gleichstrukturiertheit von Graphen G \sim G'
• Grafische Darstellung der Graphen kann ineinander überführt werden (Morphing)
• Achtung: Isomorphie <> Gleichheit
  • Knotennamen für Isomorphie irrelevant
  • Ebenso Kantenbewertungen
  • Aber: Kantenrichtungen dürfen nicht ignoriert werden
• Algorithmische Prüfung auf Isomorphie (\mathcal{O} per Adjazenzmatrix)
  • Anzahl der Knoten muss gleich sein =\mathcal{O}(1)
  • Anzahl der Kanten bzw. Summe der Grade muss gleich sein =\mathcal{O}(n^2)
• Das reicht aber noch nicht! !!!!!!!!Bild zweier nicht-isomorper Graphen mit gleichen Inv.!!!!!!
  • Die Adjazenzmatrix muss gleich sein
  • Von mindestens einer Permutation =\mathcal{O}(n!)
  • Optimierung lt. Ullman: Partitionieren! (Gruppierung von Knoten mit gleichem Grad)
    Dadurch statt 9!=362.880 Möglichkeiten, Einschränkung auf z.B. 2!\cdot 7!=10.080 Möglichkeiten