Triangulationen und Triangulationsgraphen von Polygonen

In diesem Abschnitt soll bewiesen werden, dass sich jedes Polygon ${\cal P}$ triangulieren lässt und nur 3 Farben benötigt werden, um den zu ${\cal P}$ gehörenden Triangulationsgraphen einzufärben. Einfärben bedeutet, Knoten des Triangulationsgraphs mit Farben zu beschriften. Die Knoten entsprechen den Eckpunkten des Polygons.

Beide Beweise bauen auf dem so genannten Zwei-Ohren-Theorem (engl.: two-ear-theorem) von G. Meister auf, das zunächst vorgestellt wird. Dazu ist eine Definition des Begriffs Ohr in diesem Zusammenhang notwendig. Ein Polygon ${\cal P}$ hat ein Ohr am Eckpunkt $v$, falls das Dreieck geformt aus $v$ und den benachbarten Eckpunkten vollständig in ${\cal P}$ liegt. Abbildung A.2 verdeutlicht die Definition.

Abbildung A.2: Der Begriff Ohr eines Polygons: (a) Ohr; (b),(c) kein Ohr

Satz 8 (G. Meisters Zwei-Ohren-Theorem)   Jedes Polygon ${\cal P}$ mit mehr als 4 Ecken hat mindestens zwei Ohren [55].

Beweis:Der Beweis ist eine Induktion über die Eckpunkte von ${\cal P}$.

Für den Induktionsanfang $n=4$ gilt die Aussage: Ein Viereck kann immer in zwei Dreiecke als Ohren aufgeteilt werden. Sei nun ${\cal P}$ ein Polygon mit $n$ Ecken und $v_2$ konvexer Eckpunkt. Ein solcher Eckpunkt $v_2$ ist immer vorhanden. Seien $v_1$ und $v_3$ die benachbarten Punkte. Nun sind zwei Fälle zu unterscheiden: Entweder ist $v_1v_2v_3$ ein Ohr oder an $v_2$ gibt es kein Ohr.

Fall 1: $v_1v_2v_3$ ist ein Ohr. Durch das Entfernen des Ohrs entsteht ein neues Polygon mit $n-1$ Eckpunkten. Abbildung A.3 (a) verdeutlicht diesen Fall. Mit der Induktionsvoraussetzung folgt die Behauptung.

Fall 2: An $v_2$ gibt es kein Ohr. Das heißt, es gibt mindestens einen weiteren Eckpunkt des Polygons im Dreieck $v_1v_2v_3$. Nun wird eine Gerade parallel zu $v_1v_3$ verschoben, bis diese den letzten Eckpunkt des Polygons erreicht, der noch innerhalb des Dreiecks $v_1v_2v_3$ liegt. Sei dieser Eckpunkt $x$. Die Strecke $xv_2$ liegt innerhalb des Polygons und teilt es in zwei Teile auf ( ${\cal P}_1$ und ${\cal P}_2$). Abbildung A.3 (b) verdeutlich diesen Sachverhalt.

Auch in diesem Fall besitzt ${\cal P}$ wiederum mindestens zwei Ohren. Es kann vorkommen, dass ${\cal P}_1$ oder ${\cal P}_2$ Dreiecke und somit Ohren sind. Ansonsten folgt per Induktion, dass ${\cal P}_1$ und ${\cal P}_2$ mindestens zwei Ohren haben. Das aus ${\cal P}_1$ und ${\cal P}_2$ zusammengesetzte Polygon ${\cal P}$ hat somit auch mindestens zwei Ohren.

Abbildung A.3: Induktionsbeweis des Zwei-Ohren-Theorems. Die Linie $v_2x$ ist eine innere Diagonale.

$\Box$

Satz 9 (Triangulations-Theorem)   Jedes Polygon ${\cal P}$ kann trianguliert werden [55].

Beweis:Das Zwei-Ohren-Theorem liefert eine Methode, um eine Triangulation von ${\cal P}$ zu finden. Dazu werden Ohren im Polygon gesucht und anschließend entfernt, so dass ein kleineres Polygon entsteht. Die dabei eingefügten Kanten sind die Diagonalen der gesuchten Triangulation.$\Box$

Satz 10   Jeder Triangulationsgraph eines Polygons ${\cal P}$ lässt sich mit 3 Farben einfärben [55].

Beweis:Auch hier liefert das Zwei-Ohren-Theorem die Vorarbeit zum Beweis. Nach dem Entfernen eines Polygonenohres wird der verbleibende Triangulationsgraph des Polygons induktiv mit 3 Farben koloriert. Fügt man die entfernte Ecke wieder hinzu, bekommt sie eine Farbe, die nicht auf der Diagonalen verwendet wurde.$\Box$