Graphe distance-unité

Graphe distance-unité
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.

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[1]. 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[2]. Un autre exemple connu, plus petit mais avec le même nombre chromatique, est le graphe de Moser[3].

Exemples

Dénombrement

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[4] ? En d'autres termes quel est la densité maximal d'un graphe distance-unité d'ordre n ?

L'hypercube fournit une borne inférieure sur le nombre de paires de points proportionnelle à nlogn.

Références

  1. O'Rourke, Joseph, « Problem 57: Chromatic Number of the Plane » sur The Open Problems Project.
  2. Soifer, A. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators New York: Springer, pp. 19-20, 2008.
  3. Moser, L. and Moser, W. "Problem 10." Canad. Math. Bull. 4, 187-189, 1961.
  4. [[Paul Erdős|Erdős, Paul]], « On sets of distances of n points », dans American Mathematical Monthly, vol. 53, 1946, p. 248–250 [lien DOI] 

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe distance-unité de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Graphe de Petersen — Schéma classique du graphe de Petersen, sous la forme d un pentagone et d un pentagramme concentriques, reliés par cinq rayons. Nombre de sommets 10 Nombre d arêtes 15 Distribution des degrés 3 régulier …   Wikipédia en Français

  • Graphe de Moser — Représentation du graphe de Moser. Nombre de sommets 7 Nombre d arêtes 11 Distribution des degrés 3 (6 sommets) 4 (1 sommet) Rayon 2 …   Wikipédia en Français

  • Graphe de Golomb — Nombre de sommets 10 Nombre d arêtes 18 Distribution des degrés 3 (6 sommets) 4 (3 sommets) 6 (1 sommet) Rayon 2 Maille 3 Automorphismes 6 Nombre chromatique 4 …   Wikipédia en Français

  • Graphe mite — Représentation du graphe mite. Nombre de sommets 6 Nombre d arêtes 7 Distribution des degrés 1 (2 sommets) 2 (2 sommets) 3 (1 sommet) 5 (1 sommet) Rayon 1 …   Wikipédia en Français

  • Graphe diamant — Représentation du graphe diamant. Nombre de sommets 4 Nombre d arêtes 5 Distribution des degrés 2 (2 sommets) 3 (2 sommets) Rayon 1 …   Wikipédia en Français

  • Graphe taureau — Représentation du graphe taureau. Nombre de sommets 5 Nombre d arêtes 5 Distribution des degrés 1 (2 sommets) 2 (1 sommet) 3 (2 sommets) Rayon …   Wikipédia en Français

  • Graphe triangle — Représentation du graphe triangle. Notation C3, K3 Nombre de sommets 3 Nombre d arêtes 3 Distribution des degrés 2 ré …   Wikipédia en Français

  • Graphe cerf-volant — Représentation du graphe cerf volant. Nombre de sommets 5 Nombre d arêtes 6 Distribution des degrés 1 (1 sommet) 2 (1 sommet) 3 (3 sommets) Rayon 2 …   Wikipédia en Français

  • Graphe criquet — Représentation du graphe criquet. Nombre de sommets 5 Nombre d arêtes 5 Distribution des degrés 1 (2 sommets) 2 (2 sommets) 4 (1 sommet) Rayon 1 …   Wikipédia en Français

  • Graphe fléchette — Représentation du graphe fléchette. Nombre de sommets 5 Nombre d arêtes 6 Distribution des degrés 1 (1 sommet) 2 (2 sommets) 3 (1 sommet) 4 (1 sommet) Rayon …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”