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\}

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

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

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

Kantenfolge

• abwechselnde Folge von Knoten und Kanten
• jede Kante ist mit zwei verschieden Knoten inzident
• geschlossene Kantenfolge: Startknoten = Endknoten
• offene Kantenfolge: Startknoten und Endknoten sind verschieden

Kantenzug

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

Weg

• Kantenfolge, deren Knoten mehrfach vorkommen können; Kanten sind verschieden
• besonders wichtig sind die Wege als Teilgraphen eines größeren Graphen (siehe Abb.???)
• Beschreibung des Weges durch Benennung der Knoten

Einfacher Weg

• Kantenfolge, deren Kanten und Knoten nur einmal durchlaufen werden

Kreise

Kreis:

• geschlossener Weg

Einfacher Kreis:

• alle Knoten und Kanten müssen, außer Anfangsknoten und Endknoten, verschieden sein

Zusammenhang bei Graphen

• zwischen zwei verschiedenen Endknoten gibt es einen Weg
• zusammmenhängend: ungerichteter Graph
• Zweifacher Zusammenhang: wenn nach Entfernen eines beliebigen Knotens die verbleibenden Knoten zusammenhängend sind
• maximal zusammenhängender Teilgraph eines Graphen heißt Zusammenhangskomponente des Graphen

Operationen mit Graphen

Wozu?

• Beschreibung von Eigenschaften von Graphen und
• Berechnung von Kenngrößen

Wie?

• durch strukturelle Umformungen

Strukturelle Umformungen: Entfernen von Knoten und Kanten

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

Strukturelle Umformungen: Kontrakion

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

Beispiel:

Gerüste

• zusammenhängender kreisfähiger Untergraph eines Graphen, der alle Knoten des Graphen enthält
• ein nicht zusammenhängender Graph besitzt kein Gerüst
• Anwendung: Bestimmung von Strömen und Spannungen in elektrischen Netzwerken

Einteilung:

(I) Entstehung eines neuen Gerüstes durch Kontraktion: hier mit Entfernung von Schleifen

Beispiel:

(II) Entstehung eines neuen Gerüstes durch Entfernung einer Kante

Beispiel:

Strukturelle Umformungen: Fusion

• Verschmelzung zweier Knoten
• neue Knoten ist zu allen Kanten inzident, welche vorher einem dieser beiden Knoten als Endknoten hatten

Beispiel:

Artikulationen

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

Brücken

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

Operationen

1.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

Beispiel:

2.Operation: Schnitt

• Der neue Graph ist die Schnittmenge aus zwei Graphen.

Beispiel:

3.Operation: Vereinigung

• Der neue Graph ist die Vereinigung von zwei Graphen.

Beispiel:

4.Operation: Produkt

MUSS ICH NOCHMAL MACHEN!!!

Das Produkt zweier Graphen ist der Graph der entsteht, v aus G und v' aus G' zu den Knoten des neuen Graphen erklärt und jeweils eine Kante einfügt, wenn jeweils eine der beiden Knoten identisch ist und die jeweils andere Komponenten adjanzent sind.

Beispiel:

Vollständige Graphen

Der vollständige Graph bildet bei einer Reihe von Problemen die Grundlage der Modellierung.???

• Ein ungerichteter Graph heißt vollständig, wenn je zwei Knoten durch eine Kante verbunden sind.
• Jeder Knoten ist mit jedem Knoten verbunden
• Anzahl der Kanten eines vollständigen Graphen wächst damit quadratisch in der Knotenanzahl.
• Der vollständige Graph mit n-Knoten Ecken wird mit Kn bezeichnet

Beispiel:

Teilgraph und Untergraph

Teilgraph:

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

Beispiel:

Untergraph:

• ist ein Ausschnitt aus einem Graphen, dessen Knoten samt dessen inzidenten Kanten erhalten bleiben
• Jede Untergraph ist ein Teilgraph aber nicht umgekehrt

Beispiel:

induzierter Teilgraph = induzierter Untergraph:

• Entfernung eines Knotens samt seiner inzidenten Kanten!
• Die Anzahl aller möglichen induzierter Teilgraphen = Anzahl der Knoten
• = Clique

Beispiel:

spannender Teilgraph = spannender Untergraph:

• ist ein Teilgraph mit allen Knoten und reduzierter Kantenanzahl
• Die Anzahl aller möglichen spannenden Teilgraphen = Anzahl der Kanten

Beispiel:

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