En teoría de grafos geométricos , un grafo de centavos es un grafo de contacto de círculos unitarios . Se forma a partir de una colección de círculos unitarios que no se cruzan entre sí, creando un vértice para cada círculo y una arista para cada par de círculos tangentes . [1] Los círculos se pueden representar físicamente mediante centavos , dispuestos sin superponerse sobre una superficie plana, con un vértice para cada centavo y una arista para cada dos centavos que se tocan.
Los grafos de centavos también se han llamado grafos de moneda unitaria , [2] porque son los grafos de moneda formados a partir de círculos unitarios. [1] Si cada vértice está representado por un punto en el centro de su círculo, entonces dos vértices serán adyacentes si y solo si su distancia es la distancia mínima entre todos los pares de vértices. Por lo tanto, los grafos de centavos también se han llamado grafos de distancia mínima , [3] grafos de distancia más pequeña , [4] o grafos de pares más cercanos . [5] De manera similar, en un grafo de vecino más cercano mutuo que vincula pares de puntos en el plano que son los vecinos más cercanos entre sí , cada componente conectado es un grafo de centavos, aunque los bordes en diferentes componentes pueden tener diferentes longitudes. [6]
Cada gráfico de centavos es un gráfico de disco unitario y un gráfico de cerillas . Al igual que los gráficos planares en general, obedecen al teorema de los cuatro colores , pero este teorema es más fácil de demostrar para los gráficos de centavos. Probar si un gráfico es un gráfico de centavos, o encontrar su conjunto independiente máximo , es NP-hard ; sin embargo, se conocen los límites superior e inferior para el tamaño del conjunto independiente máximo, más altos que los límites que son posibles para gráficos planares arbitrarios.
Cada vértice en un grafo de centavos tiene como máximo seis vértices vecinos; aquí el número seis es el número de beso para los círculos en el plano. Sin embargo, los centavos en el límite de la envoltura convexa tienen menos vecinos. Contando con más precisión esta reducción en los vecinos para los centavos del límite conduce a un límite preciso en el número de aristas en cualquier grafo de centavos: un grafo de centavos con n vértices tiene como máximo aristas. Algunos grafos de centavos, formados al organizar los centavos en una cuadrícula triangular , tienen exactamente este número de aristas. [7] [8] [9]
Al organizar los centavos en una cuadrícula cuadrada , o en la forma de ciertos grafos cuadrados , se pueden formar grafos de centavos sin triángulos cuyo número de aristas es al menos y en cualquier grafo de centavos sin triángulos el número de aristas es como máximo [10] Swanepoel conjeturó que el límite es estricto. [11] Probar esto, o encontrar un límite mejor, permanece abierto.
Cada grafo de centavo contiene un vértice con tres vecinos como máximo. Por ejemplo, dicho vértice se puede encontrar en una de las esquinas de la envoltura convexa de los centros de los círculos. Por lo tanto, los grafos de centavo tienen una degeneración de tres como máximo. Con base en esto, se puede demostrar que sus coloraciones gráficas requieren como máximo cuatro colores, mucho más fácilmente que la prueba del teorema de los cuatro colores más general . [12] Sin embargo, a pesar de su estructura restringida, existen grafos de centavo que aún requieren cuatro colores. [13]
Análogamente, la degeneración de cada grafo de centavo sin triángulos es como máximo dos. Cada uno de estos grafos contiene un vértice con como máximo dos vecinos, aunque no siempre es posible encontrar este vértice en la envoltura convexa. Con base en esto, se puede demostrar que requieren como máximo tres colores, más fácilmente que la prueba del teorema de Grötzsch más general de que los grafos planares sin triángulos son 3-coloreables. [10]
Un conjunto independiente máximo en un gráfico de centavos es un subconjunto de los centavos, de los cuales ninguno se toca entre sí. Encontrar conjuntos independientes máximos es NP-difícil para gráficos arbitrarios, y sigue siendo NP-difícil en gráficos de centavos. [2] Es un ejemplo del problema del conjunto disjunto máximo , en el que uno debe encontrar grandes subconjuntos de regiones no superpuestas del plano. Sin embargo, como ocurre con los gráficos planares en general, la técnica de Baker proporciona un esquema de aproximación en tiempo polinomial para este problema. [14]
En 1983, Paul Erdős pidió el número más grande c tal que cada grafo de centavos de n vértices tenga un conjunto independiente de al menos cn vértices. [15] Es decir, si colocamos n centavos en una superficie plana, debería haber un subconjunto de cn de los centavos que no se toquen entre sí. Por el teorema de los cuatro colores, c ≥ 1/4 , y el límite mejorado c ≥ 8/31 ≈ 0,258 fue demostrado por Swanepoel. [16] En la otra dirección, Pach y Tóth demostraron que c ≤ 5/16 = 0,3125 . [15] A partir de 2013, estos seguían siendo los mejores límites conocidos para este problema. [4] [17]
La construcción de un gráfico de centavos a partir de las ubicaciones de sus n círculos se puede realizar como una instancia del problema del par de puntos más cercano , tomando el tiempo del peor caso O ( n log n ) [5] o (con tiempo aleatorio y con el uso de la función de piso ) el tiempo esperado O ( n ) . [18] Un método alternativo con el mismo tiempo del peor caso es construir la triangulación de Delaunay o el gráfico del vecino más cercano de los centros de los círculos (ambos contienen el gráfico de centavos como un subgráfico) [5] y luego probar qué bordes corresponden a las tangencias de los círculos.
Sin embargo, si se proporciona un gráfico sin posiciones geométricas para sus vértices, entonces probar si se puede representar como un gráfico de centavos es NP-difícil . [6] Sigue siendo NP-difícil incluso cuando el gráfico dado es un árbol . [19] De manera similar, probar si un gráfico se puede representar como un gráfico tridimensional de vecino mutuo más cercano también es NP-difícil. [20]
Es posible realizar algunas tareas computacionales en gráficos de centavos dirigidos, como probar si un vértice puede alcanzar a otro, en tiempo polinomial y sustancialmente menor que el espacio lineal, dada una entrada que representa sus círculos en una forma que permite tareas computacionales básicas como probar la adyacencia y encontrar intersecciones de los círculos con líneas paralelas al eje. [21]
Los gráficos de centavos son un caso especial de los gráficos de monedas (gráficos que pueden representarse por tangencias de círculos no cruzados de radios arbitrarios). [1] Debido a que los gráficos de monedas son los mismos que los gráficos planares , [22] todos los gráficos de centavos son planares. Los gráficos de centavos también son gráficos de disco unitario (los gráficos de intersección de círculos unitarios), [2] gráficos de distancia unitaria (gráficos que pueden dibujarse con todos los bordes con longitudes iguales, lo que permite cruces), [23] y gráficos de cerillas (gráficos que pueden dibujarse en el plano con bordes rectos de longitud igual y sin cruces de bordes). [24]
{{citation}}: CS1 maint: DOI inactivo a partir de julio de 2024 ( enlace )