Anwendung des Vierfarbensatzes

8

Ich habe den Vierfarbensatz gelesen und frage mich, ob es eine praktische Anwendung gibt. (Ich denke nicht, dass die Aufteilung der Karte in vier verschiedene Farben als Anwendung angesehen werden kann.)

Ich habe versucht, nach Anwendungen zu googeln, konnte aber keine finden.

graph-theory colorings Computerfreak
quelle

Da bekannt war, dass fünf Farben ausreichen (mit einem einfachen Beweis), lautet die eigentliche Frage: Welche Anwendung profitiert von der Tatsache, dass vier statt fünf Farben ausreichen.

Yuval Filmus

Das Färben von Karten ist wohl keine Anwendung, da der Satz keine getrennten Gebiete zulässt. Zum Beispiel müssen Alaska, Hawaii und die kontinentalen USA alle dieselbe Farbe haben. Die Möglichkeit von getrennten Gebieten bedeutet, dass der einer Karte entsprechende Graph nicht unbedingt planar ist: In der Tat kann jeder Graph mit Kanten realisiert werden, indem Inseln so vorhanden sind, dass die Länder und eine Insel teilen, wenn eine Kante im Graph ist. Ich kann mich nicht erinnern, ob die tatsächliche Weltkarte vierfarbig ist. es ist wahrscheinlich.

m

$m$

m

$m$

i

$i$

j

$j$

i j

$ij$

David Richerby

7

Eine der bemerkenswertesten Anwendungen des 4-Farben-Theorems sind Mobilfunkmasten. Diese Masten decken alle bestimmte Bereiche mit einer gewissen Überlappung ab, was bedeutet, dass sie nicht alle auf derselben Frequenz senden können. Eine einfache Methode, um sicherzustellen, dass keine zwei überlappenden Masten dieselbe Frequenz haben, besteht darin, allen eine unterschiedliche Frequenz zu geben. Da die Regierung jedoch alle Frequenzen besitzt und für jede eine Gebühr erhebt, möchte man die minimal mögliche Anzahl von Frequenzen verwenden. Die abgedeckten Bereiche können als Karte gezeichnet und die verschiedenen Frequenzen als Farben dargestellt werden.

Raaman Nair
quelle

Mit anderen Worten, unter der Annahme, dass vier Farben effizient gefunden werden können, müssen Sie nur vier Frequenzen im Voraus reservieren, selbst wenn die genaue Position der Masten unbekannt ist (oder sich sogar ändern könnte).

Yuval Filmus

1

Ist das wirklich wahr? Es ist nicht garantiert, dass der Graph planar ist (fünf Masten, die nahe genug beieinander liegen, führen zu einem Untergraphen), daher ist nicht garantiert, dass er vierfarbig ist.

K_{5}

$K_5$

David Richerby

@ YuvalFilmus Planare Graphen können in quadratischer Zeit vierfarbig sein: Robertson, Sanders, Seymour und Thomas, "Effizient vierfarbige planare Graphen", Proc. STOC 1996 ( PDF ).

David Richerby

Erlauben Sie mir, zurück zu kommen und eine stärkere Aussage zu machen. Dies ist nicht wahr, gerade weil fünf eng platzierte Masten zu einem . Tatsächlich ist dies eine Anwendung der Tatsache, dass es einen Polynomzeitalgorithmus gibt, um die chromatische Anzahl von Einheitsscheibendiagrammen zu berechnen , die nicht unbedingt planar und nicht unbedingt vierfarbig sind.

K_{5}

$K_5$

David Richerby

3

Probleme beim Färben von Diagrammen sind auf das Planungsproblem weit verbreitet.

Stellen Sie sich eine Universität vor, an der Sie versuchen, Zeiten für alle Abschlussprüfungen festzulegen. Einige Schüler nehmen an mehr als einer Klasse teil, daher sollten Sie sicherstellen, dass nicht zwei Prüfungen gleichzeitig geplant sind. Sie möchten jedoch, dass Ihre Prüfungszeit so kurz wie möglich ist und so viele Prüfungen wie möglich gleichzeitig durchgeführt werden.

Sie können dies als Diagrammfärbungsproblem darstellen: Sie machen wobei jede Klasse ein Scheitelpunkt und eine Kante zwischen Scheitelpunkten ist, wenn zwei Klassen denselben Schüler enthalten. Ihre Farben repräsentieren verschiedene Prüfungszeitfenster. Die Mindestanzahl, mit der Sie dieses Diagramm einfärben können, ist die kleinste Anzahl von Zeitfenstern, die Sie zum Schreiben aller Prüfungen benötigen. $G=(V,E)$

Das Problem im Allgemeinen ist NP schwer, aber wenn Sie etwas Wissen über Ihren Zeitplan hatten, sagen wir, dass er planar war, dann könnten Sie den 4-Farben-Satz anwenden, um alle Prüfungen zusammen zu schreiben.

Ich bin nicht zu 100% sicher, dass Sie jemals ein planares Diagramm in einem realen Planungsproblem erhalten würden, aber hier gibt es eine umfassendere Lektion: Diagramme sind weitgehend auf Dinge anwendbar, die nicht sofort offensichtlich sind. Das 4-Farben-Theorem befasst sich nicht nur mit Grafiken und Karten, sondern kann auch zur Modellierung von Problemen im realen Leben verwendet werden, bei denen Sie eine Reihe von Objekten und einige binäre Beziehungen zwischen diesen Objekten ausdrücken.

jmite
quelle

1

Es ist relativ unwahrscheinlich, dass Sie bei einem Planungsproblem ein planares Diagramm erhalten, da Sie damit, wie Sie sagen, alles mit nur vier Slots lösen können. (In dem von Ihnen angegebenen Beispiel ist die Grafik beispielsweise nicht planar, wenn ein einzelner Schüler fünf Klassen belegt.)

David Richerby

-3

ja planare Grafik Färbung für niedrige / feste hat minimale Anwendungen, hauptsächlich planare Kartenfärbung. jedoch für beliebige -coloring ist NP vollständig , war es eines der 1 ^st Probleme erwiesen NP vollständig, damit Einbindung in das massive Gebäude der Theorie. Tatsächlich kann sogar eine -Färbung durch eine grundlegende Transformation auf eine 3-Färbung reduziert werden. [1] Die Färbung für ist also NP-vollständig (jedoch nicht auf planare Graphen beschränkt) . Es gibt wahrscheinlich andere Ermäßigungen $n$ $n$ $n$ $n$ $n$ $n$ $n \geq 3$ zu 4-farbigen & planaren Karten, die in der Literatur untersucht wurden. Das heißt, um ein besseres Gefühl für seine Bedeutung zu bekommen, müsste man die möglichen Reduzierungen untersuchen, die ein komplexes / fortgeschrittenes / umfassenderes Thema sind.

Ein weiterer Aspekt ist, dass die Frage der 4-Färbung einer planaren Karte / eines Diagramms über viele Jahrzehnte ein schwieriges offenes Problem in der Mathematik / Informatik war (tatsächlich über 1½ Jahre alt und eines der frühesten hochentwickelten Diagrammprobleme). Die Mathematik schreitet voran, indem ungelöste Probleme gelöst werden. es passt in ein gemeinsames Kernmuster von "Problemen, die leicht zu benennen sind, aber die Lösungen / Beweise waren lange Zeit nicht zugänglich und sehr komplex". Dies ist eine in der Mathematik weit verbreitete grundlegende Asymmetrie , die die Grenzen der mathematisch-theoretischen Hebelwirkung aufzeigt .

Die Techniken, die sich als erfolgreich erweisen, können auf andere ungelöste Probleme angewendet werden und manchmal neue theoretische / konzeptuelle Perspektiven / Abstraktionen eröffnen. Manchmal sind bemerkenswerte Beweise für sich genommen wertvoll, und der 4-Farben-Satz passt in diese Kategorie. Es ist einer der ausgefeiltesten frühen automatisierten Theorembeweise. Weitere Arbeiten befassten sich mit verbesserten, für Menschen lesbaren Vereinfachungen, seit sie entdeckt wurden und bei ihrer Ankündigung einen relativen Schock durch die theoretische Gemeinschaft verursachten, und lösten viele weitere Analysen und Kommentare aus. Es dient als wichtiger Benchmark / Meilenstein / Testfall für Verbesserungen bei der automatisierten Theoremprüfung .

[1] 3 Färbung ist NP vollständig

vzn
quelle

1

Es ist wahrscheinlich eine gute Idee, ein anderes Symbol als zu verwenden, um die Anzahl der Farben zu bezeichnen, da häufig die Kardinalität der Scheitelpunktmenge bezeichnet. Wir wissen auch nicht, wie man planare 3-Farben-Graphen in Polynomzeit erstellt.

n

$n$

n

$n$

Juho

Anwendung des Vierfarbensatzes

Antworten: