Coloriage graphique que vous pouvez voir

Introduction

est la tâche informatique consistant à attribuer des couleurs aux éléments d’un graphique afin que les éléments adjacents ne partagent jamais la même couleur. Il a des applications dans plusieurs domaines, notamment programmation sportive, cartographie, navigation sur plan de rue et emploi du temps. Il présente également un intérêt théorique important et constitue un sujet standard dans les cours de niveau universitaire sur la théorie des graphes, les algorithmes et la combinatoire.

Un graphe est une structure mathématique comprenant un ensemble de nœuds dans lequel certaines paires de nœuds sont reliées par bords. Étant donné n’importe quel graphique,

• UN coloration des nœuds est une affectation de couleurs aux nœuds afin que toutes les paires de nœuds reliées par des arêtes aient des couleurs différentes,
• Un coloration des bords est une attribution de couleurs aux arêtes afin que toutes les arêtes qui se rencontrent à un nœud aient des couleurs différentes,
• UN coloration du visage d’un graphe est une attribution de couleurs aux faces de l’un de ses plongements planaires (si un tel plongement existe) de sorte que les faces ayant des limites communes aient des couleurs différentes.

Des exemples de ces concepts sont présentés dans les images ci-dessus. Observez dans le dernier exemple que les colorations des faces nécessitent que les nœuds soient disposés sur le plan de manière à ce qu’aucune arête du graphe ne se coupe. Par conséquent, ils ne sont possibles que pour les graphes planaires. En revanche, les colorations des nœuds et des bords sont possibles pour tous les graphiques. Le but est de trouver des colorations qui utilisent le nombre minimum (optimal) de couleurs, ce qui est un problème NP-difficile en général.

Les articles de ce forum (ici, ici et ici) ont déjà examiné la coloration des graphes, en se concentrant principalement sur les heuristiques constructives pour le problème de coloration des nœuds. Dans cet article, nous examinons les colorations des nœuds, des bords et des faces et cherchons à donner vie au sujet à travers des exemples détaillés et visuellement attrayants. Pour ce faire, nous utilisons le nouveau GColbibliothèque une bibliothèque Python open source construite sur NetworkX. Cette bibliothèque utilise à la fois des algorithmes exacts en temps exponentiel et des heuristiques en temps polynomial.

Le code Python suivant utilise GCol pour construire et visualiser les colorations des nœuds, des bords et des faces du graphique vu ci-dessus. Une liste complète du code utilisé pour générer les images dans cet article est disponible ici. Une version étendue de cet article est également disponible ici.

import networkx as nx
import matplotlib.pyplot as plt
import gcol

G = nx.dodecahedral_graph()

# Generate and display a node coloring
c = gcol.node_coloring(G)
nx.draw_networkx(G, node_color=gcol.get_node_colors(G, c))
plt.show()

# Generate and display an edge coloring
c = gcol.edge_coloring(G)
nx.draw_networkx(G, edge_color=gcol.get_edge_colors(G, c))
plt.show()

# Generate node positions and then 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.show()

Coloration des nœuds

La coloration des nœuds est le problème le plus fondamental de coloration des graphiques. En effet, les problèmes de coloration des bords et des faces peuvent toujours être convertis en instances du problème de coloration des nœuds. Spécifiquement:

• Une coloration des bords d’un graphe peut être obtenue en colorant les nœuds de son graphique linéaire,
• Une coloration de face d’un graphe planaire peut être trouvée en colorant les nœuds de son double graphique.

Les problèmes de coloration des bords et des faces sont donc cas particuliers du problème de coloration des nœuds, concernant respectivement les graphes linéaires et les graphes planaires.

Lors de la visualisation des colorations des nœuds, le placement spatial des nœuds affecte l’interprétabilité. Une bonne disposition des nœuds peut révéler des modèles structurels, des clusters et des symétries, tandis qu’une mauvaise disposition peut les obscurcir. Une option consiste à utiliser des méthodes dirigées par la force, qui modélisent les nœuds comme des éléments mutuellement repoussants et les arêtes comme des ressorts. Le procédé ajuste ensuite les positions des nœuds pour minimiser une fonction énergétique, équilibrant les forces d’attraction des bords et les forces répulsives des nœuds. L’objectif est de créer une disposition esthétique dans laquelle les groupes de nœuds liés sont proches, les nœuds non liés sont séparés et peu d’arêtes se croisent.

Les colorations dans les images ci-dessus démontrent les effets de différents schémas de positionnement des nœuds. Le premier exemple utilise des positions sélectionnées au hasard, ce qui semble donner un diagramme plutôt encombré. Le deuxième exemple utilise une méthode dirigée par force (en particulier, la méthode NetworkX spring_layout() routine), résultant en une disposition plus logique dans laquelle les communautés et la structure sont plus apparentes. GCol permet également de positionner les nœuds en fonction de leurs couleurs. La troisième image positionne les nœuds sur la circonférence d’un cercle, en plaçant les nœuds de la même couleur dans des positions adjacentes ; le second organise les nœuds de chaque couleur en colonnes. Dans ces cas, la structure de la solution est plus apparente et il est plus facile de constater que les nœuds de même couleur ne peuvent pas avoir d’arêtes entre eux.

Les colorations des nœuds sont généralement plus faciles à afficher lorsque le nombre d’arêtes et de couleurs est petit. Parfois, les nœuds ont également un positionnement naturel qui facilite l’interprétation. Des exemples de tels graphiques sont présentés dans les images suivantes. Les trois premiers montrent des exemples de graphes bipartis (graphiques qui n’ont besoin que de deux couleurs) ; le reste montre des graphiques nécessitant trois couleurs.

Coloration des bords

Les colorations des bords nécessitent que toutes les arêtes se terminant à un nœud particulier aient une couleur différente. En conséquence, pour tout graphique $G$ le nombre minimum de couleurs nécessaires est toujours supérieur ou égal à $\Delta(G)$où $\Delta(G)$désigne le maximum degré dans $G$. Pour les graphes bipartis, Théorème de König nous dit que $\Delta(G)$ les couleurs sont toujours suffisantes.
Théorème de Vizing donne un résultat plus général, affirmant que, pour tout graphe $G$pas plus que $\Delta(G)+1$ les couleurs sont toujours nécessaires.

La coloration des bords a des applications dans la construction de ligues sportives, où un ensemble d’équipes doivent s’affronter au cours d’une série de tours. Le premier exemple ci-dessus montre un graphique complet sur six nœuds, un nœud par équipe. Ici, les bords représentent les matchs entre équipes, et chaque couleur donne un seul tour dans le calendrier. Ainsi, le tour « bleu foncé » implique des matchs entre les équipes 0 et 1, 2 et 3, et 4 et 5, par exemple. Les autres images ci-dessus montrent les colorations optimales des bords de deux des graphiques vus précédemment. Ces exemples rappellent les modèles de napperons au crochet ou, peut-être, les capteurs de rêves ojibwés.

Les colorations des bords de deux autres graphiques sont présentées ci-dessous. Ceux-ci aident à illustrer comment, en utilisant la coloration des bords, les parcours autour d’un graphique peuvent être spécifiés par un nœud de départ et une séquence de couleurs qui spécifient l’ordre dans lequel les bords sont ensuite suivis. Cela fournit une autre manière de spécifier des itinéraires entre des emplacements sur des plans de rues.

Coloriage du visage

Le célèbre théorème des quatre couleurs indique que les colorations des faces des intégrations planaires ne nécessitent jamais plus de quatre couleurs. Ce phénomène a été remarqué pour la première fois en 1852 par Francis Guthrie alors qu’il coloriait une carte des comtés d’Angleterre ; cependant, il faudrait plus de 100 ans de recherche pour que cela soit formellement prouvé.

Les images ci-dessus montrent les colorations des visages de trois graphiques. Ici, les nœuds doivent être supposés partout où les bords semblent se rencontrer. Sur cette figure, la face centrale du graphique de Thomassen illustre pourquoi quatre couleurs sont parfois nécessaires. Comme représenté, cette face centrale est adjacente à cinq faces environnantes. Ensemble, ces cinq faces forment un cycle de longueur impaire, nécessitant nécessairement trois couleurs différentes, la face centrale doit donc alors être affectée à une quatrième couleur. Cependant, une cinquième couleur ne sera jamais nécessaire.

Cependant, les colorations du visage nécessitent souvent moins de quatre couleurs. Pour démontrer cela, nous considérons ici un type spécial de graphe appelé graphe eulérien. Il s’agit simplement d’un graphique dans lequel les degrés de tous les nœuds sont pairs. Un graphe planaire est eulérien si et seulement si son graphe dual est biparti ; par conséquent, les faces des graphes planaires eulériens peuvent toujours être colorées en utilisant deux couleurs.

Des exemples sont présentés ci-dessus où, comme requis, tous les nœuds ont un degré pair. Des exemples pratiques de ce théorème peuvent être vus dans les échiquiers, les modèles de spirographe et de nombreuses formes d’art islamique et celtique, qui comportent tous des graphiques sous-jacents à la fois planaires et eulériens. Les motifs de carrelage courants impliquant des carreaux carrés, rectangulaires ou triangulaires sont également caractérisés par de tels graphiques, comme on le voit dans le style de carrelage « en damier » bien connu.

Deux autres modèles de carrelage sont présentés ci-dessous. Le premier utilise des carreaux hexagonaux, dont le corps principal présente un motif répétitif de trois couleurs. Le deuxième exemple montre une coloration optimale d’un motif de carrelage apériodique. Ici, les quatre couleurs sont réparties de manière moins régulière.

Notre dernier exemple vient d’un tristement célèbre article frauduleux extrait d’un numéro de 1975 de Américain scientifique. L’une des fausses affirmations de cet article était qu’on avait découvert un graphe dont les faces nécessitaient au moins cinq couleurs, réfutant ainsi le théorème des quatre couleurs. Ce graphique est présenté ci-dessous, accompagné de quatre colorations.

Conclusions et ressources supplémentaires

L’article a examiné et visualisé plusieurs résultats dans le domaine de la coloration des graphiques, en utilisant la bibliothèque open source Python. GCol. Au début, nous avons noté plusieurs applications pratiques importantes de ce problème, démontrant qu’il est utile. Cet article s’est concentré sur les aspects visuels, démontrant qu’il est également beau.

Le théorème des quatre couleurs est né de l’observation selon laquelle, pour colorer des territoires sur une carte géographique, pas plus de quatre couleurs sont nécessaires. Malgré cela, les cartographes ne souhaitent généralement pas se limiter à quatre couleurs seulement. En effet, il est utile que les cartes satisfassent également à d’autres contraintes, comme garantir que toutes les étendues d’eau (et aucune zone terrestre) soient colorées en bleu, et que les zones disjointes d’un même pays (comme l’Alaska et les États-Unis contigus) reçoivent la même couleur. De telles exigences peuvent être modélisées à l’aide des problèmes de précoloration et de coloration de liste, bien qu’elles puissent très bien augmenter le nombre de couleurs requis au-delà de quatre. La fonctionnalité pour ces problèmes est également incluse dans la bibliothèque GCol.

Tout le code source utilisé pour générer les chiffres peut être trouvé ici. Une version étendue de cet article peut également être trouvée ici. Tous les chiffres ont été générés par l’auteur.