En la teoría de grafos geométricos , un grafo 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 un borde entre dos vértices siempre que los vértices correspondientes se encuentren dentro de una unidad de distancia entre sí.
Por lo general, se forman a partir de un proceso de puntos de Poisson , lo que los convierte en un ejemplo simple de una estructura aleatoria.
Definiciones
Hay varias definiciones posibles del gráfico de disco unitario, equivalentes entre sí hasta una elección de factor de escala:
- Un gráfico formado a partir de una colección de puntos en el plano euclidiano, en el que dos puntos están conectados si su distancia está por debajo de un umbral fijo.
- Un gráfico de intersección de círculos de igual radio o de discos de igual radio (ver Fig. 1).
- Un gráfico formado a partir de una colección de círculos de igual radio, en el que dos círculos están conectados por un borde si un círculo contiene 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 K 1,7 con un nodo central conectado a siete hojas: si cada uno de los siete discos unitarios toca un disco unitario común, unos dos de los siete discos deben tocarse entre sí. (ya que el número de besos en el avión es 6). Por lo tanto, los gráficos de disco unitario no pueden contener un subgrafo K 1,7 inducido .
Aplicaciones
A partir del trabajo de Huson & Sen (1995) , los gráficos de discos unitarios se han utilizado en informática para modelar la topología de redes de comunicación inalámbrica 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 una señal de un nodo puede ser recibida por otro 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 disco unitarios con centros de disco generados aleatoriamente, también se han utilizado como modelo de percolación y varios otros fenómenos. [1]
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 disco unitario correspondiente en tiempo lineal , redondeando los centros a puntos de cuadrícula enteros cercanos , usando una tabla hash. para encontrar todos los pares de centros a una distancia constante entre sí, y filtrar la lista de pares resultante 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 ( Bentley, Stanat & Williams 1977 ).
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. [2] Además, es probablemente imposible en tiempo polinómico generar coordenadas explícitas de una representación gráfica de disco unitario: existen gráficos de disco unitario que requieren exponencialmente muchos bits de precisión en cualquier representación de este tipo. [3]
Sin embargo, muchos problemas importantes y difíciles de optimización de gráficos, como el conjunto independiente máximo , el color del gráfico y el conjunto dominante mínimo , se pueden aproximar de manera eficiente utilizando la estructura geométrica de estos gráficos, [4] y el problema de la camarilla máxima se puede resolver exactamente para estos gráficos. en tiempo polinomial, dada una representación de disco. [5] Incluso si no se conoce la representación de un disco, y se da un gráfico abstracto como entrada, es posible en el tiempo polinomial producir un clique máximo o una prueba de que el gráfico no es un gráfico de disco unitario, [6] y para aproximar la coloración óptima mediante el uso de un algoritmo de coloración codicioso . [7]
Cuando un conjunto de vértices dado forma un subconjunto de una red triangular , se conoce una condición necesaria y suficiente para la perfección de un gráfico unitario. [8] Para los gráficos perfectos, varios problemas de optimización NP-completos ( problema de coloración de gráficos , problema de clique máximo y problema de conjunto independiente máximo ) se pueden resolver polinomialmente.
Ver también
- Resistencia de barrera , un problema algorítmico de ruptura de ciclos en gráficos de discos unitarios
- Gráfico de indiferencia , un análogo unidimensional de los gráficos de disco unitario
- Penny graph , los gráficos de disco unitarios para los que los discos pueden ser tangentes pero no superpuestos ( gráfico de contacto )
- Gráfico de monedas , el gráfico de contacto de discos (no necesariamente del tamaño de una unidad)
- 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 por puntos de conexión que están a una distancia exactamente uno en lugar de (como aquí) como máximo un umbral determinado
Notas
- ^ Véase, por ejemplo, Dall & Christensen (2002) .
- ^ Breu y Kirkpatrick (1998) ; Kang y Müller (2011) .
- ^ McDiarmid y Mueller (2011) .
- ^ Marathe y col. (1994) ; Matsui (2000) .
- ^ Clark, Colbourn y Johnson (1990) .
- ^ Raghavan y Spinrad (2003) .
- ^ Gräf, Stumpf y Weißenfels (1998) .
- ^ Miyamoto y Matsui (2005) .
Referencias
- Bentley, Jon L .; Stanat, Donald F .; Williams, E. Hollins, Jr. (1977), "La complejidad de encontrar vecinos cercanos de radio fijo", Information Processing Letters , 6 (6): 209–212, doi : 10.1016 / 0020-0190 (77) 90070-9 , MR 0489084.
- Breu, Heinz; Kirkpatrick, David G. (1998), "El reconocimiento de grafos de disco unitario es NP-hard", Computational Geometry: Theory and Applications , 9 (1–2): 3–24, doi : 10.1016 / s0925-7721 (97) 00014- X.
- Clark, Brent N .; Colbourn, Charles J .; Johnson, David S. (1990), "Unit disk graphs", Discrete Mathematics , 86 (1-3): 165-177, doi : 10.1016 / 0012-365X (90) 90358-O.
- Dall, Jesper; Christensen, Michael (2002), "Gráficos geométricos aleatorios", Phys. Rev. E , 66 : 016121, arXiv : cond-mat / 0203026 , Bibcode : 2002PhRvE..66a6121D , doi : 10.1103 / PhysRevE.66.016121.
- Gräf, A .; Stumpf, M .; Weißenfels, G. (1998), "On coloring unit disk graphs", Algorithmica , 20 (3): 277-293, doi : 10.1007 / PL00009196 , MR 1489033.
- Huson, Mark L .; Sen, Arunabha (1995), "Algoritmos de programación de transmisiones para redes de radio", Conferencia de comunicaciones militares, IEEE MILCOM '95 , 2 , págs. 647–651, doi : 10.1109 / MILCOM.1995.483546 , ISBN 0-7803-2489-7.
- Kang, Ross J .; Müller, Tobias (2011), "Representaciones de gráficos en esferas y productos escalares ", Actas del Vigésimo Séptimo Simposio Anual sobre Geometría Computacional (SoCG'11), 13-15 de junio de 2011, París, Francia , págs. 308-314.
- Marathe, Madhav V .; Breu, Heinz; Hunt, 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.
- Matsui, Tomomi (2000), "Algoritmos de aproximación para problemas de conjuntos máximos independientes y problemas de coloración fraccional en gráficos de discos unitarios", Lecture Notes in Computer Science , Lecture Notes in Computer Science, 1763 : 194-200, doi : 10.1007 / 978-3 -540-46515-7_16 , ISBN 978-3-540-67181-7.
- McDiarmid, Colin; Mueller, Tobias (2011), Realizaciones enteras de gráficos de disco y segmento , arXiv : 1111.2931 , Bibcode : 2011arXiv1111.2931M
- Miyamoto, Yuichiro; Matsui, Tomomi (2005), "Perfectness and Imperfectness of the kth Power of Lattice Graphs" , Lecture Notes in Computer Science , Lecture Notes in Computer Science, 3521 : 233–242 , doi : 10.1007 / 11496199_26 , ISBN 978-3-540-26224-4.
- 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.