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 und Kreise

Wege

Kantenfolge (bzw. gerichtete 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
• 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

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

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

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

Elementarer Weg:

Ein elementarer Weg ist ein Kantenzug deren Knoten nur einmal durchlaufen werden. 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

Beispiel:

Abb.: Verschiedene Darstellungen des Weges.

Abb.??? Teilgrap (3,2,1,4,5).

Kreise

Kreis:

• Weg, bei der Startknoten und Endknoten gleich sind
• verschiedene Kanten, mehrfach auftretende Kanten

Einfacher Kreis:

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

Eulerische Kreise:

Graph ist zusammenhängend und alle Knoten haben einen geraden Knotengrad

Hamiltonsche Kreise:

Ein Kantenkreis heißt Hamiltonsch, wenn er alle Knoten des Graphen genau einmal enthält (Begin und Ende einmal gezählt).

Zusammenhang bei Graphen

Definition:

• zwischen zwei verschiedenen Endknoten gibt es einen Weg
• Endknoten müssen verschieden sein, sonst erhält man einen Kreis
• Baum = zusammenhängender Graph ohne Kreis

zusammmenhängend: ungerichteter Graph stark zusammenhängend: gerichteter Graph

Beispiel:

Abb.: Ein nicht zusammenhängender Graph mit zwei Zusammenhangskomponenten; hier gibt es beispielsweise zwischen Knoten 4 und Knoten 5 keinen Weg.

Quelle:

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

Operationen mit Graphen

Wozu?

• Eigenschaften von Graphen
• 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: Fusion

Bei der Fusion verschmelzen zwei Knoten u und v eines Graphen G = (V,E). Dieser neue Knoten ist zu allen Kanten inzident, welche vorher einem dieser beiden Knoten als Endknoten hatten.

Beispiel:

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

Anzahl der Gerüste

Einteilung:

(I) Entstehung eines neuen Gerüstes durch Kontraktion

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

(I)

• Entstehung eines neuen Gerüstes durch Kontraktion
• Kanten des Gerüstes
• entstehende Schlingen werden mit entfernt
• Kontraktion ist umkehrbar -> Anzahl an Gerüsten nach der Kontraktion = Anzahl an Gerüsten vor der Kontraktion

(II)

Strukturelle Umformungen: Brücken und Artikulationen

In einem zusammenhängendem Graphen sind Brücken (= Kanten) und Artikulationen (= Knoten) genau solche Kanten und Knoten, deren Entfernen den Zusammenhang zerstört.

Beispiel:

Operationen

1.Operation:

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

• Der neue Graph ist die Schnittmenge aus zwei Graphen.

Beispiel:

3.Operation:

• Der neue Graph ist die Vereinigung von zwei Graphen.

Beispiel:

4.Operation:

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

Definition:

• 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

Untergraph:

• ist ein Ausschnitt aus einem Graphen, dessen Knoten samt dessen inzidenten Kanten erhalten bleiben

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

induzierter Teilgraph = induzierter Untergraph:

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

spannender Teilgraph = spannender Untergraph:

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

kanten-induzierter Teilgraph:

knoten-induzierter Teilgraph:

Jede Unterstruktur ist eine Teilstruktur aber nicht umgekehrt.

Clique

Definition

• Teilgraph, der vollständig ist = induzierter Teilgraph