Grundbegriffe der Graphentheorie 1

Wiki-Quelltext dieser Seite.

<language>Java</language>
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=\{(v_a,v_b)|v_a, v_b \in V\}$

<popup name="Ausführliche Definition">
;Definition Graph
:$\color{red}G=\color{blue}(V,E\color{blue})$
:$V=\color{green}\{v\color{green}\}\color{magenta}|V \color{orange}{\neq \emptyset}$
:$E=\color{green}\{\color{blue}(v_a,v_b\color{blue})\color{magenta}|v_a, v_b \in V\color{green}\}$
<br/>
:Ein $\color{red}{Graph}$ ist ein $\color{blue}{geordnetes Paar}$, wobei dessen erstes Element eine $\color{green}{Menge}$ ist, $\color{magenta}{welche}$ $\color{orange}{nicht~leer}$ sein darf, und dessen zweites Element eine $\color{green}{Menge}$ von $\color{blue}{geordneten Paaren}$ ist, $\color{magenta}{deren}$ Elemente in der ersten Menge enthalten sein müssen.
<br/>
:Ist eine Menge von Knoten die durch Kanten verbunden sein können.
</popup>

==Was ist ein Graph?==
Zur grafischen Darstellung bieten sich Punkte und Linien an:<br/>
Bilder: Punkt, nur Kante, Kante mit einem Punkt, Punkt mit Schlinge, 3 Punkte, 3 Punkte mit nur einer Kante, 2 Kanten mit Punkten nebeneinander, 2 Punkte die durch mehrere Kanten verbunden sind, Punkte die durch geschwungene Kanten verbunden sind

==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 Objekt'''en''' statt
* Objekte müssen dabei nicht zwingend verschieden sein (z.B. Besitzer$\leftrightarrow$Eigentü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?
*# Mathematische Analyse ($\rightarrow$ mathematische Grundalgorithmus)
*# Verbesserung des Algorithmus (dynamic programming, divide & conquer, ...)
*# 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)<br/><code id="562384e909645">
class Graph{
	int[] vertices;
	Edge[] edges;
}
class Edge{
	int from;
	int to;
}
</code>
* 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<br/>!!!!!!!!!!Bild: Graph + Matrix!!!!!!!!
* 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:<br/><code id="5626b165b8dff">
class Graph<T>{
	T[][] adjacency;
}
</code>
* 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<br/>!!!!!!!!!!Bild: Graph + Liste!!!!!!!!
* Kante von a nach b vorhanden? $\mathcal{O}(n)$
* Anzahl anliegender Kanten am Knoten? $\mathcal{O}(1)$
* Speicherbedarf $\mathcal{O}(n+m)$
* Codebeispiel:<br/><code id="5626b165b8ea9">
class Graph<T>{
	int[] neighborIndex;
	T[] neighbors;
}
</code>
** Für jeden Knoten ein <tt>neighborIndex</tt> wo in <tt>neighbors</tt> seine adjazenten Knoten abgelegt sind<br/>!!!!!!Bild der Felder mit Pfeilen
** Knoten ohne Nachbar erkennbar wenn der Folgeknoten den gleichen <tt>neigborIndex</tt> hat<br/>Achtung! Sonderbehandlung des letzten Knotens
* weniger Speicherbedarf als Adjazenzmatrix wenn Graph nicht vollständig

==Kantenliste==
* Nur die Kanten (zwischen 2 Knoten) werden gehalten<br/>!!!!!!!!!!Bild: Graph + Kantenliste!!!!!!!!
* Kante von a nach b vorhanden? $\mathcal{O}(m)$
* Anzahl anliegender Kanten am Knoten? $\mathcal{O}(m)$
* Speicherbedarf $\mathcal{O}(m)$
* Codebeispiel:<br/><code id="5626b165b8f32">
class Graph<T>{
	T[][] edges; // second dimension is 2
}
</code>
* 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, w\}|\{v, w\} \in E\}|$

<popup name="Ausführliche Definition">
;Definition
:$\color{red}d(\color{orange}v)=\color{blue}|\color{green}\{\color{black}{\{\color{orange}v, w\}}\color{magenta}{|\{v, w\} \in E}\color{green}\}\color{blue}|$
<br/>
:Der $\color{red}{Grad}$ eines $\color{orange}{Knotens}$ ist die $\color{blue}{Mächtigkeit}$ der$ \color{green}{Menge}$ an $\color{black}{Kanten}$, $\color{magenta}{aus~der~Gesamtmenge~der~Kanten~des Graphen}$, die zu diesem $\color{orange}{Knoten}$ inzident sind.
<br/>
:Die Anzahl der Kantenenden die an einem Knoten anliegen.
</popup>
!!!!!!!!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<br/>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
<popup name="Beweis">
# Summe aller Grade ist $\color{blue}{gerade}$ wegen $\textbf{2}\cdot m$
# Summe aller $\color{blue}{geraden}$ Grade ist auch $\color{blue}{gerade}$
# Wegen 1. muss die Summe aller $\color{red}{ungeraden}$ Grade auch $\color{blue}{gerade}$ sein
# Wegen 3. muss die Anzahl der Knoten mit $\color{red}{ungeradem}$ Grad $\color{blue}{gerade}$ sein
</popup>
* Praktisch: schnelle Überprüfbarkeit einer Aussage<br/>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 <span style="font-size:88%">''($\mathcal{O}$ per Adjazenzmatrix)''</span>
** 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)<br/>Dadurch statt $9!=362.880$ Möglichkeiten, Einschränkung auf z.B. $2!\cdot 7!=10.080$ Möglichkeiten

=Wege und Kreise=

==Was ist ein Weg?==
* aneinander gehängten Kanten, welche zwei Endknoten besitzen
* Kanten dürfen nicht zweimal durchlaufen werden
* Knoten dürfen hingegen mehrfach vorkommen
* die Knotenabzahl ist dabei um 1 höher als die Kantenanzahl (siehe Abb.???)

Beispiel:

[[Bild:Ghx8_;_Wege.png|center|400px]]
Abb.: Verschiedene Darstellungen des Weges.


* besonders wichtig sind die Wege als Teilgraphen eines größeren Graphen (siehe Abb.???)
* Beschreibung des Weges durch Benennung der Knoten


[[Bild:Ghx8 ;_Wegee.png|center|400px]]
Abb.??? Teilgrap (3,2,1,4,5).

==Zusammenhang bei Graphen==
Definition:

* zwischen zwei verschiedenen Knoten/Endknoten gibt es einen Weg
* Endknoten müssen verschieden sein, sonst erhält man Kreise 

Beispiel:

[[Bild:Ghx8 ;_KeinKreis.png|center|400px]]
Abb.: Ein nicht zusammenhängender Graph mit zwei Zusammenhangskomponenten; hier gibt es
beispielsweise zwischen Knoten 4 und Knoten 5 keinen Weg.

==Kreise==
Definition:

* Endknoten müssen verschieden sein, sonst erhält man Kreise 

* Kreise können auch Teilgraphen sein (Abb.???)

Beispiel:

[[Bild:Ghx8 ;_Kreise.png|center|400px]]
Abb.: Kreis als Teilgraph

=Operationen mit Graphen=
* Eigenschaften von Graphen
* Berechnung von Kenngrößen
* -> durch strukturelle Umformungen

==Entfernen von Knoten und Kanten==

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

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


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

Beispiel:


Folge:

Ein Graph ist genau dann zusammenhängend, wenn durch eine Folge von Kontraktionen nur ein Knoten übrig bleibt.

==Brücken und Artikulationen==

Es sei c(G) die Anzahl der Komponenten eines Graphen G. Eine Kante e ??? E eines Graphen G = (V,E) mit der Eigenschaften c(G-e)>c(G) heißt eine Brücke von G. Ein Knoten v ??? V mit der Eigenschaft c(G-v)>c(G) heißt eine Artikulation von G. In einem zusammenhängendem Graphen G sind Brücken und Artikulationen genau solche Kanten und Knoten, deren Entfernen aus G den Zusammenhang zerstört.

Beispiel:

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

Definition:

Ein Graph, bei dem je zwei Knoten benachbart sind, heißt vollständig. Für n ≥ 2 bezeichnen
wir den vollständigen Graphen auf n Knoten mit Kn.

Beispiel:

[[Bild:Ghx8 ;_VollstaendigeGraphen.png|center|400px]]

Der Übergang von Kn−1 zu Kn erfordert n − 1 neue Kanten, denn der hinzugefügte Knoten
ist mit jedem der bisher n − 1 vorhandenen Knoten zu verbinden. Damit erhält man für die
Kantenanzahl des Kn die Summe der Zahlen bis n −1:


{| class="wikitable"
|-
! Thema (n)  !! Anzahl der Kanten des Kn
|-
| 2          || 1 
|-
| 3          || 1 + 2 = 3
|-
| 4          || 1 + 2 + 3 = 6
|-
| 5          || 1 + 2 + 3 + 4 = 10
|-
| 6          || 1 + 2 + 3 + 4 + 5 = 15
|-
| 7          || 1 + 2 + 3 + 4 + 5 + 6 = 21
|}

Anzahl der Kanten eines vollständigen Graphen wächst damit quadratisch in der Knotenanzahl.

==Kantenanzahl==
xkdkf

=Abstände in Graphen=
bla
==Radius, Durchmesser und Zentrum==
bla

===Die Abstandsmatrix===
bla

=Gerüste=
bla
==Die Anzahl der Gerüste==
bla