Graphe distance-unité

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Le graphe de Petersen est un graphe distance-unité : il peut être tracé sur le plan avec des arêtes toutes de longueur 1.
L'hypercube Q4 est un 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'une collection de point 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]

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 à nlogn.

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 couleur qu'il faut pour colorier le plan de façons à ce 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, la meilleure connue à ce jour[3]. Un autre exemple connu, plus petit mais avec le même nombre chromatique, est le graphe de Moser[4].

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]

  1. (en) Paul Erdős, « On sets of distances of n points », Amer. Math. Monthly, vol. 53,‎ 1946, p. 248-250 (lire en ligne)
  2. (en) Joseph O'Rourke, « Problem 57: Chromatic Number of the Plane », sur The Open Problems Project.
  3. (en) A. Soifer (en), The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators, New York, Springer, 2008, p. 19-20
  4. (en) L. Moser et W. Moser, « Problem 10 », dans Canad. Math. Bull., n° 4, 1961, p. 187-189