Kombinatorische Mathematik

Anwendungen der Graphentheorie

Planare Graphen

Ein Graph G wird als planar bezeichnet, wenn er in einer Ebene so dargestellt werden kann, dass die Eckpunkte alle unterschiedliche Punkte sind, die Kanten einfache Kurven sind und sich nur an ihren Enden zwei Kanten treffen. Zum Beispiel ist K ₄, der vollständige Graph auf vier Eckpunkten, planar, wie 4A zeigt.

Zwei Graphen werden als homöomorph bezeichnet, wenn beide durch Unterteilung von Kanten aus demselben Graphen erhalten werden können. Zum Beispiel sind die Graphen in 4A und 4B homöomorph.

Der K _{m, n-} Graph ist ein Graph, für den die Scheitelpunktmenge in zwei Teilmengen unterteilt werden kann, eine mit m Scheitelpunkten und die andere mit n Scheitelpunkten. Zwei beliebige Scheitelpunkte derselben Teilmenge sind nicht benachbart, während zwei beliebige Scheitelpunkte verschiedener Teilmengen benachbart sind. Der polnische Mathematiker Kazimierz Kuratowski bewies 1930 den folgenden berühmten Satz:

Eine notwendige und ausreichende Bedingung, damit ein Graph G planar ist, besteht darin, dass er keinen zu K ₅ oder K _3,3 homöomorphen Subgraphen enthält, wie in 5 gezeigt.

Eine Elementarkontraktion eines Graphen G ist eine Transformation von G zu einem neuen Graphen G ₁, so dass zwei benachbarte Eckpunkte u und υ von G durch einen neuen Eckpunkt w in G _{1 ersetzt werden} und w in G ₁ allen Eckpunkten zu benachbart ist was entweder u oder υ in G benachbart ist. Ein Graph G * wird als Kontraktion von G bezeichnet, wenn G * durch eine Folge von Elementarkontraktionen aus G erhalten werden kann. Das Folgende ist eine weitere Charakterisierung eines planaren Graphen des deutschen Mathematikers K. Wagner aus dem Jahr 1937.

Ein Graph ist genau dann planar, wenn er nicht mit K ₅ oder K _3,3 kontrahierbar ist.

Das Vierfarben-Kartenproblem

Über ein Jahrhundert lang entging die Lösung des Vierfarbenkartenproblems jedem Analysten, der es versuchte. Das Problem mag die Aufmerksamkeit von Möbius auf sich gezogen haben, aber der erste schriftliche Hinweis darauf scheint ein Brief eines Francis Guthrie an seinen Bruder, einen Schüler von Augustus De Morgan, aus dem Jahr 1852 zu sein.

Das Problem betrifft planare Karten, dh Unterteilungen der Ebene in nicht überlappende Bereiche, die durch einfache geschlossene Kurven begrenzt sind. In geografischen Karten wurde empirisch in so vielen Sonderfällen wie versucht beobachtet, dass höchstens vier Farben benötigt werden, um die Regionen so zu färben, dass zwei Regionen, die eine gemeinsame Grenze haben, immer unterschiedlich gefärbt sind, und in In bestimmten Fällen sind mindestens vier Farben erforderlich. (Regionen, die sich nur zu einem bestimmten Zeitpunkt treffen, wie die Bundesstaaten Colorado und Arizona in den USA, haben keine gemeinsame Grenze.) Eine Formalisierung dieser empirischen Beobachtung bildet das, was als "Vierfarbensatz" bezeichnet wird. Das Problem besteht darin, die Behauptung zu beweisen oder zu widerlegen, dass dies für jede planare Karte der Fall ist. Dass drei Farben nicht ausreichen, lässt sich leicht nachweisen, während der britische Mathematiker PJ Heawood 1890 bewies, dass fünf Farben ausreichen.

1879 schlug der Engländer AB Kempe eine Lösung des Vierfarbenproblems vor. Obwohl Heawood zeigte, dass Kempes Argument fehlerhaft war, erwiesen sich zwei seiner Konzepte in späteren Untersuchungen als fruchtbar. Eine davon, die als Unvermeidbarkeit bezeichnet wird, gibt korrekt an, dass es unmöglich ist, eine Karte zu erstellen, in der jede von vier Konfigurationen fehlt (diese Konfigurationen bestehen aus einer Region mit zwei Nachbarn, einer mit drei, einer mit vier und einer mit fünf). Das zweite Konzept, das der Reduzierbarkeit, hat seinen Namen von Kempes gültigem Beweis, dass wenn es eine Karte gibt, die mindestens fünf Farben erfordert und die eine Region mit vier (oder drei oder zwei) Nachbarn enthält, es eine Karte geben muss, die fünf erfordert Farben für eine kleinere Anzahl von Regionen. Kempes Versuch, die Reduzierbarkeit einer Karte mit einer Region mit fünf Nachbarn zu beweisen, war falsch, wurde jedoch in einem 1976 von Kenneth Appel und Wolfgang Haken aus den USA veröffentlichten Beweis korrigiert. Ihr Beweis stieß auf einige Kritik, da 1.936 verschiedene Fälle mit jeweils bis zu 500.000 logischen Operationen bewertet werden mussten. Appel, Haken und ihre Mitarbeiter entwickelten Programme, die es einem großen digitalen Computer ermöglichten, diese Details zu verarbeiten. Der Computer benötigte mehr als 1.000 Stunden, um die Aufgabe auszuführen, und der resultierende formale Beweis umfasst mehrere hundert Seiten.

Eulersche Zyklen und das Königsberger Brückenproblem

Ein Multigraph G besteht aus einer nicht leeren Menge V (G) von Eckpunkten und einer Teilmenge E (G) der Menge ungeordneter Paare verschiedener Elemente von V (G) mit einer Frequenz f ≥ 1, die an jedes Paar angehängt ist. Wenn das Paar (x ₁, x ₂) mit der Frequenz f zu E (G) gehört, werden die Eckpunkte x ₁ und x ₂ durch f Kanten verbunden.

Ein Euler-Zyklus eines Multigraphen G ist eine geschlossene Kette, in der jede Kante genau einmal vorkommt. Euler zeigte, dass ein Multigraph genau dann einen Eulerschen Zyklus besitzt, wenn er verbunden ist (abgesehen von isolierten Punkten) und die Anzahl der Eckpunkte ungeraden Grades entweder Null oder zwei beträgt.

Dieses Problem trat zuerst auf folgende Weise auf. Der durch den Zusammenfluss seiner beiden Zweige gebildete Fluss Pregel fließt durch die Stadt Königsberg und fließt zu beiden Seiten der Insel Kneiphof. Es gab sieben Brücken, wie in 6A gezeigt. Die Stadtbewohner fragten sich, ob es möglich sei, spazieren zu gehen und jede Brücke nur einmal zu überqueren. Dies ist äquivalent zum Finden eines Euler-Zyklus für den Multigraph in 6B. Euler hat gezeigt, dass dies unmöglich ist, da es vier Eckpunkte ungerader Ordnung gibt.