En la teoría de grafos , un área de las matemáticas, un grafo sin garra es un grafo que no tiene una garra como subgrafo inducido .
Una garra es otro nombre para el grafo bipartito completo K 1,3 (es decir, un grafo en estrella que comprende tres aristas, tres hojas y un vértice central). Un grafo sin garras es un grafo en el que ningún subgrafo inducido es una garra; es decir, cualquier subconjunto de cuatro vértices tiene algo más que solo tres aristas que los conectan en este patrón. De manera equivalente, un grafo sin garras es un grafo en el que la vecindad de cualquier vértice es el complemento de un grafo sin triángulos .
Los grafos sin garras se estudiaron inicialmente como una generalización de los grafos lineales , y obtuvieron una motivación adicional a través de tres descubrimientos clave sobre ellos: el hecho de que todos los grafos conectados sin garras de orden par tienen emparejamientos perfectos , el descubrimiento de algoritmos de tiempo polinomial para encontrar conjuntos independientes máximos en grafos sin garras, y la caracterización de grafos perfectos sin garras . [1] Son el tema de cientos de artículos de investigación matemática y varias encuestas. [1]
Es sencillo verificar que un grafo dado con n vértices y m aristas está libre de garras en el tiempo O( n 4 ), probando cada 4-tupla de vértices para determinar si inducen una garra. [6] Con más eficiencia y mayor complicación, uno puede probar si un grafo está libre de garras verificando, para cada vértice del grafo, que el grafo complementario de sus vecinos no contiene un triángulo. Un grafo contiene un triángulo si y solo si el cubo de su matriz de adyacencia contiene un elemento diagonal distinto de cero, por lo que encontrar un triángulo puede realizarse en el mismo límite de tiempo asintótico que la multiplicación de matrices n × n . [7] Por lo tanto, utilizando el algoritmo Coppersmith–Winograd , el tiempo total para este algoritmo de reconocimiento libre de garras sería O( n 3.376 ).
Kloks, Kratsch y Müller (2000) observan que en cualquier grafo sin garras, cada vértice tiene como máximo 2 √ m vecinos; de lo contrario, por el teorema de Turán, los vecinos del vértice no tendrían suficientes aristas restantes para formar el complemento de un grafo sin triángulos. Esta observación permite que la comprobación de cada vecindad en el algoritmo basado en la multiplicación rápida de matrices descrito anteriormente se realice en el mismo límite de tiempo asintótico que la multiplicación de matrices 2 √ m × 2 √ m , o más rápido para vértices con grados incluso inferiores. El peor caso para este algoritmo ocurre cuando Ω( √ m ) vértices tienen Ω( √ m ) vecinos cada uno, y los vértices restantes tienen pocos vecinos, por lo que su tiempo total es O( m 3.376/2 ) = O( m 1.688 ).
Debido a que los grafos sin garras incluyen complementos de grafos sin triángulos, el número de grafos sin garras en n vértices crece al menos tan rápido como el número de grafos sin triángulos, exponencialmente en el cuadrado de n . Los números de grafos sin garras conectados en n nodos, para n = 1, 2, ... son
Si se permite que los gráficos estén desconectados, el número de gráficos es aún mayor: son
Una técnica de Palmer, Read y Robinson (2002) permite contar el número de gráficos cúbicos sin garras de manera muy eficiente, algo inusual en los problemas de enumeración de gráficos .
Sumner (1974) e, independientemente, Las Vergnas (1975) demostraron que todo grafo conexo sin garras con un número par de vértices tiene un emparejamiento perfecto . [8] Es decir, existe un conjunto de aristas en el grafo tal que cada vértice es un punto final de exactamente una de las aristas emparejadas. El caso especial de este resultado para grafos de línea implica que, en cualquier grafo con un número par de aristas, uno puede dividir las aristas en caminos de longitud dos. Los emparejamientos perfectos pueden usarse para proporcionar otra caracterización de los grafos sin garras: son exactamente los grafos en los que cada subgrafo inducido conexo de orden par tiene un emparejamiento perfecto. [8]
La prueba de Sumner muestra, con mayor fuerza, que en cualquier grafo conexo sin garras se puede encontrar un par de vértices adyacentes cuya eliminación deja conectado el grafo restante. Para demostrar esto, Sumner encuentra un par de vértices u y v que estén lo más separados posible en el grafo, y elige w como vecino de v que esté lo más alejado posible de u ; como demuestra, ni v ni w pueden estar en ningún camino más corto desde cualquier otro nodo hasta u , por lo que la eliminación de v y w deja conectado el grafo restante. La eliminación repetida de pares de vértices coincidentes de esta manera forma una coincidencia perfecta en el grafo sin garras dado.
La misma idea de prueba se cumple de manera más general si u es cualquier vértice, v es cualquier vértice que está máximamente lejos de u y w es cualquier vecino de v que está máximamente lejos de u . Además, la eliminación de v y w del grafo no cambia ninguna de las otras distancias desde u . Por lo tanto, el proceso de formación de una correspondencia mediante la búsqueda y eliminación de pares vw que están máximamente lejos de u se puede realizar mediante un único recorrido de postorden de un árbol de búsqueda en amplitud del grafo, con raíz en u , en tiempo lineal. Chrobak, Naor y Novick (1989) proporcionan un algoritmo alternativo de tiempo lineal basado en la búsqueda en profundidad , así como algoritmos paralelos eficientes para el mismo problema.
Faudree, Flandrin y Ryjáček (1997) enumeran varios resultados relacionados, incluyendo los siguientes: los grafos K 1, r -libres de orden par y conexos ( r − 1) tienen emparejamientos perfectos para cualquier r ≥ 2; los grafos sin garras de orden impar con como máximo un vértice de grado uno pueden dividirse en un ciclo impar y un emparejamiento; para cualquier k que sea como máximo la mitad del grado mínimo de un grafo sin garras en el que k o el número de vértices es par, el grafo tiene un factor k ; y, si un grafo sin garras está conexo (2 k + 1), entonces cualquier emparejamiento de aristas k puede extenderse a un emparejamiento perfecto.
Un conjunto independiente en un grafo lineal corresponde a una correspondencia en su grafo subyacente, un conjunto de aristas que no comparten un punto final. El algoritmo Blossom de Edmonds (1965) encuentra una correspondencia máxima en cualquier grafo en tiempo polinomial, lo que equivale a calcular un conjunto independiente máximo en grafos lineales. Esto ha sido ampliado independientemente a un algoritmo para todos los grafos sin garras por Sbihi (1980) y Minty (1980). [9]
Ambos enfoques utilizan la observación de que en grafos sin garras, ningún vértice puede tener más de dos vecinos en un conjunto independiente, y por lo tanto la diferencia simétrica de dos conjuntos independientes debe inducir un subgrafo de grado dos como máximo; es decir, es una unión de caminos y ciclos. En particular, si I es un conjunto independiente no máximo, difiere de cualquier conjunto independiente máximo por ciclos pares y los llamados caminos de aumento : caminos inducidos que alternan entre vértices que no están en I y vértices en I , y para los cuales ambos puntos finales tienen solo un vecino en I . Como la diferencia simétrica de I con cualquier camino de aumento da un conjunto independiente más grande, la tarea se reduce a buscar caminos de aumento hasta que no se puedan encontrar más, de manera análoga a los algoritmos para encontrar emparejamientos máximos.
El algoritmo de Sbihi recrea el paso de contracción de flor del algoritmo de Edmonds y agrega un paso de contracción de camarilla similar, pero más complicado . El enfoque de Minty es transformar la instancia del problema en un gráfico de línea auxiliar y usar el algoritmo de Edmonds directamente para encontrar los caminos de aumento. Después de una corrección de Nakamura y Tamura 2001, el resultado de Minty también se puede usar para resolver en tiempo polinomial el problema más general de encontrar en gráficos sin garras un conjunto independiente de peso máximo. También se conocen generalizaciones de estos resultados a clases más amplias de gráficos. [9] Al mostrar un teorema de estructura novedoso, Faenza, Oriolo y Stauffer (2011) dieron un algoritmo de tiempo cúbico, que también funciona en el entorno ponderado.
Un grafo perfecto es un grafo en el que el número cromático y el tamaño de la camarilla máxima son iguales, y en el que esta igualdad persiste en cada subgrafo inducido. Ahora se sabe (el teorema fuerte del grafo perfecto ) que los grafos perfectos pueden caracterizarse como los grafos que no tienen como subgrafos inducidos ni un ciclo impar ni el complemento de un ciclo impar (un llamado agujero impar ). [10] Sin embargo, durante muchos años esto permaneció como una conjetura sin resolver, solo probada para subclases especiales de grafos. Una de estas subclases fue la familia de grafos sin garras: varios autores descubrieron que los grafos sin garras sin ciclos impares y agujeros impares son perfectos. Los grafos sin garras perfectos pueden reconocerse en tiempo polinomial. En un grafo sin garras perfecto, la vecindad de cualquier vértice forma el complemento de un grafo bipartito . Es posible colorear grafos sin garras perfectos, o encontrar camarillas máximas en ellos, en tiempo polinomial. [11]
En general, es NP-difícil encontrar la camarilla más grande en un grafo sin garras. [12] También es NP-difícil encontrar una coloración óptima del grafo, porque (a través de grafos lineales) este problema generaliza el problema NP-difícil de calcular el índice cromático de un grafo. [6] Por la misma razón, es NP-difícil encontrar una coloración que logre una razón de aproximación mejor que 4/3. Sin embargo, una razón de aproximación de dos se puede lograr mediante un algoritmo de coloración voraz , porque el número cromático de un grafo sin garras es mayor que la mitad de su grado máximo. Una generalización de la conjetura de coloración de la lista de aristas establece que, para grafos sin garras, el número cromático de la lista es igual al número cromático; estos dos números pueden estar muy separados en otros tipos de grafos. [13]
Los grafos sin garras están acotados por χ , lo que significa que cada grafo sin garras de un número cromático grande contiene una camarilla grande. Más fuertemente, del teorema de Ramsey se sigue que cada grafo sin garras de un grado máximo grande contiene una camarilla grande, de tamaño aproximadamente proporcional a la raíz cuadrada del grado. Para grafos sin garras conexos que incluyen al menos un conjunto independiente de tres vértices, es posible una relación más fuerte entre el número cromático y el tamaño de la camarilla: en estos grafos, existe una camarilla de tamaño al menos la mitad del número cromático. [14]
Aunque no todos los grafos sin garras son perfectos, los grafos sin garras satisfacen otra propiedad, relacionada con la perfección. Un grafo se llama dominación perfecta si tiene un conjunto dominante mínimo que es independiente, y si la misma propiedad se cumple en todos sus subgrafos inducidos. Los grafos sin garras tienen esta propiedad. Para ver esto, sea D un conjunto dominante en un grafo sin garras, y supongamos que v y w son dos vértices adyacentes en D ; entonces el conjunto de vértices dominados por v pero no por w debe ser una camarilla (de lo contrario v sería el centro de una garra). Si cada vértice en esta camarilla ya está dominado por al menos otro miembro de D , entonces v puede eliminarse produciendo un conjunto dominante independiente más pequeño, y de lo contrario v puede reemplazarse por uno de los vértices no dominados en su camarilla produciendo un conjunto dominante con menos adyacencias. Al repetir este proceso de reemplazo, uno llega eventualmente a un conjunto dominante no mayor que D , por lo que, en particular, cuando el conjunto inicial D es un conjunto dominante mínimo, este proceso forma un conjunto dominante independiente igualmente pequeño. [15]
A pesar de esta propiedad de perfección de dominación, es NP-difícil determinar el tamaño del conjunto dominante mínimo en un grafo sin garras. [6] Sin embargo, en contraste con la situación para clases más generales de grafos, encontrar el conjunto dominante mínimo o el conjunto dominante conectado mínimo en un grafo sin garras es manejable con parámetros fijos : se puede resolver en un tiempo limitado por un polinomio en el tamaño del grafo multiplicado por una función exponencial del tamaño del conjunto dominante. [16]
Chudnovsky y Seymour (2005) describen una serie de artículos en los que prueban una teoría de estructura para grafos sin garras, análoga al teorema de estructura de grafos para familias de grafos menores cerrados probado por Robertson y Seymour, y a la teoría de estructura para grafos perfectos que Chudnovsky, Seymour y sus coautores usaron para probar el teorema de grafos perfectos fuertes. [10] La teoría es demasiado compleja para describirla en detalle aquí, pero para dar una idea de ella, basta con esbozar dos de sus resultados. Primero, para una subclase especial de grafos sin garras que ellos llaman grafos cuasi-lineales (equivalentemente, grafos localmente co-bipartitos), afirman que cada uno de esos grafos tiene una de dos formas:
Chudnovsky y Seymour clasifican gráficos libres de garras conexos arbitrarios en uno de los siguientes:
Gran parte del trabajo en su teoría de la estructura implica un análisis adicional de los grafos antiprismáticos. El grafo de Schläfli , un grafo fuertemente regular sin garras con parámetros srg(27,16,10,8), desempeña un papel importante en esta parte del análisis. Esta teoría de la estructura ha llevado a nuevos avances en la combinatoria poliédrica y a nuevos límites en el número cromático de grafos sin garras, [5] [17] así como a nuevos algoritmos manejables con parámetros fijos para conjuntos dominantes en grafos sin garras. [18]
{{citation}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace ).