Graphique de distance unitaire - Unit distance graph

Le graphe de Petersen est un graphe de distance unitaire : chaque sommet interne subit une rotation à partir de son sommet externe adjacent par rapport au centre du dessin.${\displaystyle 90^{\circ }}$

En mathématiques , et en particulier en théorie des graphes géométriques , un graphe de distance unitaire est un graphe formé à partir d'une collection de points dans le plan euclidien en reliant deux points par une arête chaque fois que la distance entre les deux points est exactement un. Les arêtes des graphiques de distance unitaire se croisent parfois, de sorte qu'elles ne sont pas toujours planes ; un graphique de distance unitaire sans croisement est appelé graphique d'allumettes .

Le problème de Hadwiger-Nelson concerne le nombre chromatique de graphes de distance unitaire. On sait qu'il existe des graphiques de distance unitaire nécessitant cinq couleurs dans n'importe quelle coloration appropriée, et que tous ces graphiques peuvent être colorés avec au plus sept couleurs. Un autre problème ouvert important concernant les graphes de distances unitaires demande combien d'arêtes ils peuvent avoir par rapport à leur nombre de sommets .

Exemples

Le graphe hypercube Q _{4 en} tant que graphe de distance unitaire.

Les graphiques suivants sont des graphiques de distance unitaire :

• Tout graphique de cycle
• Tout graphique en grille
• Tout graphique hypercube
• Tout graphique en étoile
• Tout graphique d'allumettes ou graphique de penny
• Le graphique de Petersen
• Le graphique de Heawood
• Le graphique de la roue W ₇
• Le fuseau Moser , le plus petit graphique de distance unitaire à 4 couleurs

Tout produit cartésien des graphiques de distance unitaire produit un autre graphique de distance unitaire. Cependant, il n'en va pas de même pour les autres produits graphiques couramment utilisés.

Sous-graphiques des graphiques de distance unitaire

Un dessin de distance unitaire du graphe de Möbius-Kantor dans lequel certaines paires non adjacentes sont également à distance unitaire les unes des autres.

Certaines sources définissent un graphe comme étant un graphe de distance unitaire si ses sommets peuvent être mappés à des emplacements distincts dans le plan de telle sorte que les paires adjacentes soient à distance unitaire l'une de l'autre, sans tenir compte de la possibilité que certaines paires non adjacentes soient également à distance unitaire l'une de l'autre. Par exemple, le graphe de Möbius-Kantor a un dessin de ce type.

Selon cette définition plus lâche d'un graphique de distance unitaire, tous les graphiques de Petersen généralisés sont des graphiques de distance unitaire. Afin de distinguer les deux définitions, les graphiques dans lesquels les non-arêtes doivent être distantes d'une distance non unitaire peuvent être appelés graphiques de distance unitaire stricts .

Le graphe formé en supprimant l'un des rayons du graphe de roue W ₇ est un sous-graphe d'un graphe de distance unitaire, mais n'est pas un graphe de distance unitaire strict : il n'y a qu'une seule façon ( à congruence près) de placer les sommets à des emplacements distincts de telle sorte que les sommets adjacents soient séparés d'une unité de distance, et ce placement place également les deux extrémités du rayon manquant à une unité de distance.

Distances des unités de comptage

Le graphe de Hamming (3,3) a 27 sommets et 81 distances unitaires

Paul Erdős  ( 1946 ) a posé le problème de l'estimation du nombre de paires de points d'un ensemble de n points pouvant être à distance unitaire les uns des autres. En termes de théorie des graphes, à quel point un graphe de distance unitaire peut-il être dense ?

Le graphe hypercube fournit une borne inférieure sur le nombre de distances unitaires proportionnelles à En considérant les points d'une grille carrée avec un espacement soigneusement choisi, Erdős a trouvé une borne inférieure améliorée de la forme ${\displaystyle n\log n.}$

${\displaystyle n^{1+c/\log \log n},}$

et offert un prix de 500 $ pour déterminer si oui ou non le nombre maximal de distances unitaires peut également être majoré par une fonction de ce formulaire. La borne supérieure la plus connue pour ce problème, due à Joel Spencer , Endre Szemerédi et William Trotter  ( 1984 ), est proportionnelle à

${\style d'affichage n^{4/3};}$

cette borne peut également être considérée comme comptant les incidences entre les points et les cercles unitaires, et est étroitement liée au théorème de Szemerédi-Trotter sur les incidences entre les points et les lignes.

Représentation des nombres algébriques et théorème de Beckman-Quarles

Pour chaque nombre algébrique A , il est possible de trouver un graphe de distance unitaire G dans lequel une paire de sommets est à distance A dans toutes les représentations de distance unitaire de G . Ce résultat implique une version finie du théorème de Beckman-Quarles : pour deux points quelconques p et q à la distance A , il existe un graphe de distance unitaire rigide fini contenant p et q tel que toute transformation du plan qui préserve les distances unitaires dans ce graph préserve la distance entre p et q . Le théorème complet de Beckman-Quarles stipule que toute transformation du plan euclidien (ou d'un espace de dimension supérieure) qui préserve les distances unitaires doit être une congruence ; c'est-à-dire que pour le graphe de distance unitaire infini dont les sommets sont tous les points du plan, tout automorphisme de graphe doit être une isométrie .

Généralisation aux dimensions supérieures

La définition d'un graphe de distance unitaire peut naturellement être généralisée à tout espace euclidien de dimension supérieure . Tout graphe peut être intégré comme un ensemble de points dans une dimension suffisamment élevée ; Maehara & Rödl (1990) montrent que la dimension nécessaire pour enfoncer un graphe de cette manière peut être bornée par le double de son degré maximum.

La dimension nécessaire pour intégrer un graphique afin que toutes les arêtes aient une distance unitaire, et la dimension nécessaire pour intégrer un graphique afin que les arêtes soient exactement les paires de distance unitaire, peuvent être très différentes les unes des autres : le graphe de la couronne à 2 n sommets peut être intégré dans quatre dimensions de sorte que toutes ses arêtes aient une longueur unitaire, mais nécessite au moins n  − 2 dimensions pour être intégrées de sorte que les arêtes soient les seules paires unité-distance.

Complexité de calcul

Il est NP-difficile , et plus particulièrement complet pour la théorie existentielle des réels , de tester si un graphe donné est un graphe de distance unitaire, ou est un graphe de distance unitaire strict.

Il est également NP-complet pour déterminer si un graphe de distance unitaire a un cycle hamiltonien , même lorsque les sommets du graphe ont tous des coordonnées entières.

Voir également

• Graphe du disque unitaire , un graphe sur le plan qui a une arête chaque fois que deux points sont à une distance d'au plus un

Les références

Remarques

Sources

• Beckman, FS ; Quarles, DA, Jr. (1953), "On isométries des espaces euclidiens", Actes de l'American Mathematical Society , 4 (5) : 810-815, doi : 10.2307/2032415 , JSTOR  2032415 , MR  0058193.
• Erdős, Paul (1946), "On sets of distances of n points", American Mathematical Monthly , 53 (5) : 248–250, doi : 10.2307/2305092 , JSTOR  2305092.
• Erdős, Paul ; Harary, Franck ; Tutte, William T. (1965), "Sur la dimension d'un graphe" (PDF) , Mathematika , 12 : 118–122, doi : 10.1112/S0025579300005222 , hdl : 2027.42/152495 , MR  0188096.
• Erdős, Paul ; Simonovits, Miklós (1980), "Sur le nombre chromatique des graphes géométriques", Ars Combinatoria , 9 : 229-246. Tel que cité par Soifer (2008 , p. 97).
• Gerbracht, Eberhard H.-A. (2009), Eleven unit distance embeddings of the Heawood graph , arXiv : 0912.5395 , Bibcode : 2009arXiv0912.5395G.
• Gervacio, Séverino V. ; Lim, Yvette F.; Maehara, Hiroshi (2008), "Planar unit-distance graphs having planar unit-distance complement", Discrete Mathematics , 308 (10) : 1973–1984, doi : 10.1016/j.disc.2007.04.050.
• Griffiths, Martin (juin 2019), "103.27 A property of a particular unit-distance graph", The Mathematical Gazette , 103 (557): 353-356, doi : 10.1017/mag.2019.74.
• Horvat, Boris ; Pisanski, Tomaž (2010), "Products of unit distance graphs", Discrete Mathematics , 310 (12) : 1783–1792, doi : 10.1016/j.disc.2009.11.035 , MR  2610282.
• Itaï, Alon ; Papadimitriou, Christos H. ; Szwarcfiter, Jayme Luiz (1982), "Hamilton paths in grid graphs", SIAM Journal on Computing , 11 (4) : 676–686, CiteSeerX  10.1.1.383.1078 , doi : 10.1137/0211056 , MR  0677661.
• Kuperberg, Greg (1992), Le chaton Erdos : Au moins 9050 $ de prix ! , Publication dans les groupes usenet rec.puzzles et sci.math, archivé à partir de l'original le 2006-09-29.
• Langin, Katie (18 avril 2018), "Un mathématicien amateur résout un problème de maths vieux de plusieurs décennies" , Science.
• Maehara, Hiroshi (1991), "Distances in a rigid unit-distance graph in the plane", Discrete Applied Mathematics , 31 (2) : 193-200, doi : 10.1016/0166-218X(91)90070-D.
• Maehara, Hiroshi (1992), "Extending a flexible unit-bar framework to a rigid", Mathématiques discrètes , 108 (1–3) : 167–174, doi : 10.1016/0012-365X(92)90671-2 , MR  1189840.
• Maehara, Hiroshi ; Rödl, Vojtech (1990), "Sur la dimension pour représenter un graphe par un graphe de distance unitaire", Graphs and Combinatorics , 6 (4) : 365-367, doi : 10.1007/BF01787703.
• Schaefer, Marcus (2013), "Realizability of graphs and links", in Pach, János (ed.), Thirty Essays on Geometric Graph Theory , Springer, pp. 461-482, CiteSeerX  10.1.1.220.9651 , doi : 10.1007/ 978-1-4614-0110-0_24 , ISBN 978-1-4614-0109-4.
• Soifer, Alexander (2008), Le livre de coloriage mathématique , Springer-Verlag, ISBN 978-0-387-74640-1.
• Spencer, Joël ; Szemerédi, Endre ; Trotter, William T. (1984), " Distances unitaires dans le plan euclidien ", dans Bollobás, Béla (éd.), Graph Theory and Combinatorics , Londres: Academic Press, pp. 293-308, ISBN 978-0-12-111760-3, MR  0777185.
• Tyszka, Apoloniusz (2000), "Versions discrètes du théorème de Beckman-Quarles", Aequationes Mathematicae , 59 (1-2): 124-133, arXiv : math/9904047 , doi : 10.1007/PL00000119 , MR  1741475.
• Sitnik, Arjana ; Horvat, Boris ; Pisanski, Tomaž (2010), Tous les graphiques Petersen généralisés sont des graphiques unit-distance (PDF) , IMFM preprints, 1109.

Liens externes

• Venkatasubramanian, Suresh, "Problème 39 : Distances entre les ensembles de points dans R ² et R ³ ", The Open Problems Project
• Weisstein, Eric W. "Graphique unité-distance" . MathWorld .