Graphe distance-unité
En mathématiques, plus particulièrement en théorie des graphes, un graphe distance-unité est un graphe s'obtenant à partir d'un ensemble de points du plan euclidien en reliant par une arête toutes les paires de points étant à une distance de 1. Les arêtes peuvent se croiser si bien qu'un graphe distance-unité n'est pas nécessairement un graphe planaire. S'il n'y a pas de croisement entre les arêtes, alors le graphe est qualifié de graphe allumette.
Exemples[modifier | modifier le code]
- Tous les cycles et toutes les grilles ;
- N'importe quel hypercube, donc le graphe hexaédrique et le graphe tesseract ;
- Le graphe de Petersen ainsi que celui de Moser, de Harborth et de Golomb ;
- Le graphe roue W7 (c'est le seul graphe roue à être distance-unité) ;
- Le graphe papillon, le graphe longhorn, le graphe diamant, le graphe taureau, le graphe griffe, le graphe criquet, le graphe poisson, le graphe fléchette, le graphe fourche, le graphe cerf-volant, le graphe croix et le graphe mite.
Dénombrement[modifier | modifier le code]
Paul Erdős posa le problème suivant en 1946 : étant donnés n points, comment estimer le nombre maximal de paires de points pouvant être à une distance de 1 sur le plan euclidien[1] ? En d'autres termes quelle est la densité maximale d'un graphe distance-unité d'ordre n ? Ce problème est très lié au théorème de Szemerédi-Trotter.
L'hypercube fournit une borne inférieure sur le nombre de paires de points proportionnelle à n log n.
Application[modifier | modifier le code]
Le problème de Hadwiger-Nelson, introduit en 1944 par Hugo Hadwiger et Edward Nelson, concerne le nombre minimal de couleurs qu'il faut pour colorier le plan de façon que deux points à une distance de 1 ne soient jamais de la même couleur[2]. Il peut être formalisé en théorie des graphes de la façon suivante : quel est le nombre chromatique maximal d'un graphe distance-unité ? Le problème est toujours ouvert mais le graphe de Golomb, avec son nombre chromatique égal à 4, fournit une borne inférieure[3]. Un autre exemple connu, plus petit mais avec le même nombre chromatique, est le graphe de Moser[4]. Cependant, cette borne a été améliorée en 2018 grâce à la découverte d'un graphe distance-unité de nombre chromatique 5.
Généralisation[modifier | modifier le code]
La notion de dimension d'un graphe reprend l'idée d'un graphe tracé avec des arêtes de longueur 1, mais ne se restreint pas au plan.
Références[modifier | modifier le code]
- (en) Paul Erdős, « On sets of distances of n points », Amer. Math. Monthly, vol. 53, , p. 248-250 (lire en ligne)
- (en) Joseph O'Rourke, « Problem 57: Chromatic Number of the Plane », sur The Open Problems Project.
- (en) A. Soifer, The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators, New York, Springer, 2008, p. 19-20.
- (en) L. Moser et W. Moser, « Problem 10 », dans Canad. Math. Bull., no 4, 1961, p. 187-189.
