Rückblick

Sortierte Folgen Bäume

Graphentheorie

Als ein Teilgebiet der Mathematik untersucht die Graphentheorie Beziehungen und Eigenschaften von Graphen. Die Graphentheorie spielt sowohl in der Mathematik als auch in der Informatik eine wichtige Rolle. Oft können algorithmische Probleme durch Graphenrepräsentation gelöst und umgekehrt Graphenproblematiken mit Hilfe von Algorithmen überwunden werden. Deshalb bilden Graphen einen essentiellen Teil der Komplexitätstheorie in der Informatik.

Königsberger Brückenproblem

Königsberger Brückenproblem in Form eines Graphen

Beim Königsberger Brückenproblem handelt es sich um eine mathematische Fragestellung aus dem 18. Jahrhundert. Königsberg wurde am Fluss Pregel erbaut, welcher sich im Stadtgebiet teilt. Über die beiden Flussarme wurden mehrere Brücken gebaut, um schnell von einem Stadtteil zum anderen zu gelangen. Im Jahr 1736 gab es sieben Brücken. Die Einwohner Königsbergs stellten sich die Frage, ob es möglich ist, alle sieben Brücken nur genau einmal zu überqueren. Wenn dies möglich ist, kann man auch einen Rundweg gestalten, bei dem man am Ende wieder am Ausgangspunkt ankommt?

Diesen Fragen nahm sich Leonhard Euler, ein bis heute bedeutender Mathematiker an. 1736 veröffentlichte er seine Arbeit "Solutio problematis ad geometriam situs pertinentis", in der er sich mit dem Königsberger Brückenproblem befasste. Er versuchte sich bei der Untersuchung des Problems nur auf die relevanten Informationen zu beschränken. So stellte er fest, dass es vier Stadtteile gab, die durch sieben Brücken verbunden sind. Er lässt jeden Stadtteil von einen Punkt repräsentiert und jede Brücke stellt eine Linie, also eine Verbindung zwischen zwei Stadtteilen dar. Nach dem Zusammenfügen aller dieser Informationen erhält man die Grafik auf der rechten Seite.

Durch dieses grafische Hilfsmittel ist leicht zu erkennen, dass das Königsberger Brückenproblem nicht lösbar ist. Beim Passieren eines Punktes (Stadtteil) müssen zwei Linien (Brücken) durchlaufen werden (hinein und hinaus). Egal wie in welcher Reihenfolge man versucht die Brücken zu überqueren, ist es unmöglich jede Brücke nur einmal zu benutzen. Somit ist auch ein Rundgang, bei dem Anfangs- und Endpunkt übereinstimmen unmöglich. Um beide Fragen positiv beantworten zu können, müsste von jedem Punkt eine gerade Anzahl von Linien ausgehen, d.h. ein Stadtteil muss mit einer geraden Anzahl von Brücken erreichbar sein. Die Zahlen geben die Anzahl an Linien (Brücken) an, die zum / vom Punkt (Stadtteil) führen.

Leonhard Eulers Arbeit zum Königsberger Brückenproblem gilt als eine der ersten Arbeiten auf dem Gebiet der Graphentheorie.

Applet: Königsberger Brückenproblem (Autoren: Reeken,Scholz,Großer,Frommer,Krivsky)

Grundlegende Begriffe

Teile eines Graphen

Um einen leichten Einstieg in die Theorie der Graphen zu ermöglichen, ist es von Nöten, grundlegende Begriffe dieses Themas zu erläutern.

Graphrepräsentation

Im Themenkomplex Graphrepräsentationen sollen Methoden zur Darstellung von Graphen behandelt werden. Dabei wird besonders auf die Struktur von Graphen Wert gelegt, da diese für das sich anschließende Thema, dem Durchsuchen von Graphen, bedeutsam ist.

Graph

Ein Graph G stellt ein Paar G = (V,E) bestehend aus einer endlichen Menge V und einer Menge E von zweielementigen Teilmengen V dar.

Teilgraph

Teilgraph bezeichnet den Teil eines Graphen, für den gilt: G_1 = (V_1,E_1) mit V_1 \subset V und E_1 \subset E

Ecke

Die endliche Menge V repräsentiert die Eckenmenge V, bestehend aus Ecken / Knoten (engl. vertex). Ecken sind einfache Objekte mit einem Namen oder einer Eigenschaft. Beispiel: V = {a,b,c,d} Dargestellt ist die Eckenmenge V mit den Ecken des Graphen.

Endecke

Endecken sind die Ecken, die durch eine Kante verbunden sind. So besitzt die Kante [a,b] die Endecken a und b.

Kante

Bei der Menge E handelt es sich um die Kantenmenge mit den Teilelementen Kanten (engl. edge), die Verbindungen zwischen je zwei Ecken darstellen. Sie treten stets paarweise auf, da sie die beiden Ecken, die sie verbinden enthalten. Kanten müssen nicht zwingend Verbindungen zweier Ecken sein, sie können genauso eine Ecke mit sich selbst verbinden. Beispiel: E = \{[a,b],[c,d],[a,c],[b,d]\}

Aufgabe
Stellen Sie die Kanten- und Eckenmenge für den Graphen auf der rechten Seite auf (Bild: Teile eines Graphen).

Schlinge

Eine Schlinge ist eine Kante der Form [a,a], wobei die Ecke durch die Kante mit sich selbst verbunden ist. Solche Kantenformen treten häufig bei der Repräsentation von Automaten (DEA, NEA) durch Graphen auf.

Grad

Der Grad (a) einer Ecke wird durch die Anzahl der zu dieser Ecke a inzidenten Kanten beschrieben. Eine Ecke, die den Grad 0 besitzt heißt isoliert.

Adjazenz / Inzidenz

Adjazent heißen zwei Ecken, wenn sie Nachbarn sind. Die Ecken a, b sind demnach adjazent, wenn §[a,b]§ ein Kante des Graphen G ist.
Zueinander Inzident nennt man zwei Kanten, die eine gemeinsame Endecke haben. Eine Ecke ist zu einer Kante inzident, wenn die Ecke Endecke der Kante ist.

Um sich in Graphen fortzubewegen sind weitere Begriffe nötig.

Kantenzug

Eine Folge von Ecken stellt einen Kantenzug der Länge n-1 in einem Graph dar, wenn gilt: w = (e_1,...,e_n), n > 1, so dass die Kante [e_j,e_j_+_1] \in K, für j = 1,...,n - 1
Der Kantenzug gilt als geschlossen, wenn e_n = e_1. Sollte der geschlossene Kantenzug alle Kanten einmal enthalten, so spricht man vom Euler-Zug.

Weg / Pfad und Kreis

Ein Weg / Pfad ist ein Kantenzug, wenn gilt: e_i \not= e_j, für i \not= j
Ein Pfad kann durch eine Liste repräsentiert werden, bei dem alle Ecken von Ecke a nach Ecke b aufgelistete sind. Die Ecken a,b müssen durch Kanten über beliebig viele Ecken verbunden sein.
Ist der Weg geschlossen, spricht man von einem Kreis.

Zyklus

Einen Zyklus besitzt ein Graph, wenn es einen einfachen Pfad gibt, bei dem Anfangs- und Endecke identisch sind.

Graphentypen

Gerichteter Graph

Ungerichteter Graph

Ein ungerichteter Graph ist ein einfacher Graph ohne Mehrfachkanten, dessen Kanten durch Linien repräsentiert werden. Man kann eine Kante sowohl von der Ecke a nach Ecke b überqueren, als auch umgekehrt. Ein solcher Graph stellt den einfachsten Graphentyp dar.

Gerichteter Graph

Im Gegensatz zum ungerichteten Graph ist es bei gerichteten Graphen nicht möglich Kanten nach Belieben zu nutzen. Es wird stattdessen stets eine Richtung unter Verwendung einens Pfeils vorgegeben. Der Pfeil zeigt von Ecke a nach Ecke b und gibt somit eine Art Einbahnstraße vor.

Multigraph

Als Mutltigraph werden komplexere Graphen bezeichnet, die in jede Richtung nicht nur eine Kante zwischen Ecken zulassen, sondern mehrere. Solche Kanten bezeichnet man als Mehrfachkanten. Ein Beispiel für einen Multigraph ist die Visualisierung des Königsberger Brückenproblems.

Unvollständiger Graph

Unvollständige Graphen enthalten nicht alle maximal möglichen Kanten, d.h. nicht jede Ecke ist mit jeder anderen Ecke durch eine Kante verbunden.

Vollständiger Graph

Drei vollständige Graphen A, B, C

Man bezeichnet einen Graph als vollständig, wenn alle Ecken miteinander durch eine Kante verbunden sind. Man spricht auch von einem Simplex. Zu beachten ist, dass Ecken nicht mit sich selbst durch Kanten verbunden werden müssen.

Ungewichteter Graph

Bei ungewichteten Graphen besitzen die Kanten keine Gewichte, d.h. die Gewichtung einer Kante spielt für diesen Graph keine Rolle.

Gewichteter Graph

Ein Graph kann als gewichtet bezeichnet werden, wenn seine Kanten Zusatzinformationen enthalten. So wird beispielsweise einer Kante eine Zahl zugeordnet, die Entfernungen oder Kosten repräsentiert. Sowohl gerichtete als auch ungerichtete Graphen können gewichtet sein. Der Graph G = (V,E) wird durch die Funktion \mathit{w : E } \rightarrow \mathbb{R} zum gewichteten Graph. Die Kante [a,b] besitz das Gewicht, welches durch \mathit{w(a,b)} bezeichnet wird.

Netzwerke

Erfüllt ein Graph die Eigenschafte eines gewichteten und gerichteten Graphens, so kann er als Netzwerk bezeichnet werden.

Baum

Ein Graph wird Baum genannt, falls er zusammenhängend ist und keinen Kreis enthält. Zusammenhängedn ist ein Graph, wenn es zu jedem Paar (e_i,e_j) einen Kantenzug gibt, der e_i und e_j verbindet.

Ungerichteter Graph ohne Mehrfachkanten

Gerichteter Graph ohne Mehrfachkanten

Ungerichteter Graph mit Mehrfachkanten

Gerichteter Graph mit Mehrfachkanten

Aufgabe
Erstellen Sie einen ungerichteten Graph mit V = \{A,B,C,D,E\}. Die Kanten sollen so gewählt werden, dass es sich um einen vollständigen Graph handelt. Geben Sie nun die Kantenmenge K an.

Aufgabe
Der fertige Graph aus der letzten Aufgabe dient als Grundlage für diese Aufgabe. Der Graph soll zu einem gerichteten Graph verändert werden. Geben Sie die Ecken- und Kantenmenge an.

Aufgabe
Der fertige Graph aus der letzten Aufgabe dient als Grundlage für diese Aufgabe. Entfernen Sie die Kanten, welche die Ecken A und D, sowie B und C miteinander verbinden. Gesucht sind die Ecken- und Kantenmenge. Wie viele Kanten wurden entfernt und wie viele wären es bei einem ungerichteten Graph? Sind die Eigenschaften vollständig, ungerichtet, ungewichtet und Netzwerk erfüllt?

Aufgabe
Welcher Unterschied ist bei den beiden Graphen G und H festzustellen?

Graph G

Graph H

Operationen an Graphen

Zugriff auf Informationen des Graphen

Der Zugriff auf Informationen von Ecken und Kanten spielt in der Graphentheorie eine große Rolle. Ohne Informationen, die mit den Kanten und Ecken verknüpft sind, wäre die Repräsentation mit Hilfe von Graphen unnütz. Kanten können beispielsweise Informationen, wie die Entfernung zwischen zwei Ecken enthalten. Man spricht dabei vom Gewicht einer Kante und von gewichteten Graphen. Da sowohl Ecken als auch Kanten oft in der Praxis als Objekte dargestellt werden, fällt es leicht Informationen anzuhängen, d.h. als Teil des Objektes zu speichern. Unter der Annahme, dass V = 1,...,n, könnte man die entsprechenden Informationen der Ecken in Arrays speichern. Alternativ bietet sich auch ein Hashtable statt eines Arrays an. Zugriffe können somit in konstanter Zeit abgearbeitete werden.

Navigation

Die Navigation im Graphen kann man erleichtern, wenn jeder Ecke die ein- und ausgehende Kante bekannt ist. Es sit oft sinnvoll diese Informationen in der Ecke zu speichern.

Kantenqueries

Ein Eckenpaar stellt gleichzeitig die entsprechende Kante dar. Man kann sich also die Frage stellen, ob die zugehörige Ecke existiert. Mit Hilfe eines Hashtables kann dies stets implementiert werden, doch solche Operationen wären entsprechend langsam. Eine effizientere Möglichkeit ist das Speichern der Umkehrkante einer gerichteten Kante, falls diese existiert. Durch das Hinzufügen eines weiteren Zeigers, welcher die Kante mit ihrer Umkehrkante verknüpft.

Erstellung, Umwandlung, Ausgabe

Um algorithmische Probleme zu lösen, sind Graphen sehr gut geeignet. Falls man eine Repräsentation gewählt hat, die für das aktuelle Problem nicht gut geeignet ist, kann man diese Graphenform stets in eine andere Form überführen. Dies ist in linearer Zeit möglich.

Aktualisierung

Das Hinzufügen oder Entfernen von Kanten und Ecken kann Algorithmen beschleunigen, weshalb solche Operationen sinnvoll sind.

Unsortierte Kantenabfolge

Gerichteter Graph (Referenzgraph)

Die wahrscheinlich einfachste Methode Graphen zu repräsentieren, ist das Aufzählen aller Kanten. Die Kanten werden ungeordnet aufgeschrieben und beinhalten dabei das Eckenpaar, das sie verbinden. Das Gewicht der Kante kann zusätzlich gespeichert werden. Für die Wahrnehmung des Menschen ist diese Form der Graphrepräsentation nicht übersichtlich genug, denn schon bei etwas größeren Graphen geht der Überblick schnell verloren. So ist zum Beispiel die Information, ob es sich um einen gerichteten oder ungerichteten Graphen handelt bei großen Graphen schwer zu ermitteln, da die Kanten ungeordnet vorliegen.
Trotzdem wird diese Graphrepräsentation häufig für Ein- und Ausgaben genutzt. Die einzelnen Operationen können größtenteils in \Theta (m) abgearbeitet werden. Dies ist jedoch sehr langsam und deshalb für große Graphen ungeeignet. Die nachfolgenden Repräsentationen arbeiten mit einer geordneten Reihenfolge.

Adjazenzfelder - Statische Graphen

Das Adjazenzfeld zum vorhergehenden gerichteten Referenzgraph

Um einen einfachen Zugriff auf die Kanten, die eine Ecke verlassen zu gewährleisten, ist es sinnvoll diese Kanten in einem Array zu sichern. Ohne Gewichte enthält dieses Array nur die Indizes der "Zielecken". Damit nicht jede Ecke ein eigenes Array für die "Zielecken" nutzt, ist es für statische Graphen nützlich all diese Informationen in einem Array zu sichern. Dieses Hauptarray soll E heißen. Um die Startpositionen der Unterarrays zu speichern, erstellt man ein kleineres Array V. Dieses zeigt dann für jede Ecke auf die Startposition im Hauptarray E und gibt somit die Informationen über die Kanten preis.
Jede Kante der Ecke v kann somit durch E[V[v]] erreicht werden.
Auffällig ist der geringere Speicherverbrauch dieser Graphrepräsentation, der bei n + m liegt. Es ist also deutlich kompakter als bei der ungeordneten Kantenabfolge, bei der der Speicherverbrauch bei 2m lag.
Will man weitere Informationen speichern, ist es möglich weitere Array hinzuzufügen, die diese Informationen aufnehmen.

Adjazenzliste - Dynamische Graphen

Zirkulär verkettete Liste zum Referenzgraph

Arrays sind kompakte und effiziente Graphrepräsentationen, mit der Ausnahme des Hinzufügens oder Löschens einer oder mehrerer Kante(n). Für solche Fälle ist der Rechenaufwand recht hoch. Will man beispielsweise eine Kante hinzufügen, so muss man alle Kanten rechts dieser neuen Kante um eine Stelle nach rechts verschieben.

Für solche dynamischen Graphen ist eine Adjazenzliste vorteilhaft, die für jede Ecke v eine Abfolge E_v der ein- und ausgehenden Kanten durch eine verkettete Liste oder ein ungebundenes Array repräsentiert.
In einer einfach verketteten Liste erhält jede Ecke eine Liste mit den Nachfolgern bei einem gerichteten Graph beziehungsweise mit den Nachbarn bei ungerichteten Graphen.

Adjazenzmatrix

Eine Darstellungsweise für Graphhen ist die Darstellung als Adjazenzmatrix. Diese Matrix besteht aus einem V mal V großen Feld mit booleschen Variablen, in der a[i,j] auf 1 oder true gesetzt wird, wenn von Knoten x zu Knoten y eine Kante vorhanden ist und auf 0 oder false wenn eine solche Kante nicht existiert.
In einem ungerichteten Graphen repräsentieren a[i,j] und a[j,i] die gleiche Kante, nämlich genau die Kante, die i und j verbindet. Das heißt, die Adjazenzmatrix A für einen ungerichteten Graphen ist gleich ihrer Transponierten. Es gilt A = A^T.
Beachtet man die Symmetrie der Adjazenzmatrix

Es sei ein Graph G =(V,E) mit von 1 bis |V| durchnummerierter Knoten gegeben.
Die Dazugehörige Ajazenzmatrix besteht aus:
|V|x|V|-Matrix A =(a_i_j) mit den Elementen a_i_j = \begin{cases} 1, & \text{falls }(i,j) \in \text{ E } \\ 0, & \text{sonst.} \end{cases}

ungerichteter Graph G_ung

• $\left(

  \begin{array}{ccc}
    a_{11} & \cdots & a_{1j} \\
    \vdots & \ddots & \vdots \\
    a_{i1} & \cdots & a_{ij}
  \end{array}

\right) $allgemein

• $\left(

  \begin{array}{ccccc}
    0 & 1 & 0 & 0 & 1 \\
    1 & 0 & 1 & 1 & 1 \\
    0 & 1 & 0 & 1 & 0 \\
    0 & 1 & 1 & 0 & 1 \\
    1 & 1 & 0 & 1 & 0 \\
  \end{array}

\right) $ungerichtet

• $\left(

  \begin{array}{cccccc}
    0 & 1 & 0 & 1 & 0 & 0 \\
    0 & 0 & 0 & 0 & 1 & 0 \\
    0 & 0 & 0 & 0 & 1 & 1 \\
    0 & 1 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 1 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 & 1 \\
  \end{array}

\right) $gerichtet

Frage

Pseudocode:

xyz

Inzidenzmatrix

Neben der Adjazenzmatrix, kann auch eine Inzidenzmatrix zur Darstellung eines Graphen im Computer verwendet werden. Diese beschreibt einen Graphen indem sie Knoten, welche mit Kanten inzident sind, angibt.

Implizite Repräsentation

Anwendungsgebiete

Verkehrsnetze

Netz der Wiener U-Bahn - ein praktisches Beispiel für Graphen

Chemische Isomerie

Strukturen in der organischen Chemie

Elektrische Netzwerke

Umfüllaufgabe

Aufgaben

1. Mit welcher Darstellung kann man schnell bestimmen, ob ein Knoten isoliert ist?

2.