Mathematik: Diskrete Mathematik: Graphentheorie

Hoch zu Diskrete Mathematik Inhaltsverzeichnis

Vorwort

Die Graphen, mit denen sich die Graphentheorie beschäftigt, sind eine interessante mathematische Struktur. Sie spielen einerseits eine Rolle bei den Markov-Ketten aus dem Bereich der Wahrscheinlichkeitstheorie, sind ein wichtiges Instrument in fast jeder Disziplin der Informatik – angefangen von Endlichen Automaten aus der Theoretischen Informatik bis hin zur Routenberechnung für Navigationssysteme in der Geoinformatik – und spiegeln dabei Denkstrukturen wieder, die auch im Alltag oft vorkommen. So stehen hinter schematischen Darstellungen von U-Bahnnetzwerken genauso Graphen, wie sie auch hinter einem Organigramm stehen, das die Hierarchie einer Organisation beschreibt. Und so mancher Rätselfreund musste – möglicherweise nach langem Tüfteln – feststellen, dass es nicht möglich ist, drei Versorgungswerke mit drei Häusern überkreuzungsfrei zu verbinden. Dies liegt – graphentheoretisch – daran, dass der $K_{3,3}$ nicht planar ist. Was das bedeutet und warum das so ist, werden wir im Folgenden sehen.

Geschichte

Königsberger Brückenproblem im Stadtplan...

...und abstrakt als Graph (Orte durch Knoten, Brücken durch Kanten repräsentiert)

Im Jahre 1736 publizierte Leonhard Euler eine Lösung des Königsberger Brückenproblems. Im nebenstehenden Bild sieht man die sieben Brücken der Stadt Königsberg. Euler untersuchte die Frage ob es möglich ist, einen Rundgang durch Königsberg zu bestreiten, der jede der sieben Brücken über den Fluss Pregel genau einmal benutzt. Aus seinem Beweis, dass eben dies nicht möglich ist, entstand im Folgenden ein ganzer Zweig der Mathematik.

Motivierende Fragestellungen

Neben den bereits erwähnten Beispiel, bei dem nach einer Rundreise gefragt wurde, die jede Brücke genau einmal benutzt gibt es eine ganze Reihe weiterer Fragestellungen, die tatsächlich in der Praxis auftauchen und mit graphentheoretischen Mitteln gelöst werden. Wir wollen eine (unvollständige) Übersicht über typische Probleme geben. Für einige dieser Probleme wird auch eine Lösung präsentiert, aber dazu später.

Definitionen

Graph (ungerichtet)

Ein Graph G ist eine mathematische Struktur, die aus einer Knotenmenge V und einer Kantenmenge E besteht. Dabei gilt, dass die Knotenmenge $V$ eine nicht-leere, endliche Menge ist und $E\subseteq {\tbinom {V}{2}}$ (Menge von zwei-elementigen Teilmengen). Eine Kante verbindet zwei Knoten miteinander.

Schreibweise: G = (V,E)

Ein Beispiel:

Graph G

G = (V, E)

V = {1,2,3,4,5,6}

E = {{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}

Nachbarschaft und Grad

Zwei Knoten $x,y\in {V}$ heißen benachbart (auch adjazent), wenn $\{x,y\}\in E$. Im obigen Beispiel sind z.B. 1 und 2 benachbart, 1 und 3 aber nicht.

Die Menge $N_{G}(x)$ wird als Nachbarschaft des Knotens x im Graphen G bezeichnet. Es gilt $N_{G}(x)=\{y\in V:\{x,y\}\in E\}$. Im obigen Beispiel ist z.B. $N_{G}(2)=\{1,3,5\}$.

Als Grad von x bezeichnet man $deg(x)=|N_{G}(x)|$. Im obigen Beispiel ist somit $deg(2)=3$.

Ein Knoten x heißt isoliert, falls $deg(x)=0$ gilt.

Isomorphe Graphen

Zwei Graphen $G_{1}=(V_{1},E_{1})$ und $G_{2}=(V_{2},E_{2})$ heißen isomorph, wenn es eine Bijektion $f:V_{1}\rightarrow V_{2}$ gibt, so dass $\forall x,y\in V_{1}:{\Bigl \{}\{x,y\}\in E_{1}\Rightarrow \{f(x),f(y)\}\in E_{2}{\Bigr \}}$.

Subgraph

Ein Graph H=(W,F) heißt Subgraph von G=(V,E), wenn $W\subseteq V$ und $F\subseteq E$.

Schreibweise $H\subseteq G$.

gerichtete Graphen

In vielen Anwendungen ist es notwendig, den Kanten eine Richtung zu geben. In der Darstellung stellt man diese Richtung durch einen kleinen Pfeil dar.

Hier ein Beispiel für die Darstellung eines gerichteten Graphen: (Graphik stammt aus Wiki-Commons)

Planare Graphen

Graphen können wie bereits ersichtlich graphisch als Diagramm gezeichnet werden. In manchen Diagrammen kommt es dabei zu Überschneidungen von Kanten. Möglich ist es aber, dass sich Kanten in einem Knoten treffen. Man könnte jedoch auch eine andere Anordnung der Knoten wählen bzw. die vorhandenen Kanten anders zeichnen und vielleicht gäbe es dann keine Überschneidungen. Um dies zu klassifizieren bezeichnet man Graphen, die ohne Überschneidungen von Kanten, wenn sie in einer Ebene gezeichnet werden, als planar.

Hier sieht man wie ein Graph sowohl ein Diagramm mit und ohne Überschneidung von Kanten haben kann.

Doch wie kann man entscheiden ob ein Graph planar ist ohne jedes mögliche Diagramm zu zeichen.

Die Eulersche Polyederformel

Der Ikosaeder für den auch die Formel gilt

Diese Formel des bereits bekannten Leonhard Euler beschreibt die Zusammenhänge zwischen der Anzahl der Flächen, Kanten und Knoten eines Graphen. Jeder Graph besitzt mindestens eine Fläche nämlich die Fläche außerhalb des Graphen. Weitere Flächen entstehen dann wenn Kanten einen Kreis bilden, man also von einem Punkt in dieser Fläche nicht jeden weiteren Punkt außerhalb erreichen kann ohne eine Kante oder einen Knoten zu kreuzen. Der Name Polyeder kommt daher, dass man den Satz auch für Polyeder(griech. Vielflächer, also Körper wie z.B. Würfel) verwenden kann. Diese können dann auch als planarer Graph über ihr Körpernetz dargestellt werden.

Sei nun n die Anzahl der Knoten , k die Anzahl der Kante und f die Anzahl der Flächen. Dann gilt für planare Graphen:

$n+f=k+2$.

Ein Beweis mittels Induktion über die Anzahl der Kanten:

Induktionsanfang:

Ein Graph mit null Kanten besteht nur aus einem Punkt. Daher hat er nur eine Fläche und es gilt:

$1+1=0+2$

Induktionsschritt:

Wenn wir einen Graphen haben für den Eulers Formel bereits gilt (d.h.$n+f=k+2$) und eine weitere Kante hinzufügen, muss man 2 Fälle betrachten.

Entweder fügt man Kante hinzu die 2 Knoten miteinander verbindet und damit eine neue Fläche erschafft. Also gilt für diesen Graphen $n+(f+1)=(k+1)+2\Leftrightarrow n+f=k+2$

Der andere Fall wäre, dass man eine Kante mit einem neuen Knoten hinzufügt. Dann gilt also$(n+1)+f=(m+1)+2\Leftrightarrow n+f=m+2$

• 
  Der einfache Fall
• 
  Hinzufügen einer Kante mit neuem Knoten
• 
  Hinzufügen einer Kante, die 2 Knoten miteinander verbindet

Weitere Beweise lassen sind über ein Weblink verfügbar.

Der Satz von Kuratowski

Zum Verständnis dieses Satzes ist es wichtig den Begriff des Subgraphen zu kennen(falls nicht siehe oben)

Ein weiterer wichtiger Begriff ist der Begriff des Unterteilungsgraphen eines Graphen. Dies bedeutet, dass wenn man eine Kante zwischen 2 Knoten u und v hat, diese durch einen neuen Knoten w und 2 Kanten, die zwischen u und w sowie w und v verlaufen, ersetzen kann.

Ein Beispiel des Satzes von Kuratowski anhand des Petersen-Graphs

Der Satz wurde vom polnischen Mathematiker Kazimierz Kuratowski 1930 bewiesen. Ein ähnlicher Satz, der aber etwas komplizierteres Wissen erfordert, ist der Satz von Wagner des deutschen Mathematikers Klaus Wagner.

Die Aussage des Satzes ist dann, dass ein Graph genau dann planar ist, wenn er nicht einen Unterteilungsgraph des $K_{3,3}$oder den $K_{5}$als Untergraph besitzt.

Der Beweis für diesen Satz ist recht kompliziert und wird deswegen hier nicht angeführt.

Dennoch lässt es sich einfach zeigen, warum wir wissen, dass der $K_{3,3}$und der $K_{5}$nicht planar sind:

Dafür betrachten wir, dass Flächen von Kreisen einer gewissen Länge umgeben sind. Gleichzeitig grenzt jede Kante an 2 Flächen, wird also wenn wir die Kanten, die jede Fläche begrenzen, 2 mal gezählt. Also haben wir eine Ungleichung $2m\geq kf$ , wobei k die Länge des kürzesten Kreises ist.

Der Fall des $K_{5}$

Die Annahme wäre, dass der $K_{5}$planar ist. Dann gilt nach der Eulerschen Polyederformel $f=10+2-5=7$

Der kürzeste Kreis ist hier der Länge 3. Dann gilt nach obiger Ungleichung $2\times 10\geq 3f\Rightarrow f\leq 6$, was ein Widerspruch ist, sodass der $K_{5}$nicht planar sein kann.

Der Fall des $K_{3,3}$:

Die Annahme wäre, dass der $K_{3,3}$planar ist. Dann gilt nach der Eulerschen Polyederformel $f=9+2-6=5$

In einem bipartiten Graphen hat jeder Kreis gerade Länge, daher muss jede Fläche von mindestens 4 Kanten umgeben sein. Dann gilt nach obiger Ungleichung: $2\times 9\geq 4f\Rightarrow f\leq 4$, was jedoch ein Widerspruch ist, sodass der $K_{3,3}$nicht planar sein kann.

Beispiel

Es gibt 3 Häuser in denen jeweils ein Bauer wohnt. Die 3 Bauern besitzen zusammen 3 Brunnen, die sie für ihre Arbeit benutzen. Jeder Bauer benutzt jeden Brunnen. Die Bauern mögen sich jedoch nicht und möchten sich nicht auf ihrem Weg treffen. Daher möchte jeder Bauer einen eigenen Weg zu jedem Brunnen ohne dass sich diese kreuzen. Ist das möglich ?

Lösung: Dieses Problem kann als Graph simuliert werden, sodass es sich auf die Frage stellt ob dieser planar ist. In diesem Fall ist es jedoch der $K_{3,3}$und dieser ist wie oben gezeigt nicht planar, sodass sich die Bauern wohl damit abfinden müssen, dass sie sich begegnen oder jeweils nur einen Brunnen benutzen.

Weblinks

https://www.ics.uci.edu/~eppstein/junkyard/euler/ Weitere Beweise für die Eulersche Polyedersatz(auf Englisch)