stringtranslate.com

Gráfica de disco unitario

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

En la teoría de grafos geométricos , un grafo de disco unitario es el grafo de intersección de una familia de discos unitarios en el plano euclidiano . Es decir, es un grafo con un vértice por cada disco de la familia y con una arista entre dos vértices siempre que los vértices correspondientes se encuentren a una distancia unitaria entre sí.

Comúnmente se forman a partir de un proceso puntual de Poisson , lo que los convierte en un ejemplo simple de estructura aleatoria.

Definiciones

Existen varias definiciones posibles del gráfico del disco unitario, equivalentes entre sí hasta la elección del factor de escala:

Propiedades

Cada subgrafo inducido de un grafo de disco unitario es también un grafo de disco unitario. Un ejemplo de un grafo que no es un grafo 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 grafos de disco unitario no pueden contener un subgrafo inducido. [1] Se conocen infinitos otros subgrafos inducidos prohibidos. [2]

La cantidad de gráficos de discos unitarios en 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 un ancho gemelo acotado . [4]

Aplicaciones

A partir del trabajo de Huson y Sen (1995), los gráficos de disco unitario 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 unitario con centros de disco generados aleatoriamente, también se han utilizado como modelo de percolación y varios otros fenómenos. [5]

Complejidad computacional

Si se 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 de la cuadrícula cercanos , utilizando una tabla hash para encontrar todos los pares de centros dentro de una distancia constante entre sí y filtrando la lista resultante de pares para aquellos cuyos círculos se intersecan. 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 como función de la dimensión. [6]

Es NP-difícil (más específicamente, completo para la teoría existencial de los números 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 polinomial generar coordenadas explícitas de una representación de gráfico de disco unitario: existen gráficos de disco unitario que requieren exponencialmente muchos bits de precisión en cualquier representación de este tipo. [8]

Sin embargo, muchos problemas de optimización de grafos importantes y difíciles, como el conjunto independiente máximo , la coloración de grafos y el conjunto dominante mínimo, se pueden aproximar de manera eficiente utilizando la estructura geométrica de estos grafos, [9] y el problema de la camarilla máxima se puede resolver exactamente para estos grafos en tiempo polinomial, dada una representación de disco. [10] Incluso si no se conoce una representación de disco y se proporciona un grafo abstracto como entrada, es posible en tiempo polinomial producir una camarilla máxima o una prueba de que el grafo no es un grafo de disco unitario, [11] y 3-aproximar la coloración óptima utilizando un algoritmo de coloración voraz . [12]

Véase también

Notas

  1. ^ Dębski, Junosza-Szaniawski y Śleszyńska-Nowak (2020).
  2. ^ Atminas y Zamaraev (2018).
  3. ^ McDiarmid y Müller (2014).
  4. ^ Bonnet y otros (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