En teoría de grafos, el gráfico de círculo unitario es el gráfico de intersección de una familia de círculos unitarios en el plano euclidiano . Es decir, formamos un vértice para cada círculo y conectamos dos vértices con una arista si los círculos correspondientes se cruzan.
Existen varias opciones para definir el gráfico de círculos unitarios, que son equivalentes hasta la elección del coeficiente:
Cualquier subgráfico generado del gráfico de círculo unitario también es un gráfico de círculo unitario. Un ejemplo de un gráfico que no es un gráfico de círculo unitario es la estrella K 1,7 con un vértice central conectado a siete hojas: si cada uno de los siete círculos toca el círculo central, cualquier par de círculos debe tocarse entre sí (ya que el el número de contacto en el avión es 6). Por lo tanto, el gráfico de círculo unitario no puede contener K 1,7 como un subgráfico generado.
Desde el trabajo de Huson y Sen ( Huson, Sen 1995 ), los gráficos de círculo unitario se han utilizado en informática para modelar la topología de redes inalámbricas descentralizadas autoorganizadas . En esta aplicación, los nodos están conectados por comunicación inalámbrica directa sin una estación base . Se supone que todos los vértices son homogéneos y están equipados con antenas omnidireccionales . La ubicación de las antenas se modela como puntos en el plano euclidiano, y el área donde la señal puede ser recibida por otro vértice se modela como un círculo. Si todos los vértices tienen emisores de la misma potencia, estos círculos tendrán el mismo radio. Los gráficos geométricos aleatorios formados como gráficos de círculo unitario con centros aleatorios se pueden usar para modelar el filtrado y algunos otros fenómenos. [una]
El problema de si un gráfico dado de forma abstracta puede representarse como un gráfico de círculo unitario es NP-difícil (más precisamente, completo para la teoría existencial de los números reales ) [2] [3] . Además, es una imposibilidad comprobada en tiempo polinomial encontrar ciertas coordenadas de círculos unitarios: hay gráficos de círculos unitarios que requieren un número exponencial de bits de precisión en cualquier representación [4] .
Sin embargo, muchos problemas de optimización importantes y complejos en gráficos, como el problema del conjunto independiente , la coloración del gráfico y el problema del conjunto dominante mínimo , se pueden aproximar de manera efectiva utilizando la estructura geométrica de estos gráficos [5] [6] y el problema de la camarilla . ya que estos gráficos se pueden resolver exactamente en tiempo polinomial si se da la representación circular [7] . Más precisamente, para un gráfico dado, en tiempo polinomial, se puede encontrar la camarilla máxima o probar que el gráfico no es un gráfico de círculo unitario [8] .
Si el conjunto de vértices dado forma un subconjunto de la red triangular , se conoce la condición necesaria y suficiente para la perfección del grafo [9] . Para gráficos perfectos, muchos problemas de optimización NP-completos (el problema de coloración de gráficos , el problema de la camarilla máxima y el problema del conjunto independiente ) se pueden resolver en tiempo polinomial.