Der Vierfarbensatz: Ein moderner Algorithmus für das klassische Farbproblem

Sie haben bestimmt schon vom Vierfarbensatz gehört. Dieses interessante Problem, das ursprünglich aus dem Ausmalen von Ländern auf einer Karte entstand, gilt als eines der drei größten mathematischen Probleme der modernen Welt. Mathematiker brauchten mehr als 100 Jahre, um einen echten Beweis zu erbringen, und auch der verwendete Computerbeweis erreichte das mathematische Stadium. Auch heute noch gibt es im Bereich der Graphentheorie viele interessante Probleme, die sich aus dem Vierfarbensatz ableiten. Beispielsweise ein Problem, das von einem Radiosender stammt: Tragen Sie Zahlen in ein unendlich großes kariertes Papier ein, und der „Abstand“ zwischen denselben Zahlen muss größer sein als die Zahl selbst. Wie viele Zahlen werden dann mindestens benötigt, um die gesamte Ebene abzudecken?

Geschrieben von | Han Ying

Haben Sie als Kind die Weltkarte an der Wand Ihres Arbeitszimmers angestarrt? Als ich die farbenfrohen Muster betrachtete, stellte ich mir vor, dass ich eines Tages um die Welt reisen könnte. Aus einer solchen Sichtweise entstand im Großbritannien des 19. Jahrhunderts ein altes und klassisches mathematisches Problem: das Farbproblem.

Abbildung 1: Weltkarte | Quelle: Standard Map Service System des Ministeriums für natürliche Ressourcen

Ursprung des Vier-Farben-Problems

Die Geschichte beginnt im Jahr 1852, als der britische Kartograf Francis Guthrie beim Betrachten einer Karte die Frage nach dem „Kolorieren einer Karte“ aufwarf. Er entdeckte, dass nur vier Farben nötig waren, um die Karte so einzufärben, dass benachbarte Länder unterschiedliche Farben hatten. Was ihn jedoch verwirrte, war die Frage, ob die Zahl „4“ die beste war. Er wandte sich hilfesuchend an seinen Bruder Frederick Guthrie und seine Freunde. Während der Kommunikation wurde ihnen allmählich klar, dass dieses Problem einen tiefen Zusammenhang mit der Mathematik hat. Frederick wandte sich hilfesuchend an seinen Lehrer, den Mathematiker Augustus De Morgan am University College London. Professor De Morgan versuchte, das Problem zu lösen, konnte es jedoch nicht. Daher schrieb er einen Brief, um das Problem an seinen guten Freund, den irischen Mathematiker Professor William Hamilton, weiterzuleiten. Leider interessierte sich der weise Hamilton nicht sehr für dieses Thema.

Morgan schrieb in dem Brief: „Ein Student bat mich heute, eine Tatsache zu erklären. Wir wissen nicht, ob man sie als Tatsache betrachten kann. Er sagte, dass eine Figur auf einer Ebene beliebig in eine endliche Anzahl von Teilen zerlegt werden kann und jeder Teil so eingefärbt werden kann, dass benachbarte Teile unterschiedliche Farben haben und nur vier Farben verwendet werden können. Was meinen Sie? Wenn dieses Problem wahr ist, kann es die Aufmerksamkeit der Leute erregen?“

Dieses „einfach klingende“ Problem erregte zunächst bei den Mathematikern keine große Aufmerksamkeit. Erst 1878 kündigte der britische Mathematiker Arthur Cayley dieses Problem offiziell bei der London Mathematical Society an und nannte es „Vier-Farben-Problem“, was bei allen den Wunsch weckte, es zu lösen. Damals glaubten die Mathematiker im Allgemeinen, dass das Vier-Farben-Problem nicht allzu schwierig sei und schnell gelöst werden könne. Allerdings verliefen die Dinge anders als erwartet. Von der „Vier-Farben-Vermutung“ bis zum „Vier-Farben-Theorem“ dauerte es mehr als 120 Jahre. Es galt sogar einst zusammen mit dem „Großen Fermatschen Theorem“ und der „Goldbachschen Vermutung“ als eines der drei berühmtesten mathematischen Probleme der Welt.

Abbildung 2: Mathematiker Cayley Quelle: Smithsonian Institution Librarie

Hundertjähriger Beweis des Vierfarbensatzes

Die gängige Beschreibung des Vier-Farben-Problems enthält viele ungültige Informationen, beispielsweise zu Form, Fläche, Längen- und Breitengrad der einzelnen Länder usw. Die einzige wichtige Information ist die Kontiguität (d. h., zwei Regionen haben dieselbe Grenze). Lassen wir diese ungültigen Informationen außer Acht und sehen wir uns an, wie dieses Problem mithilfe der abstrakten Sprache der Graphentheorie streng definiert werden kann.

Gegeben sei ein Graph G = (V, E), wobei die nichtleere Menge V die Knotenmenge und E die Kantenmenge ist. Hier wird tatsächlich das Konzept des dualen Graphen verwendet, d. h. ein Scheitelpunkt ν∈V wird verwendet, um ein Land auf der Karte darzustellen. Eine Kante e12=(ν1, ν2)∈E wird verwendet, um anzuzeigen, dass zwei Knoten (Länder) ν1 und ν2 benachbart sind. Im Folgenden betrachten wir nur einfache ungerichtete Graphen – die Kanten des Graphen sind ungerichtet, d. h. e12=e21; es gibt keine wiederholten Kanten, d. h., es gibt höchstens eine Kante, die die Knoten ν1 und ν2 verbindet; Es gibt keine Selbstschleifen, das heißt, es gibt keine Kanten, die nur einen Scheitelpunkt verbinden.

Das Vierfarbenproblem wird dann in eine Vermutung abstrahiert: Um die Eckpunkte eines einfachen ungerichteten Graphen G=(V, E) so zu färben, dass benachbarte Punkte unterschiedliche Farben haben , sind mindestens vier Farben erforderlich. Die hierfür erforderliche Mindestanzahl an Farben wird als chromatische Zahl bezeichnet.

Zunächst konnte man nur manuell rechnen und kam zu dem Schluss, dass die Vier-Farben-Hypothese für eine Karte mit 96 Ländern gültig sei. Der Wendepunkt der Geschichte ereignete sich im Jahr 1879, als der britische Anwalt Alfred Kempe wichtige Ideen zum Beweis der Vier-Farben-Vermutung lieferte. Kempe schlug vor, dass es in jedem einfachen ungerichteten Graphen G=(V, E) mindestens einen Knoten mit 2, 3, 4 oder 5 benachbarten Knoten gibt (ein Land hat mindestens 2, 3, 4 oder 5 Nachbarn). Dieser Satz ist eigentlich eine Anwendung der Eulerschen Formel. Angenommen, es gibt ν Eckpunkte, e Kanten und f Flächen im Graphen G=(V, E). Zunächst einmal hat jede Fläche mindestens drei Kanten, zwei benachbarte Flächen haben eine gemeinsame Kante und jede Kante hat zwei Eckpunkte, also 2e=3f. Wenn jeder Knoten mindestens 6 Kanten hat, dann ist 2e ≥ 6ν. Aber Eulers Formel sagt uns, dass ν-e+f=2. Dies führt zu einem Widerspruch.

Kempe nannte die oben genannten Eckpunkte mit höchstens 5 Nachbarn und ihre entsprechenden Kanten „unvermeidliche Konfigurationen“. Als nächstes entfernte er diesen Scheitelpunkt und seine angrenzenden Kanten mittels Induktion und erhielt so einen Teilgraphen G'. Wenn dieser Teilgraph G' die Vier-Farben-Vermutung erfüllt, dann heißt der ursprüngliche Graph G' reduzierbar, und die entfernten Eckpunkte und ihre Kanten heißen „reduzierbare Konfigurationen“. Kempe glaubte, dass die Vierfarbenvermutung zwangsläufig gelten würde, solange bewiesen werden könne, dass alle unvermeidlichen Konfigurationen reduzierbare Konfigurationen seien (das heißt, dass sie nach dem Entfernen der entsprechenden Eckpunkte und Kanten vierfarbig sein könnten). Mathematisch ausgedrückt: Wenn ein Graph mit n Knoten die Vier-Farben-Vermutung erfüllt, dann muss es für einen Graphen mit n+1 Knoten einen Knoten und seine Kante geben, die eine unvermeidliche Konfiguration darstellen. Wenn die angrenzenden Punkte dreifarbig sind, malen Sie die entfernten Punkte mit einer vierten Farbe und die Schlussfolgerung bleibt natürlich bestehen. Andernfalls muss das Originalbild neu gezeichnet werden, um diesen Scheitelpunkt freizugeben, sodass die angrenzenden Punkte dreifarbig sein können. Zu diesem Zweck entwickelte Kempe die „Kemp-Ketten“-Methode.

Allerdings stellte man 11 Jahre nach der Veröffentlichung von Kempes Ergebnissen fest, dass diese einen fatalen, nicht behebbaren Fehler enthielten. Dennoch stellte Kempes Idee für spätere Generationen einen wichtigen Durchbruch dar. Die Leute setzten seine Methode fort und bewiesen, dass Karten von 22 Ländern, 39 Ländern und 52 Ländern oder weniger vierfarbig sein können. Erst 1976 gelang den amerikanischen Mathematikern Kenneth Appel und Wolfgang Haken auf zwei Computern der University of Illinois der Beweis des Vier-Farben-Theorems, nachdem sie 1.200 Stunden daran gearbeitet hatten. Sie führten Kempes Methode fort und verbesserten sie, listeten alle 1936 unvermeidlichen Konfigurationen vollständig auf und überprüften ihre Reduzierbarkeit einzeln. Diese Arbeit schockierte die Welt, nicht nur, weil sie ein schwieriges mathematisches Problem bewies, sondern – noch wichtiger – weil sie den Menschen zeigte, dass Computer auch für mathematisch-logische Beweise verwendet werden könnten. An dem Tag, an dem die beiden Mathematiker ihre Forschungsergebnisse veröffentlichten, versah das örtliche Postamt zur Feier des Tages die gesamte Post mit einem Sonderstempel mit der Aufschrift „Vier Farben sind genug“.

Abbildung 3 Viele Jahre lang, nachdem der Beweis des Vier-Farben-Theorems veröffentlicht worden war, stempelte die Fakultät für Mathematik der University of Illinois in Urbana-Champaign ihre ausgehende Post mit dem Poststempel „Vier Farben sind genug“. Bildquelle: las.illinois.edu

Abbildung 4: Die Mathematiker Wolfgang Haken (1928-2022) und Kenneth Appel (1938-2013) 丨 Quelle:
Legacy.com/mathyear2013.blogspot.com

Tatsächlich waren Appel und Haken nicht die ersten, die erkannten, dass zur Lösung der Vier-Farben-Vermutung der Einsatz von Computern notwendig war. Bereits 1950 sagte der deutsche Mathematiker Heinrich Heesch voraus, dass die begrenzte , aber große Zahl unterschiedlicher Konfigurationen der Vier-Farben-Vermutung nur mit Hilfe leistungsstarker Computer getestet werden könne, die in der Lage seien, riesige Datenmengen zu verarbeiten. In einer Zeit, in der die Computertechnologie noch nicht florierte, waren Xixus Ideen sehr fortschrittlich. Er war der erste Mathematiker, der sich für die Lösung des Vier-Farben-Problems mit Computern einsetzte und auch versuchte, diese einzusetzen. Er hat Haken auch großzügig viele seiner Ideen mitgeteilt. Man kann sagen, dass er eine große Rolle bei der Förderung des Beweises der Vier-Farben-Vermutung spielte.

Obwohl die Forschungsergebnisse von Appel und Haken für Aufsehen sorgten, fanden sie damals keine breite Anerkennung. Die Zweifel der Menschen rühren hauptsächlich daher, dass sie nicht erkennen, dass Computer zur Lösung mathematischer Probleme eingesetzt werden können. Skeptiker glauben, dass es sich bei der Methode von Appel und Haken im Wesentlichen um einen erschöpfenden Test handelt. Sie haben einfach Maschinen eingesetzt, um zig Millionen Situationen zu testen. Die Einzelheiten ihrer Beweise sind im Computer verborgen und können nicht durch menschliche Kraft überprüft werden. Die mathematische Gemeinschaft forderte einen reinen und klaren mathematischen Beweis. Dreißig Jahre später lieferte Georges Gonthier, ein junger Mathematiker der Universität Cambridge in England, einen vollständig computergestützten Beweis des Vierfarbensatzes. Anders als bei Appel und Haken wurde jeder Schritt seines logischen Beweises unabhängig von einem Computer ausgeführt. Nach Jahren der Computerrevolution haben die Menschen allmählich die Hilfe von Computern bei mathematischen Arbeiten erkannt und sind endlich bereit zuzugeben, dass der Vier-Farben-Satz gültig ist!

Broadcast-Chromatisches-Zahlen-Problem: eine Verallgemeinerung des Vierfarbenproblems

Während sie die Vier-Farben-Vermutung untersuchten, dachten Mathematiker auch über andere damit zusammenhängende Farbprobleme nach. Beispielsweise das bekannteste Hadwiger-Nelson-Problem: Punkte auf einer unendlich großen Ebene so einzufärben, dass benachbarte Punkte unterschiedliche Farben haben. Was wir heute vorstellen werden, ist eine weitere Variante des Vierfarbenproblems: das Packing-Coloring-Problem, auch Broadcast-Coloring-Problem genannt. Diese Frage wurde erstmals von Wayne Goddard, einem Professor an der Clemson University, und anderen aufgeworfen. Der Ursprung liegt eigentlich in einem ganz praktischen Problem: der Frequenzzuteilung von Radiosendern.

Abbildung 5: Radio | Quelle: Internet

Der Abdeckungsbereich des von jedem Radiosender ausgesendeten Signals ist begrenzt. Je stärker das Signal, desto größer ist sein Abdeckungsbereich. Das Frequenzmodulationsband (FM) des Radios ist sehr schmal. Der UKW-Bereich ziviler Radios in meinem Land liegt zwischen 87,5 und 108 MHz. Es wäre offensichtlich unpraktisch, wenn Radiosender in jeder Provinz und Stadt unseres Landes Signale auf unterschiedlichen Frequenzen aussenden würden. Die Signale zweier Radiosender mit gleicher Frequenz stören sich nur dann nicht, wenn sie weit genug voneinander entfernt sind. Beispielsweise liegen die UKW-Frequenzen von Tianjin Crosstalk Radio, Shenyang Metropolitan Radio und Taizhou Traffic Music Radio alle bei 92,1 MHz; und Peking, das an Tianjin grenzt, weist das 92,1-MHz-Signalband in seiner Radiosenderfrequenztabelle nicht zu, um überlappende Störungen durch dieselben Signale zu vermeiden.

Wie können wir also die Frequenzen der Radiosender in verschiedenen Regionen so zuordnen, dass wir das nationale Rundfunksystem mit der kürzesten Signalbandbreite abdecken und gleichzeitig Störungen vermeiden können? Wie definieren Mathematiker dies in der Sprache der Mathematik?

Ähnlich wie beim Vierfarbensatz verwenden wir bei einem einfachen ungerichteten Graphen G=(V, E) eine ganzzahlige Menge K={1,…,k} zur Darstellung der Farbmenge und verwenden d(u, ν), um die Distanz zwischen zwei Eckpunkten u, ν zu definieren. Betrachten Sie eine Abbildung f:V→{1,…,k}, die erfüllt, dass für zwei beliebige Eckpunkte u, ν∈V und eine beliebige Ganzzahl c∈K gilt: Wenn f(u)=f(ν)=c (d. h., die Eckpunkte u und ν haben dieselbe Farbe), dann ist der Abstand d(u, ν) zwischen u und ν>c (d. h., zwei Eckpunkte mit derselben Farbe sind weit genug voneinander entfernt; unter Berücksichtigung des oben genannten praktischen Hintergrunds bedeutet dies, dass Radiosender mit derselben Signalfrequenz weit genug voneinander entfernt sind). Eine solche Abbildung f stellt ein Packungs-k-Farbschema dar, und die kleinste Ganzzahl, die das Packungs-Farbschema erfüllen kann, wird als Packungs-Farbzahl des Graphen χρ(G) bezeichnet.

Das Problem der Packungsfärbung führt tatsächlich zu stärkeren Einschränkungen für das Problem der Kartenfärbung. Wenn K={1}, ist das Pack-1-Färbungsproblem das primitivste Kartenfärbungsproblem, das erfordert, dass die Farben zweier benachbarter Scheitelpunkte unterschiedlich sind. Schauen wir uns zunächst ein einfaches Beispiel an. Betrachten Sie die eindimensionale Ganzzahlachse in der folgenden Abbildung. Nehmen Sie den Graphen G=Z={0, ±1, ±2,...} als ganzzahlige Menge. Jede Ganzzahl stellt einen Scheitelpunkt dar. Zwei benachbarte Ganzzahlen werden als zwei benachbarte Eckpunkte aufgezeichnet. Der Abstand zwischen zwei ganzen Zahlen wird als der absolute Wert ihrer Differenz definiert. Die Konstruktionszuordnung ist wie folgt:

Abbildung 9: Pluszeichenbereich | Quelle: Referenz [8]

Ihre Kollegen kommentierten: Suvecaseus und Heller lösen nicht nur Probleme, sie optimieren Forschungsideen in der Kombinatorik. Nach vier Monaten unermüdlicher Bemühungen lösten sie schließlich das Problem des Flachpackungsfärbens.

Ende

Der Vierfarbensatz hat der Mathematikergemeinde mehr als ein Jahrhundert lang Rätsel aufgegeben, und bis heute konnte kein wirklich rein mathematischer Beweis dafür gefunden werden. Die Bedeutung des Vierfarbenproblems geht jedoch weit über das Problem selbst hinaus. Noch wichtiger ist jedoch, dass dies im Laufe des Denkens nachfolgender Mathematikergenerationen auch zum Nachdenken über andere Disziplinen geführt hat, wie etwa Graphentheorie, Topologie, Informatik usw. Die Menschen sind bereit, das Vier-Farben-Problem zu untersuchen, nicht um die Karte tatsächlich mit vier Farben zu füllen, sondern um die topologischen Eigenschaften und mathematischen Konnotationen der Zahl „4“ zu erforschen.

Als der erste mathematische Satz mit Hilfe eines Computers bewiesen wurde, erlangte der Vierfarbensatz, der zunächst in Frage gestellt wurde, breite Anerkennung und nahm dadurch eine außergewöhnliche Stellung in der Geschichte der Mathematik ein. Angesichts der rasanten Entwicklung der künstlichen Intelligenz sind KI-gestützte mathematische Beweise heute in den Fokus der meisten Wissenschaftler gerückt. Obwohl manche immer noch glauben, dass die formalen Beweise der KI die ursprüngliche Schönheit der Mathematik zerstören würden, lässt sich nicht leugnen, dass fortschrittliche technische Mittel die Arbeit der Mathematiker tatsächlich erheblich vereinfacht haben. Vielleicht sollten wir nicht die Computer selbst in Frage stellen, sondern die Einstellung und Methoden der Wissenschaftler im Umgang mit Computern.

In „Elementen“ definierte Euklid 300 v. Chr. die Mathematik in einer nahezu perfekten Sprache und präsentierte zukünftigen Generationen eine Reihe intuitiver und strenger Systeme. Im 21. Jahrhundert verwendeten die Menschen präzise Symbole und mechanische Regeln, um Mathematik in Computercode zu übersetzen. Handelt es sich hierbei nicht auch um eine Vererbung und Wiederholung der mathematischen Kultur?

Verweise

[1] Xu Junming. Graphentheorie und ihre Anwendungen. 3. Auflage[M]. Hefei: Universität für Wissenschaft und Technologie des chinesischen Verlags. 2010.

[2]Fritsch R. Der Vier-Farben-Satz[J]. American Mathematical Monthly, 1997, 106(8):785.

[3]Gonthier G. Formaler Beweis – Der Vierfarbensatz[J]. Mitteilungen der Amerikanischen Mathematischen Gesellschaft, 2009(1).

[4] Wang Xianfen, Hu Zuoxuan. Drei Generationen von Beweisen des Vierfarbensatzes. Zeitschrift für Dialektik der Natur. 2010, Nr. 4, S. 42-48, 127, insgesamt 7 Seiten

[5]Goddard, W., Hedetniemi, S., Hedetniemi, S., Harris, J., Rall, D.: Übertragung chromatischer Zahlen von Graphen. Ars Comb. 86 (01 2008)

[6]Bre sar, B., Ferme, J., Klav zar, S., Rall, DF: Eine Übersicht über Verpackungsfarbstoffe. Diskussionen Mathematicae Graph Theory 40(4), 923 (2020)

[7]Subercaseaux, B., Heule, MJH: Die chromatische Packungszahl des unendlichen quadratischen Gitters beträgt mindestens 14. In: Meel, KS, Strichman, O. (Hrsg.) 25. Internationale Konferenz zu Theorie und Anwendung von Erfüllbarkeitstests (SAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Bd. 236, S. 21:1–21:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Deutschland (2022)

[8]Subercaseaux, B., Heule, MJH Die chromatische Packungszahl des unendlichen quadratischen Gitters ist 15. arXiv:2301.09757

Dieser Artikel wird vom Science Popularization China Starry Sky Project unterstützt

Produziert von: Chinesische Vereinigung für Wissenschaft und Technologie, Abteilung für Wissenschaftspopularisierung

Hersteller: China Science and Technology Press Co., Ltd., Beijing Zhongke Xinghe Culture Media Co., Ltd.

Besondere Tipps

1. Gehen Sie zur „Featured Column“ unten im Menü des öffentlichen WeChat-Kontos „Fanpu“, um eine Reihe populärwissenschaftlicher Artikel zu verschiedenen Themen zu lesen.

2. „Fanpu“ bietet die Funktion, Artikel nach Monat zu suchen. Folgen Sie dem offiziellen Account und antworten Sie mit der vierstelligen Jahreszahl + Monat, also etwa „1903“, um den Artikelindex für März 2019 zu erhalten, usw.

Copyright-Erklärung: Einzelpersonen können diesen Artikel gerne weiterleiten, es ist jedoch keinem Medium und keiner Organisation gestattet, ihn ohne Genehmigung nachzudrucken oder Auszüge daraus zu verwenden. Für eine Nachdruckgenehmigung wenden Sie sich bitte an den Backstage-Bereich des öffentlichen WeChat-Kontos „Fanpu“.