En matemáticas , y en particular en la teoría de grafos geométricos , un gráfico de distancia unitaria es un gráfico formado a partir de una colección de puntos en el plano euclidiano al conectar dos puntos por un borde siempre que la distancia entre los dos puntos sea exactamente uno. Los bordes de los gráficos de distancia unitaria a veces se cruzan entre sí, por lo que no siempre son planos ; un gráfico de unidad de distancia sin cruces se denomina gráfico de cerilla .
El problema de Hadwiger-Nelson se refiere al número cromático de los gráficos de distancia unitaria. Se sabe que existen gráficos de unidades de distancia que requieren cinco colores en cualquier color adecuado, [2] y que todos estos gráficos se pueden colorear con un máximo de siete colores. Otro problema abierto importante con respecto a las gráficas de distancia unitaria se pregunta cuántas aristas pueden tener en relación con su número de vértices .
Ejemplos de
Los siguientes gráficos son gráficos de unidades de distancia:
- Cualquier gráfico de ciclo
- Cualquier gráfico de cuadrícula
- Cualquier gráfico de hipercubo
- Cualquier gráfico de estrellas
- Cualquier gráfico de fósforo o gráfico de centavo
- El gráfico de Petersen [3]
- El gráfico de Heawood [4]
- El gráfico de la rueda W 7
- El husillo Moser , el gráfico de distancia de 4 unidades cromáticas más pequeño
Cualquier producto cartesiano de las gráficas de distancia unitaria produce otra gráfica de distancia unitaria. Sin embargo, no ocurre lo mismo con otros productos gráficos de uso común. [5]
Subgrafos de los gráficos de unidades de distancia
Algunas fuentes definen un gráfico como un gráfico de unidad de distancia si sus vértices se pueden mapear en distintas ubicaciones en el plano de modo que los pares adyacentes estén separados por unidades de distancia, sin tener en cuenta la posibilidad de que algunos pares no adyacentes también puedan estar separados por unidades de distancia. Por ejemplo, el gráfico de Möbius-Kantor tiene un dibujo de este tipo.
De acuerdo con esta definición más flexible de un gráfico de unidad de distancia, todos los gráficos de Petersen generalizados son gráficos de unidad de distancia. [6] Para distinguir las dos definiciones, los gráficos en los que se requiere que los no bordes estén separados por una distancia no unitaria pueden denominarse gráficos de distancia unitaria estricta . [7]
El gráfico formado al eliminar uno de los radios del gráfico de rueda W 7 es un subgráfico de un gráfico de distancia unitaria, pero no es un gráfico de distancia unitario estricto: solo hay una forma ( hasta la congruencia ) de colocar los vértices en ubicaciones distintas de manera que los vértices adyacentes estén separados por una unidad de distancia, y esta ubicación también coloca los dos extremos del radio faltante a una unidad de distancia. [8]
Contando distancias de unidades
¿Cuántas unidades de distancia se pueden determinar mediante un conjunto de ¿puntos?
Paul Erdős ( 1946 ) planteó el problema de estimar cuántos pares de puntos en un conjunto de n puntos podrían estar a una distancia unitaria entre sí. En términos de la teoría de grafos, ¿qué tan denso puede ser un gráfico de distancia unitaria?
El gráfico de hipercubo proporciona un límite inferior en el número de unidades de distancia proporcional a Al considerar puntos en una cuadrícula cuadrada con un espaciado cuidadosamente elegido, Erdős encontró un límite inferior mejorado de la forma
y ofreció un premio de $ 500 por determinar si el número máximo de distancias unitarias también puede ser delimitado por una función de este formulario. [9] El límite superior más conocido para este problema, debido a Joel Spencer , Endre Szemerédi y William Trotter ( 1984 ), es proporcional a
este límite también puede verse como una cuenta de incidencias entre puntos y círculos unitarios, y está estrechamente relacionado con el teorema de Szemerédi-Trotter sobre las incidencias entre puntos y líneas.
Representación de números algebraicos y el teorema de Beckman-Quarles
Por cada número algebraico A , es posible encontrar una unidad de distancia gráfico G en la que algún par de vértices están a una distancia A en todas las representaciones unidad de distancia de G . [10] Este resultado implica una versión finita del teorema de Beckman-Quarles : para dos puntos p y q cualesquiera a la distancia A , existe una gráfica de distancia unitaria rígida finita que contiene p y q tal que cualquier transformación del plano que conserva la unidad distancias en este gráfico conserva la distancia entre p y q . [11] El teorema completo de Beckman-Quarles establece que cualquier transformación del plano euclidiano (o un espacio de dimensiones superiores) que preserve las distancias unitarias debe ser una congruencia ; es decir, para el gráfico de distancia unitaria infinita cuyos vértices son todos los puntos en el plano, cualquier automorfismo de gráfico debe ser una isometría . [12]
Generalización a dimensiones superiores
La definición de un gráfico de distancia unitaria puede generalizarse naturalmente a cualquier espacio euclidiano de dimensiones superiores . Cualquier gráfico puede integrarse como un conjunto de puntos en una dimensión suficientemente alta; Maehara y Rödl (1990) muestran que la dimensión necesaria para incrustar un gráfico de esta manera puede estar limitada al doble de su grado máximo.
La dimensión necesaria para incrustar un gráfico de modo que todos los bordes tengan una unidad de distancia, y la dimensión necesaria para incrustar un gráfico de modo que los bordes sean exactamente los pares de unidades de distancia, pueden diferir mucho entre sí: el gráfico de corona de 2 n - vértices puede ser incrustado en cuatro dimensiones para que todos sus bordes tengan una longitud unitaria, pero requiere que se incrusten al menos n - 2 dimensiones de modo que los bordes sean los únicos pares unidad-distancia. [13]
Complejidad computacional
Es NP-difícil , y más específicamente completo para la teoría existencial de los reales , probar si un gráfico dado es un gráfico de unidad de distancia o es un gráfico de unidad de distancia estricto. [14]
También es NP-completo determinar si un gráfico de distancia unitaria tiene un ciclo hamiltoniano , incluso cuando los vértices del gráfico tienen coordenadas enteras. [15]
Ver también
- Gráfico de disco unitario , un gráfico en el plano que tiene un borde siempre que dos puntos están a la distancia como máximo uno
Referencias
Notas
- ^ Griffiths (2019) .
- ^ Langin (2018) .
- ^ Erdős, Harary y Tutte (1965) ; Griffiths (2019)
- ^ Gerbracht (2009) .
- ^ Horvat y Pisanski (2010) .
- ^ Žitnik, Horvat y Pisanski (2010) .
- ^ Gervacio, Lim y Maehara (2008) .
- ^ Soifer (2008) , p. 94.
- ^ Kuperberg (1992) .
- ^ Maehara ( 1991 , 1992 ).
- ^ Tyszka (2000) .
- ^ Beckman y Quarles (1953) .
- ^ Erdős y Simonovits (1980) .
- ^ Schaefer (2013) .
- ^ Itai, Papadimitriou y Szwarcfiter (1982) .
Fuentes
- Beckman, FS; Quarles, DA, Jr. (1953), "On isometries of Euclidean spaces", Proceedings of the American Mathematical Society , 4 (5): 810–815, doi : 10.2307 / 2032415 , JSTOR 2032415 , MR 0058193.
- Erdős, Paul (1946), "Sobre conjuntos de distancias de n puntos", American Mathematical Monthly , 53 (5): 248-250, doi : 10.2307 / 2305092 , JSTOR 2305092.
- Erdős, Paul ; Harary, Frank ; Tutte, William T. (1965), "Sobre la dimensión de un gráfico" (PDF) , Mathematika , 12 : 118-122, doi : 10.1112 / S0025579300005222 , hdl : 2027.42 / 152495 , MR 0188096.
- Erdős, Paul ; Simonovits, Miklós (1980), "Sobre el número cromático de gráficos geométricos", Ars Combinatoria , 9 : 229–246. Como lo cita Soifer (2008 , p. 97).
- Gerbracht, Eberhard H.-A. (2009), Incorporaciones de once unidades de distancia del gráfico de Heawood , arXiv : 0912.5395 , Bibcode : 2009arXiv0912.5395G.
- Gervacio, Severino V .; Lim, Yvette F .; Maehara, Hiroshi (2008), "Gráficos planos de unidad-distancia con complemento plano de unidad-distancia", Matemáticas discretas , 308 (10): 1973-1984, doi : 10.1016 / j.disc.2007.04.050.
- Griffiths, Martin (junio de 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), "Productos de gráficos de distancia unitaria", Matemáticas discretas , 310 (12): 1783–1792, doi : 10.1016 / j.disc.2009.11.035 , MR 2610282.
- Itai, Alon; Papadimitriou, Christos H .; Szwarcfiter, Jayme Luiz (1982), "Rutas de Hamilton en gráficos de cuadrícula", SIAM Journal on Computing , 11 (4): 676–686, CiteSeerX 10.1.1.383.1078 , doi : 10.1137 / 0211056 , MR 0677661.
- Kuperberg, Greg (1992), El gatito de Erdos: ¡Al menos $ 9050 en premios! , Publicando en los grupos de usenet rec.puzzles y sci.math, archivado desde el original el 2006-09-29.
- Langin, Katie (18 de abril de 2018), "Matemático aficionado resuelve un problema matemático de hace décadas" , Ciencia.
- Maehara, Hiroshi (1991), "Distancias en un gráfico rígido de unidad-distancia en el plano", Matemáticas aplicadas discretas , 31 (2): 193-200, doi : 10.1016 / 0166-218X (91) 90070-D.
- Maehara, Hiroshi (1992), "Extendiendo un marco flexible de barras unitarias a uno rígido", Discrete Mathematics , 108 (1-3): 167-174, doi : 10.1016 / 0012-365X (92) 90671-2 , MR 1189840.
- Maehara, Hiroshi; Rödl, Vojtech (1990), "Sobre la dimensión para representar un gráfico por un gráfico de distancia unitaria", Gráficos y combinatoria , 6 (4): 365–367, doi : 10.1007 / BF01787703.
- Schaefer, Marcus (2013), "Realizability of graphs and linkages", en Pach, János (ed.), Thirty Essays on Geometric Graph Theory , Springer, págs. 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), El libro de colorear matemático , Springer-Verlag, ISBN 978-0-387-74640-1.
- Spencer, Joel ; Szemerédi, Endre ; Trotter, William T. (1984), "Unidades de distancias en el plano euclidiano", en Bollobás, Béla (ed.), Graph Theory and Combinatorics , Londres: Academic Press, págs. 293-308, ISBN 978-0-12-111760-3, MR 0777185.
- Tyszka, Apoloniusz (2000), "Versiones discretas del teorema de Beckman-Quarles", Aequationes Mathematicae , 59 (1-2): 124-133, arXiv : math / 9904047 , doi : 10.1007 / PL00000119 , MR 1741475.
- Žitnik, Arjana; Horvat, Boris; Pisanski, Tomaž (2010), Todos los gráficos de Petersen generalizados son gráficos de unidad de distancia (PDF) , preimpresiones de IMFM, 1109.
enlaces externos
- Venkatasubramanian, Suresh, "Problema 39: Distancias entre conjuntos de puntos en R 2 y R 3 ", The Open Problems Project
- Weisstein, Eric W. "Gráfico de unidad de distancia" . MathWorld .