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

\color{red}G=\color{blue}(V,E\color{blue}),~V=\color{green}\{v\color{green}\},~V \color{orange}{\neq \emptyset},~E=\color{green}\{~\color{brown}\{x,y\color{brown}\}~\color{magenta}|~x,y \in V~\color{green}\}*

Gelesen: Ein \color{red}{Graph} ist ein \color{blue}{geordnetes~Paar}, wobei dessen erstes Element eine \color{green}{Menge} ist, welche \color{orange}{nicht~leer} sein darf, und dessen zweites Element eine \color{green}{Menge} von \color{brown}{Zweiermengen} ist, \color{magenta}{mit~der~Eigenschaft,~dass} die Zweiermengenelemente in der ersten Menge enthalten sein müssen.

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

• Zur grafischen Darstellung bieten sich Punkte und Linien an
• Welche der Darstellungen repräsentieren Graphen?
  

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

\color{red}d(\color{orange}v) = \color{blue}|~\color{green}\{~\color{brown}\{\color{orange}v,x\color{brown}\}~\color{magenta}{|~\{v,x\} \in E}~\color{green}\}~\color{blue}|*

Gelesen: Der \color{red}{Grad} eines \color{orange}{Knotens} ist die \color{blue}{Kardinalität} der \color{green}{Menge} von \color{brown}{Zweiermengen}, die diesen \color{orange}{Knoten} enthalten und \color{magenta}{in~E~enthalten~sind}.

• 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,J,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?
  • Antwort: {G}
• Wo ist die Brücke?
  • Antwort: Kante {G,H}

Vollständige Graphen

• alle Knoten sind miteinander 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

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

• • Antwort: {A,B,D,E,F,E} oder {G,B,A}

Welche Teilgraphen gibt es?

• • Antwort: {G,B,A} oder {G,B,A} ohne Kante {A,B}

Nenne induzierte Teilgraphen!

Wie sieht der spannende Teilgraph aus?

Grundlegende Graphenoperationen

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

Operation: Durchschnitt

• es bleiben nur die Knoten und Kanten erhalten, welche beide Graphen enthalten

Graph G und G'

G \cap G'

Operation: Vereinigung

• zwei Graphen werden durch gleichen Knoten und Kanten vereinigt

Graph G und G'

G \cup G'

G \sqcup G'

Operation: Differenz

• es bleiben die Knoten und Kanten erhalten, welche nur in G enthalten sind

Graph G und G'

G \setminus G'

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{G} und \overline{G'}

Übung

Welcher Graph entsteht durch Vereinigung?

Welcher Graph entsteht durch die Bildung des Durchschnitts?

Welcher Graph entsteht durch Differenz?

Wie sehen die komplementären Graphen aus?

Quellen

• https://books.google.de/books?id=Og8dBgAAQBAJ&pg=PA103&dq=graph+differenz&hl=de&sa=X&ved=0CDUQ6AEwBGoVChMI6-z8s87iyAIVxPNyCh0iFwtU#v=onepage&q=vereinigung&f=false

• Krischke/Röpcke, 2015, Graphen und Netzwerktheorie

• Tittmann, 2003, Graphentheorie

• Turau, 2009, Algorithmische Graphentheorie