Gráfico de intersección de discos unitarios en el plano.
En teoría de grafos geométricos , un gráfico de disco unitario es el gráfico de intersección de una familia de discos unitarios en el plano euclidiano . Es decir, es un gráfico con un vértice para cada disco de la familia, y con una arista entre dos vértices siempre que los vértices correspondientes se encuentren dentro de una unidad de distancia entre sí.
Comúnmente se forman a partir de un proceso de puntos de Poisson , lo que los convierte en un ejemplo simple de estructura aleatoria.
Definiciones
Hay varias definiciones posibles del gráfico de disco unitario, equivalentes entre sí hasta una elección de factor de escala:
Los gráficos de disco unitarios son gráficos formados a partir de una colección de puntos en el plano euclidiano, con un vértice para cada punto y un borde que conecta cada par de puntos cuya distancia está por debajo de un umbral fijo.
Las gráficas de discos unitarios son las gráficas de intersección de círculos de igual radio o de discos de igual radio. Estos gráficos tienen un vértice para cada círculo o disco y un borde que conecta cada par de círculos o discos que tienen una intersección no vacía.
Los gráficos de discos unitarios se pueden formar de una manera diferente a la de una colección de círculos de igual radio, conectando dos círculos con un borde siempre que un círculo contenga el centro del otro círculo.
Propiedades
Cada subgrafo inducido de un gráfico de disco unitario es también un gráfico de disco unitario. Un ejemplo de un gráfico que no es un gráfico de disco unitario es la estrella con un nodo central conectado a seis hojas: si cada uno de los seis discos unitarios toca un disco unitario común, dos de los seis discos deben tocarse entre sí. Por lo tanto, los gráficos de discos unitarios no pueden contener un subgrafo inducido. [1] Se conocen infinitos otros subgrafos inducidos prohibidos. [2]
El número de gráficos de discos unitarios en los vértices etiquetados está dentro de un factor exponencial de . [3] Este rápido crecimiento implica que los gráficos de discos unitarios no tienen ancho gemelo acotado . [4]
Aplicaciones
A partir del trabajo de Huson y Sen (1995), los gráficos de disco unitarios se han utilizado en informática para modelar la topología de redes de comunicación inalámbricas ad hoc . En esta aplicación, los nodos se conectan a través de una conexión inalámbrica directa sin una estación base . Se supone que todos los nodos son homogéneos y están equipados con antenas omnidireccionales . Las ubicaciones de los nodos se modelan como puntos euclidianos y el área dentro de la cual otro nodo puede recibir una señal de un nodo se modela como un círculo. Si todos los nodos tienen transmisores de igual potencia, estos círculos son todos iguales. Los gráficos geométricos aleatorios, formados como gráficos de discos unitarios con centros de discos generados aleatoriamente, también se han utilizado como modelo de percolación y varios otros fenómenos. [5]
Complejidad computacional
Si se le da una colección de discos unitarios (o sus centros) en un espacio de cualquier dimensión fija, es posible construir el gráfico de discos unitarios correspondiente en tiempo lineal , redondeando los centros a puntos enteros cercanos de la cuadrícula , usando una tabla hash. para encontrar todos los pares de centros a una distancia constante entre sí y filtrar la lista resultante de pares para aquellos cuyos círculos se cruzan. La relación entre el número de pares considerados por este algoritmo y el número de aristas en el gráfico final es una constante, lo que da el límite de tiempo lineal. Sin embargo, esta constante crece exponencialmente en función de la dimensión. [6]
Es NP-difícil (más específicamente, completo para la teoría existencial de los reales ) determinar si un gráfico, dado sin geometría, puede representarse como un gráfico de disco unitario. [7] Además, es demostrablemente imposible en tiempo polinómico generar coordenadas explícitas de una representación gráfica de disco unitario: existen gráficos de disco unitarios que requieren exponencialmente muchos bits de precisión en cualquier representación de este tipo. [8]
Sin embargo, muchos problemas de optimización de gráficos importantes y difíciles, como el conjunto máximo independiente , la coloración de gráficos y el conjunto dominante mínimo , se pueden aproximar de manera eficiente utilizando la estructura geométrica de estos gráficos, [9] y el problema de camarilla máxima se puede resolver exactamente para estos gráficos. en tiempo polinómico, dada una representación de disco. [10] Incluso si no se conoce una representación de disco y se proporciona un gráfico abstracto como entrada, es posible en tiempo polinomial producir una camarilla máxima o una prueba de que el gráfico no es un gráfico de disco unitario, [11 ] y a 3: aproximar la coloración óptima mediante el uso de un algoritmo de coloración codicioso . [12]
Ver también
Resiliencia de barrera , un problema algorítmico de ruptura de ciclos en gráficos de discos unitarios
Gráfico de monedas , el gráfico de contacto de discos (no necesariamente de tamaño unitario)
Complejo de Vietoris-Rips , una generalización del gráfico de disco unitario que construye espacios topológicos de orden superior a partir de distancias unitarias en un espacio métrico.
Gráfico de distancia unitaria , un gráfico formado conectando puntos que están a una distancia exactamente uno en lugar de (como aquí) como máximo un umbral determinado.
Notas
^ Dębski, Junosza-Szaniawski y Śleszyńska-Nowak (2020).
^ Atminas y Zamaraev (2018).
^ McDiarmid y Muller (2014).
^ Capo y col. (2022).
^ Véase, por ejemplo, Dall y Christensen (2002).
^ Bentley, Stanat y Williams (1977).
^ Breu y Kirkpatrick (1998); Kang y Muller (2011).
^ McDiarmid y Mueller (2013).
^ Marathe y col. (1994); Matsui (2000).
^ Clark, Colbourn y Johnson (1990).
^ Raghavan y Spinrad (2003).
^ Gräf, Stumpf y Weißenfels (1998).
Referencias
Atminas, Aistis; Zamaraev, Viktor (2018), "Sobre subgrafos inducidos prohibidos para gráficos de discos unitarios", Geometría computacional y discreta , 60 (1): 57–97, arXiv : 1602.08148 , doi : 10.1007/s00454-018-9968-1, MR 3807349 , S2CID 254025741
Bentley, Jon L .; Stanat, Donald F.; Williams, E. Hollins Jr. (1977), "La complejidad de encontrar vecinos cercanos de radio fijo", Cartas de procesamiento de información , 6 (6): 209–212, doi :10.1016/0020-0190(77)90070-9, Señor 0489084.
Bonnet, Édouard; Geniet, Colin; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2022), "Twin-width II: clases pequeñas", Teoría combinatoria , 2 (2): P10:1–P10:42, arXiv : 2006.09877 , doi :10.5070/C62257876, MR 4449818
Gräf, A.; Stumpf, M.; Weißenfels, G. (1998), "Sobre colorear gráficos de discos unitarios", Algorithmica , 20 (3): 277–293, doi :10.1007/PL00009196, MR 1489033, S2CID 36161020.
Huson, Mark L.; Sen, Arunabha (1995), "Algoritmos de programación de transmisiones para redes de radio", Conferencia de Comunicaciones Militares, IEEE MILCOM '95 , vol. 2, págs. 647–651, doi :10.1109/MILCOM.1995.483546, ISBN 0-7803-2489-7, S2CID 62039740.
Kang, Ross J.; Müller, Tobias (2011), "Representaciones de gráficos con esferas y productos escalables", Actas del vigésimo séptimo simposio anual sobre geometría computacional (SoCG'11), 13 al 15 de junio de 2011, París, Francia , págs..
Marathe, Madhav V.; Breu, Heinz; Cazar, III, Harry B.; Ravi, SS; Rosenkrantz, Daniel J. (1994), Heurística basada en geometría para gráficos de discos unitarios , arXiv : math.CO/9409226 , Bibcode : 1994math......9226M.
Matsui, Tomomi (2000), "Algoritmos de aproximación para problemas de conjuntos máximos independientes y problemas de coloración fraccionaria en gráficos de discos unitarios", Geometría discreta y computacional , Lecture Notes in Computer Science, vol. 1763, págs. 194–200, doi :10.1007/978-3-540-46515-7_16, ISBN 978-3-540-67181-7.
McDiarmid, Colin; Mueller, Tobias (2013), "Realizaciones enteras de gráficos de disco y segmentos", Journal of Combinatorial Theory , Serie B, 103 (1): 114–143, arXiv : 1111.2931 , Bibcode : 2011arXiv1111.2931M, doi : 10.1016/j. jctb.2012.09.004
McDiarmid, Colin; Müller, Tobias (2014), "El número de gráficos de disco", European Journal of Combinatorics , 35 : 413–431, doi : 10.1016/j.ejc.2013.06.037 , MR 3090514
Raghavan, Vijay; Spinrad, Jeremy (2003), "Algoritmos robustos para dominios restringidos", Journal of Algorithms , 48 (1): 160–172, doi :10.1016/S0196-6774(03)00048-8, MR 2006100, S2CID 16327087.