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

Definition Kantenzug

Für n ≥ 2 nennt man einen Graphen P_n mit einer Folge von Knoten V(P_n) = (v_0, v_1, . . . , v_n) und einer Folge von Kanten E(P_n) = ({v_0, v_1}, {v_1, v_2}, . . . , {v_{n−1}, v_n}) einen Kantenzug der Länge n, sofern alle Kanten und Knoten mehrfach durchlaufen werden.

Also: Kanten und Knoten werden mehrfach durchlaufen

• geschlossender Kantenzug: Kantenzug mit Startknoten = Endknoten

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

Definition Kantenzug

Für n ≥ 2 nennt man einen Graphen P_n mit einer Folge von Knoten V(P_n) = (v_0, v_1, . . . , v_n) und einer Folge von Kanten E(P_n) = ({v_0, v_1}, {v_1, v_2}, . . . , {v_{n−1}, v_n}) einen geschlossenen Kantenzug der Länge n, sofern alle Kanten und Knoten mehrfach durchlaufen werden und v_0 = v_n ist.

Also: Ein geschlossener Kantenzug ist ein Kantenzug bei dem der Anfangsknoten gleich der Endknoten ist.

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

Weg

Definition Weg

Für n ≥ 2 nennt man einen Graphen P_n mit der Knotenmenge V(P_n) = {v_0, v_1, . . . , v_n} oder auch einer Folge von Knoten V(P_n) = (v_0, v_1, . . . , v_n) und der Kantenmenge E(P_n) = {{v_0, v_1}, {v_1, v_2}, . . . , {v_{n−1}, v_n}} einen Weg (oder Pfad) der Länge n, sofern keine Kante mehrfach durchlaufen wird. Knoten hingegen dürfen bei einem Weg mehrfach vorkommen (d. h. die Knoten vi müssen nicht notwendig paarweise verschieden sein).

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

Definition Einfacher Weg

Für n ≥ 2 nennt man einen Graphen P_n mit der Knotenmenge V(P_n) = {v_0, v_1, . . . , v_n} und der Kantenmenge E(P_n) = {{v_0, v_1}, {v_1, v_2}, . . . , {v_{n−1}, v_n}} einen einfachen Weg (oder Pfad) der Länge n, sofern keine Kante und kein Knoten mehrfach durchlaufen wird.

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

Kreise

Definition Kreis

Für n ≥3 heißt der Graph C_n mit V(P_n) = {v_0, v_1, . . . , v_n} oder auch V(P_n) = (v_0, v_1, . . . , v_n) und E(C_n) = {{v_0, v_1}, {v_1, v_2}, . . . , {v_{n−1}, v_n}} Kreis der Länge n.

Also: Ein Kreis ist ein geschlossener Weg mit vo = vn, mit mindestens drei Knoten.

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

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

Definition Einfacher Kreis

Für n ≥ 3 nennt man einen Graphen P_n mit der Knotenmenge V(P_n) = {v_0, v_1, . . . , v_n} und der Kantenmenge E(C_n) = {{v_0, v_1}, {v_1, v_2}, . . . , {v_{n−1}, v_n}} einen einfachen Weg (oder Pfad) der Länge n, sofern keine Kante und kein Knoten mehrfach durchlaufen wird.

Also: Ein einfacher Kreis ist ein geschlossener einfacher Weg mit vo = vn, mit mindestens drei Knoten.

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

Zusammenhang bei Graphen

Definition

• 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

Definition Enfernen von Kanten

Es sei G = (V,E) ein Graph. Das Entfernen einer Kante e ∈ E erzeugt aus G einen neuen Graphen G - e = (V,E~\$~{e}). Wenn F ∈ E eine Kantenteilmenge des Graphen G = (V,E) ist, so sei G - F der Graph, der aus G durch Entfernen aller Kanten aus F$ hervorgeht.

Also: Entfernung einer Kante -> neuer Graph bzw. Graphen

Definition Enfernen von Knoten

Als einen Knoten v ∈ V wird G - v als der Graph definiert, der aus G durch Entfernen des Knotens v hervorgeht. Das Entfernen eines Knotens v schließt hierbei das gleichzeitige Entfernen aller zu v inzidenten Kanten des Graphen ein.

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

Kontraktion

Definition Kontraktion

Die Kontraktion einer Kante e = \{u,v\} eines Graphen G ist das Entfernen von e mit der anschließenden Fusion der Endknoten u und v.

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

Definition

Es sei c(G) die Anzahl der Komponenten eines Graphen G. Ein Knoten v ∈ V mit der Eigenschaft c(G-v) > c(G) heißt eine Artikulation von G.

Also: 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)

Definition

Eine Kante e ∈ E eines Graphen G = (V,E) mit der Eigenschaft c(G-e) > c(G) heißt eine Brücke von G.

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

Definition

Ein Graph, bei dem je zwei Knoten benachbart sind, heißt vollständig.

Also: alle Knoten sind miteinander verbunden

Teilgraph und Untergraph

Teilgraph

Definition

Es sei G = (V_G,E_G) ein Graph. Ein Teilgraph von G ist ein Graph H = (V_H,E_H), dessen Knotenmenge E_H eine Teilmenge von E_G ist.

Also: Ein 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

Definition

Ein induzierter Teilgraph entsteht, wenn beim Obergraphen ein oder mehrere Knoten samt dessen inzidenten Kanten entfernt werden.

Untergraph

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

spannender Teilgraph

Definition

Beim spannenden Teilgraphen bleiben alle Knoten des Obergraphen erhalten. Die Knoten sind dabei zusammenhängend.

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

Skizziere induzierte Teilgraphen!

300pxpx

300pxpx

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

Definition

Also: Es bleiben nur die Knoten und Kanten erhalten, welche beide Graphen enthalten.

Graph $G$ und $G'$

$G\cap G'$

Operation: Vereinigung

Definition

Also: Zwei Graphen werden durch gleichen Knoten und Kanten vereinigt.

Graph $G$ und $G'$

$G\cup G'$

$G \sqcup G'$ = disjunkte Vereinigung

Operation: Differenz

Definition

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

Graph G und G'

G \setminus G'

Operation: Komplement

Definition

Der Komplementärgraph \overline{G} bzw. \overline{G'} eines Graphen G hat die selbe Knotenmenge wie der Ausgangsgraph. In \overline{G} bzw. \overline{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 die Bildung des Durchschnitts?

Welcher Graph entsteht durch Vereinigung?

Welcher Graph entsteht durch Differenz?

Wie sehen die komplementären Graphen aus?

Quellen

• Turau, 2009, Algorithmische Graphentheorie

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

• Tittmann, 2003, Graphentheorie

• 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

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