Gráfico de distancia unitaria

En teoría de grafos, un gráfico de unidad de distancia es un gráfico formado por puntos en el plano euclidiano, con dos vértices conectados por una arista si la distancia entre ellos es exactamente uno. Los bordes del gráfico de distancia unitaria a veces se cruzan, por lo que no siempre son planos . Una gráfica de distancias unitarias sin intersecciones se llama gráfica de coincidencia .

El problema de Nelson-Erdős-Hadwiger se refiere al número cromático de gráficos de unidad de distancia. Se sabe que hay gráficos de unidad de distancia que requieren 5 colores para una coloración adecuada, y que todos esos gráficos se pueden colorear con un máximo de 7 colores. Otro problema abierto importante relacionado con los gráficos de unidades de distancia pregunta cuántas aristas puede tener dicho gráfico en relación con el número de vértices .

Ejemplos

Los siguientes gráficos son gráficos de distancia unitaria:

Subgrafos de grafos de unidad de distancia

Algunos autores definen un gráfico de unidad de distancia como un gráfico que se puede incrustar en un plano de modo que dos vértices adyacentes deben estar a una distancia de uno, pero los vértices que están a una distancia de uno no necesitan ser adyacentes. Por ejemplo , el grafo de Möbius-Cantor tiene una representación gráfica de este tipo.

De acuerdo con esta definición, todos los gráficos de Petersen generalizados son gráficos de unidad de distancia ( Žitnik, Horvat, Pisanski 2010 ). Para distinguir entre estas dos definiciones, los gráficos en los que dos vértices cualesquiera a una distancia de uno están conectados por una arista se denominarán gráficos de distancia unitaria estricta ( Gervacio, Lim, Maehara 2008 ).

El gráfico formado al quitar un radio de la rueda W 7 es un subgráfico de distancia unitaria, pero no un gráfico de distancia unitaria estricto ( Soifer 2008 , p. 94).

Cálculo de distancias unitarias

Problemas sin resolver en Matemáticas : ¿Cuántas unidades de distancia puede haber en un conjunto de n puntos?

Erdős ( Erdős 1946 ) planteó el problema de estimar, en un conjunto de n puntos, el número de pares que se encuentran a una distancia de uno. En términos de teoría de grafos, la cuestión es estimar la densidad del gráfico de distancia unitaria.

El gráfico de hipercubo da un límite inferior en el número de unidades de distancia proporcionales a Al considerar los puntos de una red cuadrada con una distancia cuidadosamente elegida, Erdős encontró un límite inferior mejorado

y ofreció un bono de $500 para averiguar si el número máximo de unidades de distancia se puede expresar mediante una función del mismo tipo ( Kuperberg 1992 ). El límite superior más conocido, según Spencer, Szemerédi y Trotter ( Spencer, Szemerédi, Trotter 1984 ), es proporcional a

.

Este límite se puede considerar como el número de aciertos de puntos en círculos unitarios, y está estrechamente relacionado con el teorema de Szemeredi-Trotter sobre la incidencia de puntos y líneas.

Representación de números algebraicos y el teorema de Beckman-Quorles

Para cualquier número algebraico A , se puede encontrar un gráfico de unidad de distancia G , en el que algunos pares de vértices están a la distancia A en todas las representaciones de unidad de distancia de G ( Maehara 1991 ) ( Maehara 1992 ). Este resultado implica una versión finita del teorema de Beckman-Quorles para cualesquiera dos puntos p y q que estén a la distancia A , existe un gráfico de unidad de distancia rígido finito que contiene p y q tal que cualquier transformación de la plano que conserva distancias unitarias en este gráfico conserva la distancia entre p y q ( Tyszka 2000 ). El teorema completo de Beckman-Quorles establece que cualquier transformación del plano euclidiano (o espacio de mayor dimensión) que preserve la distancia debe ser una congruencia . Por lo tanto, para grafos de unidades de distancia infinita cuyos vértices son el plano completo, cualquier automorfismo de grafos debe ser una isometría ( Beckman, Quarles 1953 ).

Generalización a dimensiones superiores

La definición de un gráfico de unidad de distancia se puede generalizar naturalmente a cualquier dimensión del espacio euclidiano . Cualquier gráfico se puede incrustar como un conjunto de puntos en un espacio de dimensión suficientemente alta. Maehara y Rödl ( Maehara, Rödl 1990 ) han demostrado que la dimensión requerida para incrustar un gráfico puede limitarse al doble de la potencia máxima.

La dimensión requerida para la incrustación de gráficos, en la que todos los bordes tendrán una unidad de longitud, y la dimensión de incrustación, en la que los bordes conectarán exactamente aquellos puntos entre los que la distancia es uno, pueden diferir significativamente. Una corona con 2n vértices se puede incrustar en un espacio de 4 para que todos los bordes tengan dina unitaria, pero se necesita al menos una dimensión n  - 2 para incrustarse de modo que no haya pares de vértices que estén separados por la unidad que no estén conectados por un borde ( Erdös, Simonovits 1980 ).

Complejidad computacional

Es un problema NP-difícil , más precisamente completo para la teoría de la existencia de los números reales , verificar si un gráfico dado es un gráfico de distancia unitaria o un gráfico de distancia unitaria estricta ( Schaefer 2013 ).

Véase también

Notas

Enlaces