Warum hat die Weltkarte nur 4 Farben?

Wie viele Farben werden auf einer Weltkarte benötigt, um benachbarte Länder unterschiedlich einzufärben?

Die Antwort lautet: vier Farben.

Dies ist der sehr berühmte Vier-Farben-Satz in der Mathematik. Dieses interessante Problem, das ursprünglich aus der Frage entstand, Länder auf einer Karte einzufärben, gilt als eines der drei größten mathematischen Probleme der Neuzeit auf der 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?

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.

Weltkarte, koloriert nach dem Vier-Farben-Theorem. Bildquelle: Standardkartendienstsystem 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. Also wandte sich Frederick 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.

Mathematiker Cayley, Bildquelle: 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. Tatsächlich wird hier 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. Nehmen wir an, dass es im Graphen G=(V, E) ν Eckpunkte, e Kanten und f Flächen gibt. Zunächst einmal hat jede Fläche mindestens drei Kanten, zwei benachbarte Flächen teilen sich eine 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 bezeichnete die oben genannten Eckpunkte mit höchstens 5 Nachbarn und ihre entsprechenden Kanten als „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 Konfiguration“.

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 aufweisen. 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 die gesamte Post mit einem Sonderstempel mit der Aufschrift „Vier Farben sind genug“.

Viele Jahre nach der Veröffentlichung des Beweises des Vier-Farben-Theorems 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

Die Mathematiker Wolfgang Haken (1928-2022) und Kenneth Appel (1938-2013), Bildquelle: 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 unendlichen 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.

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 um überlappende Störungen durch dieselben Signale zu vermeiden, weist Peking, das an Tianjin grenzt, das 92,1-MHz-Signalband in seiner Frequenztabelle für Radiosender nicht zu.

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, ν>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:

Daher ist d(-2, 2)=4＞3=f(-2)=f(2). Dann ist χρ(Z)=3.

Eindimensionale Packung 3-Färbung, Bildquelle: Referenz [8]

Das obige Beispiel betrachtet nur den eindimensionalen Fall. Was ist, wenn wir das Färbungsproblem der zweidimensionalen ebenen ganzzahligen Menge Z2 betrachten? Es ist denkbar, dass wir eine unendlich große Ebene in Gitter unterteilen (wie ein unendlich großes Schachbrett) und den Abstand zwischen zwei Gittern als den horizontalen Abstand zwischen ihnen plus den vertikalen Abstand definieren können. Wie verpacken und färben wir sie also?

Im Jahr 2008 veröffentlichten Goddard und seine vier Mitarbeiter erstmals ihre Gedanken zu diesem Problem. Sie verwendeten ausschließlich menschliche Berechnungen und kamen zu dem Schluss, dass 9 ≤χρ(Z2)≤ 23. Anschließend verwendeten mehrere Mathematiker computergestützte Beweise, um das Ergebnis schrittweise auf 13 ≤χρ(Z2)≤ 15 zu optimieren.

Im Jahr 2022 optimierten der Doktorand Bernardo Subercaseaux und Professor Marijn JH Heule von der Carnegie Mellon University dieses Ergebnis weiter auf 14 ≤χρ(Z2)≤ 15. Im Januar 2023 gaben sie bekannt, dass sie das Packungsfärbungsproblem der planaren ganzzahligen Menge Z2 vollständig gelöst hätten. In dem Artikel haben sie bewiesen, dass χρ(Z2) = 15 ist, d. h., es werden nur 15 Zahlen von 1 bis 15 benötigt, um das gesamte ebene Gitter auszufüllen, und es ist garantiert, dass der Abstand zwischen zwei Gittern mit derselben Zahl größer als diese Zahl ist. Im Folgenden stellen wir ihre Ideen und Methoden kurz vor.

Offensichtlich ist es weder praktisch noch notwendig, für ein unendliches Gitter die erschöpfende Methode zu verwenden. Daher dachten Mathematiker darüber nach, einen kleinen Teil davon zu überprüfen, indem sie beispielsweise ein 10×10-Gitter nahmen und es dann kopierten und zusammenfügten. Können die Abstandsanforderungen weiterhin eingehalten werden, ist der Nachweis erbracht.

Suvecaseus und Heller waren die ersten, die den Graphen aus dieser Perspektive vereinfachten, sie betrachteten jedoch kein einfaches Rechteck. Stattdessen begannen sie mit einem endlichen Teilgraphen Dr(ν)={u∈Z2/d(u, ν)≤r} ähnlich einer Raute und verwendeten Dr, k zur Darstellung der k-Packungsfärbung des Teilgraphen Dr[(0, 0)] und Dr, k, c zur Darstellung der k-Packungsfärbung des Teilgraphen Dr[(0, 0)] mit dem Mittelpunkt (0, 0), dem die Farbe c zugewiesen wurde. Wenn eine k-Packungsfärbung auf dem Teilgraphen Dr(ν) durchgeführt werden kann, dann ist χρ(Z2)≥k; andernfalls χρ(Z2)≥k+1. Es ist nicht schwer, sich vorzustellen, dass in einem endlichen Graphen wie Dr(ν) kleinere Zahlen häufiger vorkommen; So kann beim Einfärben dem Speicherort größerer Zahlen Vorrang eingeräumt werden. Wenn beispielsweise r≤k, erscheint die Zahl r im Teilgraphen Dr, k, r nur einmal am Mittelpunkt (0, 0), da sonst unsere Anforderung an die Distanz verletzt würde. Dies ist auch der Vorteil von Dr(ν) gegenüber rechteckigen Teilgraphen. Dr(ν) ist eigentlich ein regelmäßiges Viereck mit guter Symmetrie, daher haben Suecaseus und Heller Dr(ν) in acht gleiche Teile aufgeteilt (siehe Abbildung 7). Beim Ausmalen ordneten sie die größeren Zahlen im 1/8-Winkelbereich der Reihe nach an und vermieden so eine wiederholte Überprüfung des Ausmalschemas. D3, 7, 3 in Abbildung 8 ist ein sehr intuitives Beispiel.

Teilen Sie Dr(ν) in acht gleiche Teile. Bildquelle: Referenz [8]

D3, 7, 3 Färbung, Bildquelle: Referenz [8]

Die zweite Vereinfachung durch Suecaseus und Heller bestand darin, den Gitterpunkt nicht mehr einfach als Farbeinheit zu betrachten. Sie wählten fünf benachbarte Gitterpunkte in Dr(ν) aus, um einen plusförmigen Bereich zu bilden, und verwendeten diesen plusförmigen Bereich als Einheit zum Färben. Mit anderen Worten, wir können nur in Betracht ziehen, eine bestimmte Zahl in diesen plusförmigen Bereich einzufügen, überlegen aber vorerst nicht, an welchem ​​konkreten Gitterpunkt in diesem plusförmigen Bereich sie platziert werden soll. Nachdem Sie das Farbschema für die plusförmigen Bereiche angeordnet haben, färben Sie jeden Gitterpunkt ein.

Pluszeichenbereich, Bildquelle: 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 beträgt 15. arXiv:2301.09757

Planung und Produktion

Quelle: Fanpu

Autor: Han Ying

Dieser Artikel ist eine vom Science Popularization China Starry Sky Project unterstützte Arbeit

Produziert von: Abteilung für Wissenschaftspopularisierung der Chinesischen Vereinigung für Wissenschaft und Technologie

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

Herausgeber: Yinuo