Qgelm

Zahlen, bitte! 5 - Wie bunt ist die Ebene?

<html> <a href=„https://www.heise.de/newsticker/meldung/Zahlen-bitte-Wie-bunt-ist-die-Ebene-4024574.html“>zurück zum Artikel</a><figure class=„printversionlogo“><img src=„https://1.f.ix.de/icons/svg/logos/svg/heiseonline.svg“ alt=„heise online“ width=„180“ heigth=„40“/></figure><figure class=„aufmacherbild“><img src=„https://heise.cloudimg.io/width/700/q75.png-lossy-75.webp-lossy-75.foil1/_www-heise-de_/imgs/18/2/4/0/9/0/0/4/fuenf-e90bc2508e5ee263.png“ alt=„fünf“/></figure>Das berühmte Vier-Farben-Problem zum Einfärben von Landkarten ist gelöst, aber eine zweite Vier-Farben-Frage zur „chromatischen Zahl der Ebene“ widersetzt sich seit 1950 einer Antwort. Seit Kurzem weiß man, dass sie mindestens fünf lautet. Viele Fragen in der Mathematik sind so einfach, dass ein Schulkind sie begreifen kann, und trotzdem so kompliziert, dass sich Mathematiker jahrzehntelang die Zähne daran ausbeißen. Eine recht bekannte Frage dieser Art lautet: Wie viele Farben braucht man mindestens, wenn man eine Landkarte so einfärben will, dass Länder mit einer gemeinsamen Grenze verschiedene Farben bekommen?

Als Francis Guthrie im Jahre 1852 eine Karte der Grafschaften von England einfärben wollte, benötigte er dazu vier Farben und fragte sich, ob das eigentlich immer ausreicht. Man kann leicht Beispiele konstruieren, für die drei Farben nicht genügen, aber gibt es irgendeine denkbare Landkarte, die mindestens fünf Farben erfordert? Sein Bruder Frederick trug diese Frage weiter zu dem britischen Mathematiker Augustus De Morgan, von wo aus sie ihren Weg durch die mathematische Fachwelt nahm. Ihre bewegte Geschichte soll hier nicht erzählt werden – erst seit 1976 kennt man jedenfalls die Antwort als Vier-Farben-Satz[2]: Ja, vier Farben genügen immer. <h3 class=„subheading“ id=„nav_graphentheorie_1“>Graphentheorie</h3> Abstrakter formuliert geht es beim Vier-Farben-Problem um das Färben eines Graphen. Ein Graph beschreibt Dinge, Knoten genannt, und Verbindungen zwischen ihnen, die Kanten. Im Falle der Landkarte sind die Knoten die Länder und eine Kante verbindet zwei Länder, wenn diese eine gemeinsame Grenze haben. So betrachtet ist die Welt voller Graphen: In einem Computernetzwerk ist jedes Element ein Knoten und jede Verbindung eine Kante; soziale Netzwerke haben Menschen als Knoten und Freundschaftsbeziehungen als Kanten und so weiter. <figure class=„ a-inline–right“><noscript> <img src=„https://heise.cloudimg.io/width/840/q75.png-lossy-75.webp-lossy-75.foil1/_www-heise-de_/imgs/18/2/4/0/9/0/0/4/GolombGraph-3315817d995425ae.png“ alt=„Golomb-Graph“ class=„akwa-article-teaserimage c1“/> </noscript> <figcaption class=„rteinlinebild_source akwa-caption“>Der Golomb-Graph und eine zulässige Färbung mit vier Farben (Bild:  MathsPoetry / Wikimedia Commons[3] (CC BY-SA 3.0[4]) )</figcaption></figure>Das Färben von Graphen, also die Zuweisung einer Farbe zu jedem Knoten, sodass zwei durch eine Kante verbundene Knoten nicht dieselbe Farbe erhalten, hat massenhaft praktische Anwendungen, wenn man auch den Begriff Farbe als Abstraktion auffasst: Zwei Mobilfunksender (Knoten), die benachbart sind (Kante dazwischen), sollen nicht auf dem gleichen Kanal (Farbe) senden; zwei Leute, die auf Facebook befreundet sind, sollen bei einer Umfrage nicht denselben Fragebogen bekommen; zwei Lehrveranstaltungen eines Dozenten können nicht zum gleichen Zeitpunkt stattfinden. <h3 class=„subheading“ id=„nav_ein_neues2“>Ein neues Vier-Farben-Problem</h3> Im Jahr 1950 – das Vier-Farben-Problem war da noch ungelöst – dachte sich der damals 18-jährige werdende Mathematiker Edward Nelson (später Professor in Princeton; 2014 verstorben): Was wäre, wenn sich eine große Klasse von Färbungsproblemen auf eine „Mutter aller Graphen“ zurückführen ließe, sagen wir mal alle Punkte der Ebene als Knoten, wobei alle Punkte mit Abstand eins durch Kanten verbunden sind? Dieser Gedanke führte in dieser Form nicht weiter, aber er lieferte ein an sich spannendes Problem, von dem Nelson mehreren Leuten erzählte. <div class=„apester-media“ data-context=„true“ data-fallback=„true“ data-tags=„“ data-token=„5a659b370b0e0c0001667550“/> Und so sprach sich die Frage nach der „chromatischen Zahl der Ebene“ herum: Wie viele Farben braucht man mindestens, um jeden Punkt der Ebene so einzufärben, dass je zwei Punkte im Abstand von genau 1 nicht dieselbe Farbe haben? Hier geht es wohlgemerkt nicht um endlich viele zusammenhängende Farbflächen, sondern wirklich jeder Punkt der ganzen Ebene bekommt eine eigene Farbe; das klingt also erst einmal viel komplizierter. Aber schon 1950 wurde klar, dass die chromatische Zahl der Ebene zwischen 4 und 7 liegen muss. Die Argumente für beides – die Untergrenze 4 und die Obergernze 7 – sind auch ohne tiefe Mathe-Kenntnisse nachzuvollziehen. Aufwärmübung: Zwei Farben genügen offensichtlich nicht, denn betrachtet man die Ecken eines beliebigen gleichseitigen Dreiecks mit Kantenlänge 1, dann müssen allein diese drei Punkte schon drei verschiedene Farben haben; da braucht man an die Farben all der anderen Punkte der Ebene erst gar nicht zu denken. <h3 class=„subheading“ id=„nav_mindestens_4_3“>Mindestens 4</h3> <figure class=„ a-inline–right“><noscript> <img src=„https://heise.cloudimg.io/width/1340/q75.png-lossy-75.webp-lossy-75.foil1/_www-heise-de_/imgs/18/2/4/0/9/0/0/4/MoserSpindel-42cb8ea576cb9e49.png“ alt=„Moser-Spindel“ class=„akwa-article-teaserimage c1“/> </noscript> <figcaption class=„rteinlinebild_source akwa-caption“>Die Moser-Spindel lässt sich nicht mit drei Farben einfärben. (Bild:  The Mathematical Coloring Book[5] )</figcaption></figure>Dass drei Farben nicht genügen, sieht man durch Betrachtung der „Moser-Spindel“ (nach den kanadischen Brüdern Leo und William Moser). Die sieben Punkte in der nebenstehenden Abbildung (alle Linien haben Länge 1) lassen sich nicht mit drei Farben, sagen wir rot, grün und blau, einfärben. Wenn beispielsweise A rot ist, dann müssen B und C grün und blau (oder umgekehrt) sein, der zu beiden benachbarte Punkt D dann wiederum rot. Ebenso müssen E und F als Nachbarn von A grün beziehungsweise blau sein, weswegen der zu beiden benachbarte Punkt G wiederum rot sein muss. Das hieße aber, dass die beiden benachbarten Punkte D und G beide rot wären, was nicht sein darf. Der weiter oben gezeigte Golomb-Graph lässt sich übrigens ebenfalls nicht mit drei Farben einfärben. <h3 class=„subheading“ id=„nav_höchstens_7_4“>Höchstens 7</h3> <figure class=„ a-inline–right“><noscript> <img src=„https://heise.cloudimg.io/width/860/q75.png-lossy-75.webp-lossy-75.foil1/_www-heise-de_/imgs/18/2/4/0/9/0/0/4/7farben-3187b00a42ed8962.png“ alt=„7 Farben in der Ebene“ class=„akwa-article-teaserimage c1“/> </noscript> <figcaption class=„rteinlinebild_source akwa-caption“>Eine regelmäßige Parkettierung der Ebene mit 7 Farben</figcaption></figure>Dass sieben Farben genügen, sieht man an einem Beispiel, das Hugo Hadwiger bereits 1945 im Kontext eines anderen Problems veröffentlicht hat. Wenn man die Ebene mit Sechsecken der Kantenlänge 1 parkettiert und diese mit sieben Farben einfärbt, dann haben zwei gleichfarbige Punkte innerhalb eines Sechsecks einen Abstand von höchstens 2. Der Abstand zum nächsten gleichfarbigen Sechseck beträgt (kann man leicht nachrechnen) die Quadratwurzel aus 7, ungefähr 2,65. Zwei Punkte im Abstand von mehr als 2 und weniger als 2,65 können also nicht die gleiche Farbe haben. Verkleinert man also dieses Muster um einen Faktor von beispielsweise 2,3, so ist das Ergebnis eine gemäß dem Problem zulässige Färbung der Ebene mit sieben Farben. <h3 class=„subheading“ id=„nav_geschichte_des5“>Geschichte des Problems</h3> Nachdem das klar war, widersetzte sich das Problem viele Jahre lang hartnäckig einer Lösung. Weil viele es nur vom Hörensagen kannten, wurde es immer wieder verschiedenen Autoren zugeschrieben. Martin Gardner war der erste, der das Problem veröffentlichte, und zwar im Oktober 1960 in seiner Kolumne im Scientific American. In seinem sehr empfehlenswerten Buch The Mathematical Coloring Book[6] widmet Alexander Soifer ein ganzes Kapitel der Spurensuche nach der Quelle des Problems, um es schließlich Nelson zuzuordnen; weil Hadwiger schon zuvor die obige Parkettierung der Ebene betrachtet hatte, heißt es heute Hadwiger-Nelson-Problem. Paul Erdös, der vielleicht produktivste Mathematiker des 20. Jahrhunderts, interessierte sich für die chromatische Zahl der Ebene und erwähnte diese offene Frage in Vorträgen immer wieder, ohne einer Lösung näher zu kommen. Sein Bauchgefühl war aber, dass man mindestens fünf Farben brauchen würde. Das hat sich nun endlich bestätigt. <h3 class=„subheading“ id=„nav_mindestens_56“>Mindestens 5!</h3> In seinem Artikel The chromatic number of the plane is at least 5[7] gibt der Biomediziner und Hobby-Mathematiker Aubrey de Grey Beispiele für Graphen aus Punkten im Abstand 1 an, die sich nicht mit vier Farben färben lassen. Das größere hat 20.425 Knoten, das kleinste ist mit 1581 Knoten immer noch „etwas unhandlich“ und der Nachweis, dass vier Farben nicht genügen, erfordert Computerhilfe. Die Konstruktion selbst ist elementar und ohne tiefe mathematische Kenntnisse nachzuvollziehen. Nach 68 Jahren des Stillstands in dieser Frage weiß man also nun endlich, dass die chromatische Zahl der Ebene mindestens fünf beträgt. Womit sie aber immer noch sechs oder sieben sein könnte. Paul Erdös meinte eher fünf, Alexander Soifer vermutet in seinem oben erwähnten Buch sieben. Wenn es jedenfalls genauso lange bis zur Lösung dauert wie beim ursprünglichen Vier-Farben-Problem, werden wir wohl noch 50 Jahre warten müssen. (Harald Bögeholz) / (bo[8]) <hr/>URL dieses Artikels: <code>http://www.heise.de/-4024574</code> Links in diesem Artikel: <code>[1] http://www.heise.de/thema/Zahlen-bitte!</code> <code>[2] https://de.wikipedia.org/wiki/Vier-Farben-Satz</code> <code>[3] https://commons.wikimedia.org/wiki/File:GolombGraphProperties.svg</code> <code>[4] https://creativecommons.org/licenses/by-sa/3.0/deed.en</code> <code>[5] https://www.heise.de/preisvergleich/124191231?hocid=newsticker&wt_mc=intern.newsticker.textlink-pvg.pvg_124191231</code> <code>[6] https://www.heise.de/preisvergleich/124191231?hocid=newsticker&wt_mc=intern.newsticker.textlink-pvg.pvg_124191231</code> <code>[7] https://arxiv.org/abs/1804.02385</code> <code>[8] mailto:bo@boegeholz.org</code> Copyright © 2018 Heise Medien </html>

Qgelm

Seiten-Werkzeuge

Webseiten-Werkzeuge

Benutzer-Werkzeuge

Zahlen, bitte! 5 - Wie bunt ist die Ebene?