Mathematik: Diskrete Mathematik: Graphentheorie

Aus Wikibooks


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)

Beispiel für eine Darstellung eines gerichteten Graphen

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)