13.6 Ausblick: Planare Graphen

Zum Schluss noch ein kleiner Ausblick auf ein weiteres Thema der Graphentheorie, auch wenn wir es hier nicht mit Methoden der Linearen Algebra in Verbindung bringen.

Definition 13.15

Sei $G$ ein Graph. Wir sagen, $G$ sei ein planarer Graph, wenn sich $G$ ohne Überschneidung von Kanten in der Ebene zeichnen lässt.

$\begin{tikzpicture} [transform shape,line width=0.3pt, scale=.4] \pgfmathsetmacro {\numnodes }{4} \foreach \x in {1,...,\numnodes }{\pgfmathparse {(\x -1)*720/\numnodes +floor(\x /(\numnodes /2+1))*360/\numnodes } \node [fill,circle,inner sep=0.15cm] (N-\x ) at (\pgfmathresult :5.4cm) [thick] {}; } \foreach \x [count=\xi from 1] in {2,...,\numnodes }{\foreach \y in {\x ,...,\numnodes }{\path [thick] (N-\xi ) edge[-] (N-\y ); } } \end{tikzpicture}$

Die Definition ist ein bisschen salopp, soll an dieser Stelle aber genügen. Der subtile Punkt dabei ist, dass man es einem Graphen nicht unbedingt auf den ersten Blick ansieht, ob er planar ist. Zum Beispiel ist der Graph $K_4$ ein planarer Graph, auch wenn er hier mit einer Kantenüberschneidung gezeichnet ist. Man kann denselben Graphen nämlich auch so zeichnen, dass sich keine zwei Kanten schneiden (zum Beispiel, indem man die vertikale Kante außen um das Quadrat herumführt). Entsprechend ist es auch nicht trivial zu zeigen, dass ein gegebener Graph nicht planar ist; auch wenn es nicht gelingt, den Graph überschneidungsfrei in der Ebene zu zeichnen, könnte es ja sein, dass man eine geschickte Möglichkeit übersehen hat.

Ein berühmter Satz über planare Graphen ist der

Satz 13.16 Vierfarbensatz

In jedem planaren Graphen lassen sich die Ecken mit höchstens $4$ Farben so einfärben, dass je zwei benachbarte Ecken unterschiedliche Farben haben.

Drei Farben reichen im allgemeinen nicht aus, um einen planaren Graphen in dieser Weise einzufärben, wie das Beispiel des Graphen $K_4$ zeigt.

Der Vierfarbensatz lässt sich auch so uminterpretieren, dass man jede Landkarte so einfärben kann, dass je zwei entlang einer Grenze benachbarte Länder unterschiedlich gefärbt werden. Der Satz wurde 1976 von Appel und Haken mit Hilfe von Computern bewiesen. Es ist der erste berühmte mathematische Satz, der mit einem computergestützen Beweis gezeigt wurde. Bis heute ist kein Beweis bekannt, der ohne Computerberechnungen auskommt. Gleichzeitig ist dieses Problem eine Quelle von Beispielen für Fehler und falsche Beweise. Siehe Vierfarbensatz (Wikipedia).

Für die folgende Diskussion definieren wir:

Definition 13.17

Ein Graph heißt zusammenhängend, wenn je zwei Ecken durch einen Weg verbunden sind (und die Eckenmenge nicht leer ist).

Für zusammenhängende planare Graphen gilt die Eulersche Formel, die zurückgeht auf L. Euler (um 1750). Euler hat mit seiner Lösung des Königsberger Brückenproblems sozusagen die Graphentheorie begründet.

$\includegraphics[width=4.9cm]{figures/graph3}$

Um die Euler-Formel anzugeben, beobachten wir, dass ein (in der Ebene ohne Kantenüberschneidungen gezeichneter) planarer Graph durch seine Kanten die Ebene in endlich viele »Gebiete« unterteilt. Das »äußere«, unbegrenzte Gebiet zählen wir dabei mit. Die Form und Lage der Gebiete hängt natürlich davon ab, wie der Graph gezeichnet wird. A priori hängt auch die Anzahl der Gebiete davon ab, die Euler-Formal zeigt allerdings, dass das nicht der Fall ist. Der hier gezeichnete Graph unterteilt die Ebene in $4$ Gebiete.

Satz 13.18 Eulersche Formel für planare Graphen

Sei $G$ ein zusammenhängender planarer Graph, den wir uns in der Ebene gezeichnet vorstellen, sei $E$ die Anzahl seiner Ecken, $K$ die Anzahl der Kanten, und $F$ die Anzahl der Gebiete (»Flächen«), in die $G$ die Ebene unterteilt. Dann gilt

\[ E - K + F = 2. \]

Der Beweis des Satzes ist nicht sehr schwierig. Eine naheliegende Möglichkeit ist es, induktiv vorzugehen. Dazu überlegt man sich, dass man jeden zusammenhängenden planaren Graphen, ausgehend vom Graphen mit einer einzigen Ecke, schrittweise aufbauen kann, indem man entweder eine Kante zwischen zwei Ecken hinzufügt, oder eine Ecke und eine Kante, die die neue Ecke mit einer anderen Ecke verbindet, hinzufügt. Da die Formel für den Graphen mit einem einzigen Punkt gilt, muss man sich dann nur noch überlegen, dass diese beiden Schritte die Gültigkeit der Formel erhalten. Versuchen Sie, die Details einzufüllen! Oder schauen Sie zum Beispiel bei Grieser [ Gr ] nach.

Eng mit dieser Formel verwandt ist die Eulersche Polyederformel , die besagt, dass dieselbe Relation $E-K+F=2$ gilt, wenn $E$ die Anzahl der Ecken, $K$ die Anzahl der Kanten und $F$ die Anzahl der Außenflächen eines konvexen Polyeders in $\mathbb R^3$ ist. Ein Beispiel ist der Würfel mit $8$ Ecken, $12$ Kanten und $6$ Flächen; in der Tat gilt $8-12+6=2$.

Korollar 13.19

Sei $G$ ein zusammenhängender planarer Graph mit $E{\gt}2$ Ecken und $K$ Kanten.

Es gilt $3E-6 \ge K$.
Es gibt eine Ecke, von der weniger als $6$ Kanten abgehen.

Beweis

zu (1). Wir stellen uns $G$ in der Ebene gezeichnet vor und betrachten wie bei der Eulerschen Formel die Gebiete, in die die Ebene durch $G$ zerteilt wird. Sei $F_i$ die Anzahl der Gebiete, die durch $i$ Kanten von $G$ begrenzt werden. (Dabei zählen wir Kanten doppelt, wenn das Gebiet auf beiden Seiten der Kante liegt.

$\includegraphics[width=4.9cm]{figures/graph4}$

Die beiden hellblau gefärbten Gebiete haben jeweils $3$ Begrenzungskanten (also $F_3=2$), das gelbe Gebiet hat $4$ Begrenzungskanten (also $F_4=1$) und das weiße Außengebiet hat $12$ Begrenzungskanten, weil wir die beiden dunkelgrün gezeichneten Kanten jeweils doppelt zählen. Also ist $F_{12}=1$. Für $i\not \in \{ 3, 4, 12\} $ gilt $F_i=0$.

Dann gilt für die Gesamtzahl $F$ der Gebiete:

\[ F = F_3 + F_4 + F_5 + \cdots , \]

denn jedes Gebiet muss von mindestens $3$ Kanten begrenzt werden.

Andererseits ist jede Kante eine »Begrenzungskante« für genau zwei Gebiete, es gilt also auch

\[ 2K = 3F_3 + 4F_4 + 5F5 + \cdots \]

Wenn wir das Dreifache der ersten Gleichung von der zweiten abziehen, dann erhalten wir

\[ K-3F = F_4 + 2F_5 + \cdots \ge 0, \]

folglich unter Ausnutzung der Euler-Formel

\[ 2K \ge 3F = 3 (2+K-E) = 6 + 3K - 3E, \]

also $3E-6 \ge K$, und das wollten wir zeigen.

zu (2). Angenommen, von jeder Ecke würden $6$ oder mehr Kanten abgehen. Dann hätten wir

\[ K \ge 6E/2 = 3E {\gt} 3E-6, \]

also einen Widerspruch zu Teil (1).

Korollar 13.20

Der Graph $K_5$ ist kein planarer Graph.

Beweis

Dies folgt aus Teil (1) des vorherigen Korollars. Der Graph $K_5$ hat $5$ Ecken und $10$ Kanten. Es gilt aber nicht $3\cdot 5 - 6 \ge 10$.

Außerdem können wir den »Sechsfarbensatz« beweisen, eine (wesentlich) abgeschwächte Version des Vierfarbensatzes:

Korollar 13.21 Sechsfarbensatz

Sei $G$ ein planarer Graph. Dann lässt sich jeder Ecke eine von sechs Farben zuordnen, derart dass niemals zwei benachbarte Ecken dieselbe Farbe haben.

Dies ist natürlich eine wesentlich schwächere Aussage als der oben genannte Vierfarbensatz, aber weil der Beweis so einfach ist, soll er hier trotzdem skizziert werden. (Auch der analoge Fünffarbensatz ist wesentlich einfacher zu beweisen als der Vierfarbensatz.)

Beweis

Wir führen Induktion nach Anzahl der Ecken. Für alle Graphen mit $6$ oder weniger Ecken ist die Aussage klar. Für den Induktionsschritt wählen wir eine Ecke, von der höchstens $5$ Ecken abgehen. Eine solche existiert nach Korollar 13.19. Den Graphen $G^\prime $, der aus $G$ entsteht indem wie diese Ecke und alle Kanten, die von ihr ausgehen, entfernen, können wir nach Induktionsvoraussetzung mit höchstens $6$ Farben einfärben, so dass benachbarte Ecken stets unterschiedliche Farben zugewiesen bekommen.

Nun färben wir $G$, indem wir für alle Ecken in $G^\prime $ die Färbung übernehmen. Für die eine verbleibende Ecke können wir auch noch eine gültige Farbe finden, weil ja von dieser Ecke höchstens $5$ Kanten ausgehen, also höchstens $5$ der $6$ Farben ausgeschlossen sind.

Lineare Algebra I, WS 2020/21

Inhalt

13.6 Ausblick: Planare Graphen