Einführung
ist die Rechenaufgabe, den Elementen eines Diagramms Farben zuzuweisen, sodass benachbarte Elemente niemals dieselbe Farbe haben. Es gibt Anwendungen in mehreren Bereichen, darunter Sportplanung, Kartografie, Straßenkartennavigation und Stundenplanerstellung. Es ist auch von erheblichem theoretischen Interesse und ein Standardfach in universitären Kursen zu Graphentheorie, Algorithmen und Kombinatorik.
Ein Graph ist eine mathematische Struktur, die aus einer Reihe von besteht Knoten in dem einige Knotenpaare durch verbunden sind Kanten. Gegeben sei ein Graph,
- A Knotenfärbung ist eine Zuweisung von Farben zu Knoten, so dass alle durch Kanten verbundenen Knotenpaare unterschiedliche Farben haben,
- Ein Kantenfärbung ist eine Zuweisung von Farben zu Kanten, sodass alle Kanten, die an einem Knoten zusammentreffen, unterschiedliche Farben haben.
- A Gesichtsfärbung eines Graphen ist eine Zuweisung von Farben zu den Flächen einer seiner planaren Einbettungen (falls eine solche Einbettung existiert), sodass Flächen mit gemeinsamen Grenzen unterschiedliche Farben haben.
Beispiele für diese Konzepte sind in den Bildern oben dargestellt. Beachten Sie im letzten Beispiel, dass Gesichtsfärbungen erfordern, dass Knoten auf der Ebene angeordnet werden, sodass sich keine der Kanten des Diagramms schneiden. Sie sind daher nur für planare Graphen möglich. Im Gegensatz dazu sind Knoten- und Kantenfärbungen für alle Diagramme möglich. Ziel ist es, Färbungen zu finden, die die minimale (optimale) Anzahl an Farben verwenden, was im Allgemeinen ein NP-schweres Drawback darstellt.
Artikel in diesem Discussion board (Hier, Hier Und Hier) haben sich zuvor mit der Graphenfärbung befasst und sich dabei hauptsächlich auf konstruktive Heuristiken für das Knotenfärbungsproblem konzentriert. In diesem Artikel betrachten wir Knoten-, Kanten- und Flächenfarben und versuchen, das Thema durch detaillierte, visuell ansprechende Beispiele zum Leben zu erwecken. Dazu nutzen wir das neu Geschaffene GColBibliothek, eine Open-Supply-Python-Bibliothek, die auf NetworkX aufbaut. Diese Bibliothek nutzt sowohl exakte Exponentialzeitalgorithmen als auch Polynomzeitheuristiken.
Der folgende Python-Code verwendet GCol, um Knoten-, Kanten- und Flächenfarben des oben gezeigten Diagramms zu erstellen und zu visualisieren. Eine vollständige Auflistung des Codes, der zum Generieren der Bilder in diesem Artikel verwendet wurde, ist verfügbar Hier. Eine erweiterte Model dieses Artikels ist ebenfalls verfügbar Hier.
import networkx as nx
import matplotlib.pyplot as plt
import gcol
G = nx.dodecahedral_graph()
# Generate and show a node coloring
c = gcol.node_coloring(G)
nx.draw_networkx(G, node_color=gcol.get_node_colors(G, c))
plt.present()
# Generate and show an edge coloring
c = gcol.edge_coloring(G)
nx.draw_networkx(G, edge_color=gcol.get_edge_colors(G, c))
plt.present()
# Generate node positions after which a face coloring
pos = nx.planar_layout(G)
c = gcol.face_coloring(G, pos)
gcol.draw_face_coloring(c, pos)
nx.draw_networkx(G, pos)
plt.present()Knotenfärbung
Die Knotenfärbung ist das grundlegendste Drawback der Graphenfärbung. Dies liegt daran, dass Kanten- und Flächenfärbungsprobleme immer in Instanzen des Knotenfärbungsproblems umgewandelt werden können. Speziell:
- Eine Kantenfärbung eines Diagramms kann durch Einfärben seiner Knoten erreicht werden Liniendiagramm,
- Eine Flächenfärbung eines planaren Graphen kann durch Einfärben seiner Knoten ermittelt werden Duales Diagramm.
Daher gibt es Probleme mit der Kanten- und Gesichtsfärbung Sonderfälle des Knotenfärbungsproblems in Bezug auf Liniendiagramme bzw. planare Diagramme.
Bei der Visualisierung von Knotenfarben wirkt sich die räumliche Platzierung der Knoten auf die Interpretierbarkeit aus. Gute Knotenlayouts können strukturelle Muster, Cluster und Symmetrien offenbaren, während schlechte Layouts sie verschleiern können. Eine Möglichkeit besteht darin, kraftgerichtete Methoden zu verwenden, die Knoten als sich gegenseitig abstoßende Elemente und Kanten als Federn modellieren. Die Methode passt dann die Knotenpositionen an, um eine Energiefunktion zu minimieren und die anziehenden Kräfte der Kanten und die abstoßenden Kräfte der Knoten auszugleichen. Ziel ist es, ein ästhetisch ansprechendes Format zu schaffen, bei dem Gruppen verwandter Knoten nahe beieinander liegen, nicht verwandte Knoten getrennt sind und sich nur wenige Kanten schneiden.
Die Farben in den Bildern oben veranschaulichen die Auswirkungen verschiedener Knotenpositionierungsschemata. Das erste Beispiel verwendet zufällig ausgewählte Positionen, was ein ziemlich unübersichtliches Diagramm zu ergeben scheint. Das zweite Beispiel verwendet eine erzwungene Methode (insbesondere die von NetworkX). spring_layout() Routine), was zu einem logischeren Format führt, in dem Gemeinschaften und Strukturen deutlicher hervortreten. Mit GColl können Knoten auch anhand ihrer Farben positioniert werden. Das dritte Bild positioniert die Knoten auf dem Umfang eines Kreises und platziert Knoten derselben Farbe an benachbarten Positionen. Der zweite ordnet die Knoten jeder Farbe in Spalten an. In diesen Fällen ist die Struktur der Lösung klarer und es ist einfacher zu erkennen, dass Knoten derselben Farbe keine Kanten zwischen sich haben können.
Knotenfarben lassen sich normalerweise einfacher anzeigen, wenn die Anzahl der Kanten und Farben gering ist. Manchmal haben die Knoten auch eine natürliche Positionierung, die die Interpretation erleichtert. Beispiele für solche Diagramme sind in den folgenden Bildern dargestellt. Die ersten drei zeigen Beispiele für bipartite Graphen (Graphen, die nur zwei Farben benötigen); Der Relaxation zeigt Diagramme, die drei Farben erfordern.
Kantenfärbung
Kantenfärbungen erfordern, dass alle Kanten, die an einem bestimmten Knoten enden, eine andere Farbe haben. Als Ergebnis für jedes Diagramm Die Mindestanzahl der benötigten Farben ist immer größer oder gleich Wo bezeichnet das Most Grad In . Für bipartite Graphen gilt: Satz von König sagt uns das Farben reichen immer aus.
Satz von Vizing liefert ein allgemeineres Ergebnis und besagt, dass dies für jedes Diagramm gilt nicht mehr als Farben werden immer benötigt.
Edge Coloring findet Anwendung beim Aufbau von Sportligen, bei denen eine Reihe von Groups über eine Reihe von Runden gegeneinander antreten müssen. Das erste Beispiel oben zeigt ein vollständiges Diagramm auf sechs Knoten, einem Knoten professional Staff. Hier stellen Kanten Spiele zwischen Groups dar und jede Farbe ergibt eine einzelne Runde im Spielplan. In der „dunkelblauen“ Runde finden additionally beispielsweise Spiele zwischen den Groups 0 und 1, 2 und 3 sowie 4 und 5 statt. Die anderen Bilder oben zeigen optimale Kantenfärbungen von zwei der zuvor gesehenen Diagramme. Diese Beispiele erinnern an Häkeldeckchenmuster oder vielleicht an Ojibwe-Traumfänger.
Unten sind Kantenfärbungen von zwei weiteren Diagrammen dargestellt. Diese helfen zu veranschaulichen, wie mithilfe der Kantenfärbung Durchgänge um einen Graphen durch einen Startknoten und eine Farbfolge angegeben werden können, die die Reihenfolge angeben, in der die Kanten dann verfolgt werden. Dies bietet eine various Möglichkeit, Routen zwischen Standorten in Straßenkarten anzugeben.
Gesichtsfärbung
Der Berühmte Vierfarbensatz besagt, dass für die Gesichtsfärbung planarer Einbettungen nie mehr als vier Farben erforderlich sind. Dieses Phänomen wurde erstmals 1852 von Francis Guthrie bemerkt, als er eine Karte der Grafschaften Englands kolorierte; Es würde jedoch über 100 Jahre Forschung erfordern, um dies offiziell zu beweisen.
Die obigen Bilder zeigen Gesichtsfarben von drei Diagrammen. Hier sollten Knoten überall dort angenommen werden, wo sich Kanten treffen. In dieser Abbildung veranschaulicht die zentrale Fläche des Thomassen-Diagramms, warum manchmal vier Farben benötigt werden. Wie gezeigt, grenzt diese zentrale Fläche an fünf umgebende Flächen. Zusammen bilden diese fünf Flächen einen Zyklus ungerader Länge, der notwendigerweise drei verschiedene Farben erfordert, sodass die mittlere Fläche dann einer vierten Farbe zugeordnet werden muss. Eine fünfte Farbe wird jedoch nie benötigt.
Gesichtsfarben erfordern jedoch oft weniger als vier Farben. Um dies zu demonstrieren, betrachten wir hier einen speziellen Typ von Graphen, der als Euler-Graph bekannt ist. Dies ist einfach ein Diagramm, in dem die Grade aller Knoten gerade sind. Ein planarer Graph ist genau dann Eulersch, wenn sein dualer Graph zweiteilig ist; Folglich können die Flächen von Eulerschen planaren Graphen immer mit zwei Farben gefärbt werden.
Beispiele hierfür sind oben dargestellt, wobei bei Bedarf alle Knoten einen geraden Grad haben. Praktische Beispiele dieses Theorems finden sich in Schachbrettern, Spirograph-Mustern und vielen Formen der islamischen und keltischen Kunst, denen alle sowohl planare als auch Eulersche Graphen zugrunde liegen. Auch gängige Fliesenmuster mit quadratischen, rechteckigen oder dreieckigen Fliesen zeichnen sich durch solche Diagramme aus, wie man sie im bekannten „karierten“ Fliesenstil sieht.
Zwei weitere Kachelmuster sind unten dargestellt. Die erste besteht aus sechseckigen Fliesen, deren Hauptkörper ein sich wiederholendes Muster aus drei Farben aufweist. Das zweite Beispiel zeigt eine optimale Färbung eines kürzlich entdeckten Objekts Aperiodisches Kachelmuster. Hier sind die vier Farben weniger regelmäßig verteilt.
Unser letztes Beispiel stammt von einem berüchtigten Parodieartikel aus einer Ausgabe von 1975 Wissenschaftlicher Amerikaner. Eine der falschen Behauptungen in diesem Artikel struggle, dass ein Graph entdeckt worden sei, dessen Flächen mindestens fünf Farben benötigten, was den Vier-Farben-Satz widerlegte. Diese Grafik ist unten zusammen mit einer vierfarbigen Darstellung dargestellt.
Schlussfolgerungen und weitere Ressourcen
Der Artikel hat mehrere Ergebnisse aus dem Bereich der Graphfärbung unter Verwendung der Open-Supply-Python-Bibliothek überprüft und visualisiert GCol. Zu Beginn haben wir mehrere wichtige praktische Anwendungen dieses Issues erwähnt und gezeigt, dass dies der Fall ist nützlich. Dieser Artikel hat sich auf visuelle Aspekte konzentriert und gezeigt, dass dies auch der Fall ist Schön.
Der Vier-Farben-Satz entstand aus der Beobachtung, dass zum Färben von Gebieten auf einer geografischen Karte nicht mehr als vier Farben erforderlich sind. Dennoch sind Kartographen in der Regel nicht daran interessiert, sich auf nur vier Farben zu beschränken. Tatsächlich ist es für Karten nützlich, auch andere Einschränkungen zu erfüllen, etwa um sicherzustellen, dass alle Gewässer (und keine Landflächen) blau gefärbt sind und dass getrennte Gebiete desselben Landes (wie Alaska und die angrenzenden Vereinigten Staaten) die gleiche Farbe erhalten. Solche Anforderungen können mithilfe der Vorfärbungs- und Listenfärbungsprobleme modelliert werden, obwohl sie durchaus die erforderliche Anzahl von Farben über vier hinaus erhöhen können. Funktionalität für diese Probleme ist auch in der GColl-Bibliothek enthalten.
Der gesamte Quellcode, der zur Generierung der Zahlen verwendet wurde, ist zu finden Hier. Eine erweiterte Model dieses Artikels finden Sie ebenfalls Hier. Alle Zahlen wurden vom Autor erstellt.