Mathematik: Diskrete Mathematik: Graphentheorie


Vorwort Bearbeiten

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   nicht planar ist. Was das bedeutet und warum das so ist, werden wir im Folgenden sehen.

Geschichte Bearbeiten

 
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 Bearbeiten

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.

Kürzeste Wege Bearbeiten

Problem des Handlungsreisenden Bearbeiten

Heiratsprobleme Bearbeiten

Zeitplanung Bearbeiten

Frequenzen von Sendemasten Bearbeiten

Definitionen Bearbeiten

Graph (ungerichtet) Bearbeiten

Ein Graph G ist eine mathematische Struktur, die aus einer Knotenmenge V und einer Kantenmenge E besteht. Dabei gilt, dass die Knotenmenge   eine nicht-leere, endliche Menge ist und   (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}}

Graph (gerichtet) Bearbeiten

Nachbarschaft und Grad Bearbeiten

Zwei Knoten   heißen benachbart (auch adjazent), wenn  . Im obigen Beispiel sind z.B. 1 und 2 benachbart, 1 und 3 aber nicht.

Die Menge   wird als Nachbarschaft des Knotens x im Graphen G bezeichnet. Es gilt  . Im obigen Beispiel ist z.B.  .

Als Grad von x bezeichnet man  . Im obigen Beispiel ist somit  .

Ein Knoten x heißt isoliert, falls   gilt.

Isomorphe Graphen Bearbeiten

Zwei Graphen   und   heißen isomorph, wenn es eine Bijektion   gibt, so dass  .

Subgraph Bearbeiten

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

Schreibweise  .

Induzierter Subgraph Bearbeiten

Pfad Bearbeiten

Kreis Bearbeiten

Klique und Stabile Menge Bearbeiten

gerichtete Graphen Bearbeiten

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 Bearbeiten

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

 .

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:

 

Induktionsschritt:

Wenn wir einen Graphen haben für den Eulers Formel bereits gilt (d.h. ) 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  

Der andere Fall wäre, dass man eine Kante mit einem neuen Knoten hinzufügt. Dann gilt also 

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

Der Satz von Kuratowski Bearbeiten

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  oder den  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  und der  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   , wobei wir mit k die Länge des kürzesten Kreises ist.

Der Fall des  

Die Annahme wäre, dass der  planar ist. Dann gilt nach der Eulerschen Polyederformel  

Der kürzeste Kreis ist hier der Länge 3. Dann gilt nach obiger Ungleichung  , was ein Widerspruch ist, sodass der  nicht planar sein kann.

Der Fall des  :

Die Annahme wäre, dass der  planar ist. Dann gilt nach der Eulerschen Polyederformel  

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:  , was jedoch ein Widerspruch ist, sodass der  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  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.

Algorithmen Bearbeiten

Weblinks Bearbeiten

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