stringtranslate.com

Gráfico de disco unitario

Una colección de círculos unitarios y el gráfico de disco unitario correspondiente.

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:

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

Notas

  1. ^ Dębski, Junosza-Szaniawski y Śleszyńska-Nowak (2020).
  2. ^ Atminas y Zamaraev (2018).
  3. ^ McDiarmid y Muller (2014).
  4. ^ Capo y col. (2022).
  5. ^ Véase, por ejemplo, Dall y Christensen (2002).
  6. ^ Bentley, Stanat y Williams (1977).
  7. ^ Breu y Kirkpatrick (1998); Kang y Muller (2011).
  8. ^ McDiarmid y Mueller (2013).
  9. ^ Marathe y col. (1994); Matsui (2000).
  10. ^ Clark, Colbourn y Johnson (1990).
  11. ^ Raghavan y Spinrad (2003).
  12. ^ Gräf, Stumpf y Weißenfels (1998).

Referencias