Gráfica de distancia unitaria

En matemáticas , particularmente en la teoría de grafos geométricos , un grafo de distancia unitaria es un grafo formado a partir de una colección de puntos en el plano euclidiano conectando dos puntos siempre que la distancia entre ellos sea exactamente uno. Para distinguir estos grafos de una definición más amplia que permite que algunos pares de vértices no adyacentes estén a una distancia de uno, también se los puede llamar grafos de distancia unitaria estrictos o grafos de distancia unitaria fieles . Como familia hereditaria de grafos , se pueden caracterizar por subgrafos inducidos prohibidos . Los grafos de distancia unitaria incluyen los grafos de cactus , los grafos de cerillas y los grafos de centavo , y los grafos de hipercubo . Los grafos de Petersen generalizados son grafos de distancia unitaria no estrictos.

Un problema no resuelto de Paul Erdős pregunta cuántas aristas puede tener un grafo de distancia unitaria sobre vértices. El límite inferior más conocido está ligeramente por encima de la linealidad en —lejos del límite superior , proporcional a . El número de colores necesarios para colorear los grafos de distancia unitaria también es desconocido (el problema de Hadwiger–Nelson ): algunos grafos de distancia unitaria requieren cinco colores, y cada grafo de distancia unitaria puede colorearse con siete colores. Para cada número algebraico hay un grafo de distancia unitaria con dos vértices que deben estar separados por esa distancia. Según el teorema de Beckman–Quarles , las únicas transformaciones planas que preservan todos los grafos de distancia unitaria son las isometrías . ${\estilo de visualización n}$${\estilo de visualización n}$${\displaystyle n^{4/3}}$

Es posible construir un grafo de distancia unitaria de manera eficiente, dados sus puntos. Encontrar todas las distancias unitarias tiene aplicaciones en la comparación de patrones , donde puede ser un primer paso para encontrar copias congruentes de patrones más grandes. Sin embargo, determinar si un grafo dado puede representarse como un grafo de distancia unitaria es NP-hard y, más específicamente, completo para la teoría existencial de los números reales .

El grafo de distancia unitaria para un conjunto de puntos en el plano es el grafo no dirigido que tiene esos puntos como sus vértices , con una arista entre dos vértices siempre que su distancia euclidiana sea exactamente uno. Se dice que un grafo abstracto es un grafo de distancia unitaria si es posible encontrar ubicaciones distintas en el plano para sus vértices, de modo que sus aristas tengan longitud unitaria y de modo que todos los pares de vértices no adyacentes tengan distancias no unitarias. Cuando esto es posible, el grafo abstracto es isomorfo al grafo de distancia unitaria de las ubicaciones elegidas. Alternativamente, algunas fuentes usan una definición más amplia, permitiendo que pares de vértices no adyacentes estén a una distancia unitaria. Los grafos resultantes son los subgrafos de los grafos de distancia unitaria (como se define aquí). ^[2] Cuando la terminología puede ser ambigua, los grafos en los que las no aristas deben estar a una distancia no unitaria pueden llamarse grafos de distancia unitaria estrictos ^[3] o grafos de distancia unitaria fieles . ^[2] Los subgrafos de los grafos de distancia unitaria son equivalentemente los grafos que se pueden dibujar en el plano utilizando solo una longitud de arista. ^[4] Para abreviar, este artículo se refiere a estos como "grafos de distancia unitaria no estrictos".

Los gráficos de distancia unitaria no deben confundirse con los gráficos de disco unitario , que conectan pares de puntos cuando su distancia es menor o igual a uno, y se utilizan con frecuencia para modelar redes de comunicación inalámbrica. ^[5]

El grafo completo sobre dos vértices es un grafo de distancia unitaria, como lo es el grafo completo sobre tres vértices (el grafo triangular ), pero no el grafo completo sobre cuatro vértices. ^[3] Generalizando el grafo triangular, cada grafo de ciclo es un grafo de distancia unitaria, realizado por un polígono regular . ^[4] Dos grafos de distancia unitaria finitos, conectados en un único vértice compartido, producen otro grafo de distancia unitaria, ya que uno puede rotarse con respecto al otro para evitar distancias unitarias adicionales no deseadas. ^[6] Al conectar grafos de esta manera, cada grafo de árbol o cactus finito puede realizarse como un grafo de distancia unitaria. ^[7]

Cualquier producto cartesiano de grafos de distancia unitaria produce otro grafo de distancia unitaria; sin embargo, no sucede lo mismo con otros productos de grafos comunes. Por ejemplo, el producto fuerte de grafos , aplicado a dos grafos cualesquiera no vacíos, produce subgrafos completos con cuatro vértices, que no son grafos de distancia unitaria. Los productos cartesianos de grafos de trayectoria forman grafos de cuadrícula de cualquier dimensión, los productos cartesianos del grafo completo en dos vértices son los grafos de hipercubo , ^[8] y los productos cartesianos de grafos triangulares son los grafos de Hamming . ^[9]${\displaystyle H(d,3)}$

Otros gráficos específicos que son gráficos de distancia unitaria incluyen el gráfico de Petersen , ^[10] el gráfico de Heawood , ^[11] el gráfico de rueda (el único gráfico de rueda que es un gráfico de distancia unitaria), ^[3] y el gráfico de huso de Moser y el gráfico de Golomb (pequeños gráficos de distancia unitaria de 4 cromas ). ^[12] Todos los gráficos de Petersen generalizados , como el gráfico de Möbius-Kantor representado, son gráficos de distancia unitaria no estrictos. ^[13]$Estilo de visualización W7$

Los grafos de cerillas son un caso especial de grafos de distancia unitaria, en los que no se cruzan aristas. Todo grafo de cerillas es un grafo plano ^[14] , pero algunos grafos de distancia unitaria que por lo demás son planos (como el huso de Moser) tienen un cruce en cada representación como grafo de distancia unitaria. Además, en el contexto de los grafos de distancia unitaria, el término "planar" debe usarse con cuidado, ya que algunos autores lo usan para referirse al plano en el que se definen las distancias unitarias, en lugar de a una prohibición de cruces ^[3] . Los grafos de centavo son un caso aún más especial de grafos de distancia unitaria y de cerillas, en los que cada par de vértices no adyacentes están separados por más de una unidad ^{[14] .}

Problema sin resolver en matemáticas :

¿Cuántas distancias unitarias se pueden determinar mediante un conjunto de puntos?${\estilo de visualización n}$

(más problemas sin resolver en matemáticas)

Paul Erdős  (1946) planteó el problema de estimar cuántos pares de puntos en un conjunto de puntos podrían estar a una distancia unitaria entre sí. En términos de teoría de grafos, la pregunta pregunta cuán denso puede ser un grafo de distancia unitaria, y la publicación de Erdős sobre esta cuestión fue uno de los primeros trabajos en teoría de grafos extremales . ^[15] Los grafos de hipercubo y los grafos de Hamming proporcionan un límite inferior en el número de distancias unitarias, 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 para una constante , y ofreció $500 por una prueba de si el número de distancias unitarias también puede ser acotado por encima por una función de esta forma. ^[16] El límite superior más conocido para este problema es Este límite puede verse como el recuento de incidencias entre puntos y círculos unitarios, y está estrechamente relacionado con la desigualdad del número de cruces y con el teorema de Szemerédi-Trotter sobre incidencias entre puntos y líneas. ^[17]${\estilo de visualización n}$${\estilo de visualización n\log n.}$$${\displaystyle n^{1+c/\log \log n}}$$${\estilo de visualización c}$$${\displaystyle {\sqrt[{3}]{\frac {29n^{4}}{4}}}\aproximadamente 1,936n^{4/3}.}$$

Para valores pequeños se conoce el número máximo exacto de aristas posibles. Para estos números de aristas son: ^[18]${\estilo de visualización n}$${\displaystyle n=2,3,4,\puntos}$

Si un grafo dado no es un grafo de distancia unitaria no estricta, tampoco lo es ningún supergrafo de . Una idea similar funciona para los grafos de distancia unitaria estricta, pero utilizando el concepto de un subgrafo inducido , un subgrafo formado a partir de todas las aristas entre los pares de vértices en un subconjunto dado de vértices. Si no es un grafo de distancia unitaria estricta, entonces tampoco lo es ningún otro que tenga como subgrafo inducido. Debido a estas relaciones entre si un subgrafo o su supergrafo es un grafo de distancia unitaria, es posible describir los grafos de distancia unitaria por sus subgrafos prohibidos . Estos son los grafos mínimos que no son grafos de distancia unitaria del tipo dado. Se pueden utilizar para determinar si un grafo dado es un grafo de distancia unitaria, de cualquier tipo. es un grafo de distancia unitaria no estricta, si y solo si no es un supergrafo de un grafo prohibido para los grafos de distancia unitaria no estricta. es un grafo de distancia unitaria estricta, si y solo si no es un supergrafo inducido de un grafo prohibido para los grafos de distancia unitaria estricta. ^[8]${\estilo de visualización G}$${\estilo de visualización H}$${\estilo de visualización G}$${\estilo de visualización G}$${\estilo de visualización H}$${\estilo de visualización G}$${\estilo de visualización G}$${\estilo de visualización G}$${\estilo de visualización G}$${\estilo de visualización G}$${\estilo de visualización G}$

Tanto para los grafos de distancia unitaria estrictos como para los no estrictos, los grafos prohibidos incluyen tanto el grafo completo como el grafo bipartito completo . Para , dondequiera que se coloquen los vértices en el lado de dos vértices de este grafo, hay como máximo dos posiciones a distancia unitaria de ellos para colocar los otros tres vértices, por lo que es imposible colocar los tres vértices en puntos distintos. ^[8] Estos son los únicos dos grafos prohibidos para los grafos de distancia unitaria no estrictos en hasta cinco vértices; hay seis grafos prohibidos en hasta siete vértices ^[6] y 74 en grafos de hasta nueve vértices. Debido a que pegar dos grafos de distancia unitaria (o subgrafos de los mismos) en un vértice produce grafos de distancia unitaria estrictos (respectivamente no estrictos), cada grafo prohibido es un grafo biconexo , uno que no se puede formar mediante este proceso de pegado. ^[19]$Estilo de visualización K_{4}$ $Estilo de visualización K_{2,3}$$Estilo de visualización K_{2,3}$

El gráfico de rueda puede realizarse como un gráfico de distancia unitaria estricta con seis de sus vértices formando un hexágono regular unitario y el séptimo en el centro del hexágono. Quitar una de las aristas del vértice central produce un subgrafo que todavía tiene aristas de longitud unitaria, pero que no es un gráfico de distancia unitaria estricta. La colocación de sus vértices en hexágonos regulares es la única forma ( hasta la congruencia ) de colocar los vértices en ubicaciones distintas de modo que los vértices adyacentes estén separados por una distancia unitaria, y esta colocación también coloca los dos puntos finales de la arista faltante a una distancia unitaria. Por lo tanto, es un gráfico prohibido para los gráficos de distancia unitaria estricta, ^[20] pero no uno de los seis gráficos prohibidos para los gráficos de distancia unitaria no estricta. Otros ejemplos de gráficos que son gráficos de distancia unitaria no estricta pero no gráficos de distancia unitaria estricta incluyen el gráfico formado al quitar una arista exterior de y el gráfico de seis vértices formado a partir de un prisma triangular al quitar una arista de uno de sus triángulos. ^[19]$Estilo de visualización W7$ $Estilo de visualización W7$

Para cada número algebraico , es posible construir un grafo de distancia unitaria en el que algún par de vértices estén a distancia en todas las representaciones de distancia unitaria de . ^[21] Este resultado implica una versión finita del teorema de Beckman-Quarles : para dos puntos cualesquiera y a distancia uno del otro, existe un grafo de distancia unitaria rígido finito que contiene y tal que cualquier transformación del plano que preserve las distancias unitarias en este grafo también preserva la distancia entre y . ^[22] El teorema completo de Beckman-Quarles establece que las únicas transformaciones del plano euclidiano (o un espacio euclidiano de dimensión superior) que preservan las distancias unitarias son las isometrías . De manera equivalente, para el grafo de distancia unitaria infinita generado por todos los puntos en el plano, todos los automorfismos del grafo preservan todas las distancias en el plano, no solo las distancias unitarias. ^[23]${\estilo de visualización \alpha}$${\estilo de visualización G}$${\estilo de visualización \alpha}$${\estilo de visualización G}$${\estilo de visualización p}$${\estilo de visualización q}$${\estilo de visualización \alpha}$${\estilo de visualización p}$${\estilo de visualización q}$${\estilo de visualización p}$${\estilo de visualización q}$

Si es un número algebraico de módulo 1 que no es raíz de la unidad , entonces las combinaciones enteras de potencias de forman un subgrupo finitamente generado del grupo aditivo de números complejos cuyo gráfico de distancia unitaria tiene grado infinito . Por ejemplo, puede elegirse como una de las dos raíces complejas del polinomio , lo que produce un gráfico de distancia unitaria de grado infinito con cuatro generadores. ^[24]${\estilo de visualización \alpha}$${\estilo de visualización \alpha}$${\estilo de visualización \alpha}$${\displaystyle z^{4}-z^{3}-z^{2}-z+1}$

El problema de Hadwiger-Nelson se refiere al número cromático de grafos de distancia unitaria, y más específicamente del grafo de distancia unitaria infinita formado a partir de todos los puntos del plano euclidiano. Por el teorema de de Bruijn-Erdős , que supone el axioma de elección , esto es equivalente a preguntar por el número cromático más grande de un grafo de distancia unitaria finito. Existen grafos de distancia unitaria que requieren cinco colores en cualquier coloración adecuada, ^[25] y todos los grafos de distancia unitaria pueden colorearse con un máximo de siete colores. ^[26]

Respondiendo a otra pregunta de Paul Erdős, es posible que los gráficos de distancia unitaria sin triángulos requieran cuatro colores. ^[27]

El número de gráficos de distancia unitaria estricta en vértices etiquetados es como máximo ^[2], como se expresa utilizando la notación O grande y la notación O pequeña. ${\displaystyle n\geq 4}$ $${\displaystyle {\binom {n(n-1)}{2n}}=O\left(2^{{\bigl (}4+o(1){\bigr )}n\log _{2}n}\right),}$$

La definición de un grafo de distancia unitaria puede generalizarse naturalmente a cualquier espacio euclidiano de dimensiones superiores . En tres dimensiones, los grafos de distancia unitaria de puntos tienen como máximo aristas, donde es una función de crecimiento muy lento relacionada con la función inversa de Ackermann . ^{[28] Este resultado conduce a un límite similar en el número de aristas de} los grafos de vecindad relativa tridimensionales . ^[29] En cuatro o más dimensiones, cualquier grafo bipartito completo es un grafo de distancia unitaria, realizado colocando los puntos en dos círculos perpendiculares con un centro común, por lo que los grafos de distancia unitaria pueden ser grafos densos . ^[7] Las fórmulas de enumeración para grafos de distancia unitaria se generalizan a dimensiones superiores y muestran que en dimensiones de cuatro o más el número de grafos de distancia unitaria estrictos es mucho mayor que el número de subgrafos de grafos de distancia unitaria. ^[2]${\estilo de visualización n}$${\displaystyle n^{3/2}\beta (n)}$${\estilo de visualización \beta}$

Cualquier grafo finito puede ser incrustado como un grafo de distancia unitaria en una dimensión suficientemente alta. Algunos grafos pueden necesitar dimensiones muy diferentes para incrustaciones como grafos de distancia unitaria no estrictos y como grafos de distancia unitaria estrictos. Por ejemplo, el grafo de corona de vértice- ángulo puede ser incrustado en cuatro dimensiones como un grafo de distancia unitaria no estricto (es decir, de modo que todos sus bordes tengan longitud unitaria). Sin embargo, requiere al menos dimensiones para ser incrustado como un grafo de distancia unitaria estricto, de modo que sus bordes sean los únicos pares de distancia unitaria. ^[30] La dimensión necesaria para realizar cualquier grafo dado como un grafo de unidad estricto es como máximo el doble de su grado máximo. ^[31]${\estilo de visualización 2n}$${\estilo de visualización n-2}$

La construcción de un gráfico de distancia unitaria a partir de sus puntos es un paso importante para otros algoritmos que buscan copias congruentes de algún patrón en un conjunto de puntos más grande. Estos algoritmos utilizan esta construcción para buscar posiciones candidatas donde una de las distancias en el patrón está presente, y luego utilizan otros métodos para probar el resto del patrón para cada candidato. ^[32] Se puede aplicar un método de Matoušek (1993) a este problema, ^[32] produciendo un algoritmo para encontrar el gráfico de distancia unitaria de un conjunto de puntos planar en el tiempo donde es la función logarítmica iterada de crecimiento lento . ^[33]${\displaystyle n^{4/3}2^{O(\log ^{*}n)}}$${\displaystyle \log ^{*}}$

Es NP-difícil —y más específicamente, completo para la teoría existencial de los números reales— comprobar si un gráfico dado es un gráfico de distancia unitaria (estricto o no estricto) en el plano. ^[34] También es NP-completo determinar si un gráfico de distancia unitaria planar tiene un ciclo hamiltoniano , incluso cuando todos los vértices del gráfico tienen coordenadas enteras conocidas. ^[35]

• Venkatasubramanian, Suresh, "Problema 39: Distancias entre conjuntos de puntos en R2 y R3", The Open Problems Project
• Weisstein, Eric W. , "Gráfico de distancia unitaria", MathWorld