Ralf Zücker, Frank Ehrlich

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=\{(x,y)~|~x, y \in V\}

• V (für Vertices) ist die Menge der Knoten
• E (für Edges) ist die Menge der Kanten
• Man beachte: Es ist nicht festgelegt, was v eigentlich ist!

Was ist ein Graph?

Zur grafischen Darstellung bieten sich Punkte und Linien an:

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
• n für Anzahl der Knoten
• m für Anzahl der Kanten

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
  
• 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
  
• 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
    
  • 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
  
• 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)

Grad eines Knotens

Definition

d(v)=|\{(v,x)~|~(v,x) \in E\}| + |\{(y,v)~|~(y,v) \in E\}|

• 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:
  • 2 benachbarte Knoten haben immer gleich viele gemeinsame Nachbarknoten und
  • 2 nicht benachbarte Knoten haben immer gleich viele gemeinsame Nachbarknoten
• 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!
  
  • Die Adjazenzmatrix muss gleich sein von mindestens einer ihrer Permutationen =\mathcal{O}(n!)
  • Optimierung lt. Ullmann: 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
  • Hier gibts einen Ferrari zu holen...

Wege, Kreise und Zusammenhang

Kantenzug

• Kantenfolge deren Kanten und Knoten mehrfach auftreten
• geschlossender Kantenzug: Kantenzug mit Startknoten = Endknoten

• Kantenzug: {B,C,E,F,G,H,F,E,D}

• Kantenzug: {B,C,E,F,G,H,F,E,D,B}

Weg

• Knoten können mehrfach vorkommen; Kanten sind verschieden
• minimum 2 Knoten
• Beschreibung des Weges durch Benennung der Knoten
• Einfacher Weg: Kantenfolge, deren Kanten und Knoten nur einmal durchlaufen werden

• Weg: {C,E,F,G,J,F}

• Einfacher Weg: {C,E,F,G}

Kreise

• geschlossener Weg
• minimum 3 Knoten
• Einfacher Kreis: alle Knoten und Kanten müssen, außer Anfangsknoten und Endknoten, verschieden sein

• Kreis: {F,G,J,I,H,F}

• Einfacher Kreis: {F,G,J,F}

Zusammenhang bei Graphen

• zwischen zwei verschiedenen Endknoten gibt es einen Weg
• maximal zusammenhängender Teilgraph eines Graphen heißt Zusammenhangskomponente des Graphen

Übung

Strukturelle Umformungen

Entfernen von Knoten und Kanten

• Obergraph

• Entfernung einer Kante -> neuer Graph bzw. Graphen

• Entfernung eines Knoten -> neuer Graph, hierbei das gleichzeitige Entfernen aller zum Knoten inzidenten Kanten

Kontraktion

• entfernen einer Kante -> Fusion derer Endknoten
• dadurch Wegverkürzung
• wenn Endknoten = Endknoten des Weges -> Weglänge = 0
• wenn die Kante nicht auf dem Weg liegt, dann bleibt der Weg erhalten
• Folge: Ein Graph ist genau dann zusammenhängend, wenn durch eine Folge von Kontraktionen nur ein Knoten übrig bleibt.

• Obergraph

• Nach Kontraktion

Artikulationen (= Knoten)

• wenn durch Entfernung eines Knotens der Graph in zwei oder mehrere Komponenten zerfällt

• Kritische Knoten: blau

• Nach Entfernung der kritischen Knoten

Brücken (= Kanten)

• wenn durch Entfernung einer Kante der Graph in zwei oder mehrere Komponenten zerfällt

• kritische Kante: blau

• Nach Entfernung der Brücke

Übung

• Was passiert bei Entfernung einer Kante bzw. Knoten
• Was passiert bei Kontraktion?
• Wo ist die Artikulation?
• Wo ist die Brücke?

Vollständige Graphen

• Ein ungerichteter Graph heißt vollständig, wenn je zwei Knoten durch eine Kante verbunden sind.
• Jeder Knoten ist mit jedem Knoten verbunden

Teilgraph und Untergraph

Untergraph

• ist ein Ausschnitt aus einem Graphen, dessen Knoten samt dessen inzidenten Kanten erhalten bleiben
• wird auch als Clique bezeichnet

Teilgraph

• weniger Knoten und Kanten als der Ausgangsgraph
• ist ein Ausschnitt aus einem Graphen, bei der Kanten zwischen den Knoten fehlen können
• Kreise können auch Teilgraphen sein
• jeder Untergraph ist auch ein Teilgraph, aber nicht umgekehrt!

induzierter Teilgraph = Untergraph

• Entfernung eines Knotens samt seiner inzidenten Kanten

spannender Teilgraph

• ist ein Teilgraph mit allen Knoten und reduzierter Kantenanzahl

Übung

Welche Untergraphen gibt es?

Welche Teilgraphen gibt es?

Nenne induzierte Teilgraphen!

Wie sieht der spannende Teilgraph aus?

Grundlegende Operationen

Besonders häufig werden die üblichen Operationen der Mengenlehre (Vereinigung, Durchschnitt, Differenz und Komplement) auf Knoten- bzw. Kantenmengen von Graphen angewendet.

Operation: Komplement

• Komplementärgraph G' eines Graphen G hat die selbe Knotenmenge wie der Ausgangsgraph
• in G' sind genau zwei Knoten adjazent, wenn sie in G nicht adjazent sind

Graph G und G'

\overline{A}

Operation: Durchschnitt

Graph G und G'

G \cap G'

Operation: Vereinigung

Graph G und G'

G \cup G'

G \sqcup G'

Operation: Differenz

Graph G und G'

G \setminus G'

Übung

Quellen

• https://books.google.de/books?id=6w3OBgAAQBAJ&pg=PA358&dq=graph+Kantenfolge&hl=de&sa=X&ved=0CEMQ6AEwBmoVChMIrpDR4tjayAIVCVUaCh2Rmwpz#v=onepage&q=graph%20Kantenfolge&f=false

• https://books.google.de/books?id=JWGWbv-kB_EC&pg=PA401&dq=graph+einfacher+weg&hl=de&sa=X&ved=0CBwQ6AEwAGoVChMIioPj0-jayAIVQaIsCh0aWQw5#v=onepage&q=graph%20einfacher%20weg&f=false

• https://books.google.de/books?id=JWGWbv-kB_EC&pg=PA401&dq=graph+einfacher+weg&hl=de&sa=X&ved=0CBwQ6AEwAGoVChMIioPj0-jayAIVQaIsCh0aWQw5#v=onepage&q=graph%20einfacher%20weg&f=false

• https://books.google.de/books?id=xRSbBgAAQBAJ&pg=PA92&dq=elementarer+weg+graph&hl=de&sa=X&redir_esc=y#v=onepage&q=elementarer%20weg%20graph&f=false

• https://books.google.de/books?id=G70fBAAAQBAJ&pg=PA55&dq=graph+Kantenfolge&hl=de&sa=X&ved=0CDEQ6AEwA2oVChMIrpDR4tjayAIVCVUaCh2Rmwpz#v=onepage&q=graph%20Kantenfolge&f=false

• Turau, 2009, Algorithmische Graphentheorie