Contar sin pinzas

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 12 de septiembre de 2021; la verificación requiere 1 edición .

En teoría de grafos, un grafo sin garras es un grafo que no contiene subgrafos generados isomorfos a K 1,3 ( garras ).

Una garra es un grafo bipartito completo K 1,3 (es decir, una estrella de tres aristas, tres hojas y un vértice central). Un grafo sin garras es un grafo en el que ningún subgrafo generado es una garra, es decir, no hay cuatro vértices A , B , C y O tales que O esté conectado a A , B y C , pero los vértices A , B y C no lo están . conectados entre sí. También es posible definir un gráfico sin garras como uno en el que la vecindad de cualquier vértice forma el complemento del gráfico sin triángulos .

Los gráficos sin garras se estudiaron originalmente como una generalización de los gráficos de líneas y recibieron un estímulo adicional cuando se descubrieron tres hechos clave sobre ellos:

el hecho de que todas las gráficas conectadas sin garras de orden uniforme tienen coincidencias perfectas ;
descubrimiento de un algoritmo polinomial de tiempo para encontrar el máximo conjunto independiente en grafos sin garras;
descripción de grafos perfectos sin garras [1] . Cientos de artículos y varias revisiones se han dedicado a los gráficos sin garras [2] .

Ejemplos

El gráfico lineal L ( G ) de cualquier gráfico G no tiene garras. L ( G ) contiene un vértice para cada arco en G y los vértices son conjugados en L ( G ) cuando las aristas correspondientes comparten un vértice en G . El gráfico lineal L ( G ) no puede tener garras, porque si cada una de las tres aristas e 1 , e 2 y e 3 en G tiene un vértice común con la cuarta arista e 4 , entonces por el principio de Dirichlet hay al menos 2 las aristas de e 1 , e 2 y e 3 tienen un vértice común. Los gráficos lineales se pueden describir mediante nueve subgráficos prohibidos [3] y la garra es el más simple de estos nueve gráficos. Esto proporciona un motivo para estudiar grafos sin garras [1] .

Los gráficos de De Bruijn (gráficos cuyos vértices corresponden a cadenas binarias de n bits para algunos n , y cuyos arcos corresponden a coincidencias de ( n −1) bits) no tienen garras. Una forma de mostrar esto es construir el gráfico de Bruijn para cadenas de n bits como el gráfico lineal de De Bruijn para cadenas de ( n − 1) bits.
El complemento de cualquier gráfico sin triángulos no tiene garras [4] . Estos gráficos incluyen cualquier gráfico completo como caso especial.
Los gráficos de intervalos propios son gráficos de intervalos formados como gráficos de intersecciones por familias de intervalos en los que ningún intervalo contiene otro intervalo de la familia; no tienen garras, ya que cuatro de esos intervalos no pueden cruzarse en un patrón de garras [4] .
El huso de Moser es un gráfico con siete vértices, que se utiliza para probar el límite inferior del número cromático del plano , no tiene garras.
Los gráficos de algunos poliedros y politopos no tienen garras. Esto incluye el grafo de un tetraedro y en general cualquier simplex (grafo completo), el grafo de un octaedro y, en general, cualquier politopo cruzado ( isomorfo al grafo cocktail party , que se obtiene quitando un emparejamiento perfecto de un gráfico completo), el gráfico de un icosaedro regular [5] y un recuento de dieciséis celdas .
El gráfico de Schläfli , un gráfico fuertemente regular con 27 vértices, no tiene garras [5] .

Reconocimiento

Se puede comprobar directamente que un gráfico dado con n vértices y m aristas no tiene garras en tiempo O( n 4 ) comprobando cada cuatro vértices para ver si generan una garra [6] . De manera algo más eficiente, pero más difícil, se puede comprobar que un gráfico no tiene garras comprobando para cada vértice del gráfico que el complemento del gráfico vecino del vértice no contiene un triángulo. Un gráfico contiene un triángulo si y solo si el cubo de la matriz de adyacencia contiene un elemento diagonal distinto de cero, por lo que la búsqueda de un triángulo se puede realizar en el mismo tiempo asintótico que la multiplicación de matrices n × n [7] . Así, usando el algoritmo de Coppersmith-Winograd , el tiempo total para determinar si un grafo tiene garras será O( n 3.376 ).

Kloks, Kratsch y Müller ( Kloks, Kratsch, Müller ) [8] llamaron la atención sobre el hecho de que en un grafo sin garras cada vértice tiene un máximo de vecinos, de lo contrario, según el teorema de Turan , la vecindad del vértice no tendrá suficientes aristas para formar el complemento de la gráfica sin triángulos. Esta observación nos permite verificar los vecinos usando el algoritmo de producto de matriz rápido mencionado anteriormente en el mismo tiempo asintótico . El peor caso de este algoritmo ocurre cuando los vértices Ω(√ m ) tienen cada uno Ω(√ m ) vecinos y los vértices restantes tienen pocos vecinos, en cuyo caso el tiempo total es ( m 3.376/2 ) = O( m 1.688 ). $2{\sqrt {m))$ $2{\sqrt {m}}{\sqrt {m}}$

Enumeración

Dado que los gráficos sin garras incluyen todos los complementos de los gráficos sin triángulos, el número de gráficos sin garras con n vértices crece al menos al mismo ritmo que el número de gráficos sin triángulos, es decir, exponencialmente desde la raíz de n . Número de grafos conectados sin garras con n aristas, para n = 1, 2, …

1, 1, 2, 5, 14, 50, 191, 881, 4494, 26389, 184749, ... Secuencia OEIS A022562 .

Si las gráficas se pueden desconectar, el número de gráficas es mayor:

1, 2, 4, 10, 26, 85, 302, 1285, 6170, ... Secuencia OEIS A086991 .

La técnica de Palmer, Read, Robinson ( Palmer, Read, Robinson, 2002 ) [9] permite calcular el número de grafos cúbicos sin garras de manera muy eficiente, lo cual es inusual para problemas de enumeración de grafos .

Coincidencia

Sumner ( Sumner, 1974 ) [10] e, independientemente, Las Vergnas ( Las Vergnas, 1975 ) [11] demostraron que cualquier grafo conexo sin garras con un número par de vértices tiene un emparejamiento perfecto [12] . Es decir, hay un conjunto de aristas en el gráfico tal que cada vértice es el vértice final de exactamente una arista del emparejamiento. De esto se deduce que para gráficos lineales con un número par de aristas, es posible dividir todas las aristas en un camino de longitud dos. Las coincidencias perfectas se pueden usar para otra característica de los gráficos sin garras: estos son exactamente aquellos gráficos en los que cualquier subgrafo generado conectado de orden par tiene una coincidencia perfecta [12] .

La prueba de Sumner muestra, estrictamente hablando, que en cualquier grafo conexo sin garras se pueden encontrar un par de vértices conjugados cuya eliminación deja al grafo conexo. Para probar esto, Sumner encuentra un par de vértices u y v que están lo más alejados posible y elige w entre los vecinos del vértice v que está lo más alejado posible de u . Como mostró, ni v ni w pueden estar en el camino más corto desde cualquier otro vértice a u , por lo que eliminar v y w deja el gráfico conectado. La eliminación sucesiva de tales pares forma una combinación perfecta en un gráfico sin garras.

La misma idea de la prueba funciona en el caso más general: si u es cualquier vértice, v es cualquier vértice que esté lo más alejado posible de u , y w es cualquier vértice vecino de v que esté lo más alejado posible de u . Ahora, eliminar v y w del gráfico no cambia las distancias a u . Por lo tanto, el proceso de formación de emparejamientos mediante la búsqueda y eliminación de pares de vw que estén lo más lejos posible de u puede completarse en tiempo lineal simplemente recorriendo el árbol de búsqueda en anchura , comenzando desde el vértice u . Chrobak, Naor y Novick ( 1989 ) [13] dieron otro algoritmo lineal en el tiempo basado en la búsqueda primero en profundidad , así como algoritmos paralelos eficientes para el mismo problema.

Faudree , Flandrin, Ryjáček [2] dieron varios resultados estrechamente relacionados, incluidos los siguientes:

Un gráfico conexo ( r − 1) que no contiene K 1, r subgráficos de orden impar tienen coincidencias perfectas para cualquier r ≥ 2.
Los gráficos de orden impar sin garras con como máximo un vértice de grado uno se pueden dividir en un ciclo impar y una coincidencia.
Para cualquier k que sea al menos la mitad del grado mínimo de un gráfico sin garras en el que k o el número de vértices sea par, el gráfico tiene un factor k .
Si un grafo sin garras es ( 2k + 1) conectado, entonces cualquier coincidencia de k -aristas se puede extender a una coincidencia perfecta.

Conjuntos independientes

Un conjunto independiente en un gráfico lineal corresponde a una coincidencia en el gráfico original, es decir, un conjunto de aristas en el que dos aristas no tienen un punto común. Como mostró Edmonds ( 1965) [14] , la coincidencia máxima en cualquier gráfico se puede encontrar en el tiempo polinomial; Sbihi ( 1980 ) [15] extendió este algoritmo para que el nuevo algoritmo encuentre el máximo conjunto independiente en cualquier gráfico sin garras [16] . Minty ( Minty, 1980 ) [17] (corregido por Nakamura y Tamura ( Nakamura, Tamura, 2001 ) [18] ) dio otra extensión de los algoritmos de Edmond para grafos sin garras, que transforma el problema en emparejamiento en un grafo auxiliar obtenido de la gráfico original sin garras. El enfoque de Minty se puede utilizar para resolver el problema más general de encontrar un conjunto independiente de peso máximo en tiempo polinomial. Hay una generalización de estos resultados a una amplia clase de gráficos [16] .

Como señaló Sbihi, si es un conjunto independiente en un gráfico sin garras, entonces cualquier vértice del gráfico puede tener como máximo dos vértices vecinos de tres vértices vecinos que formarían una garra. Sbihi llama a un vértice saturado si tiene dos vecinos de e insaturado si no pertenece y al mismo tiempo tiene menos de dos vecinos de . De la observación de Sbyha se deduce que si y hay conjuntos independientes, el gráfico generado por , debe tener grado dos como máximo. Así, es la unión de caminos y ciclos. En particular, si no es un conjunto independiente máximo, se diferencia de cualquier conjunto independiente máximo por ciclos y caminos complementarios , es decir, caminos en los que se alternan vértices de y no de , y para los que ambos vértices finales no están saturados. La diferencia simétrica de los gráficos y la ruta de finalización es el máximo conjunto independiente (La diferencia simétrica de los gráficos H y G que tienen el mismo conjunto de vértices V es un gráfico con el mismo conjunto de vértices V, que contiene las aristas G y H, pero no contiene aristas comunes pertenecientes tanto a G como a H). El algoritmo de Sbiha aumenta gradualmente el tamaño del conjunto independiente al encontrar caminos complementarios siempre que se puedan encontrar dichos caminos. $yo$ $yo$ $yo$ $yo$ $yo$ $yo$ $j$ $I\copa J$ $yo$ $yo$ $yo$ $yo$

Encontrar una ruta de aumento es complicado porque una extensión de ruta puede no existir si contiene un borde entre dos vértices que no pertenecen a . Afortunadamente, esto puede ocurrir solo en dos casos: dos vértices adyacentes pueden ser los vértices finales del camino, o hay un vértice entre ellos que es adyacente a ambos. Cualquier otro vértice adyacente dará lugar a una garra. Los vértices terminales adyacentes se pueden eliminar eliminando temporalmente todos los vértices v adyacentes antes de buscar una ruta de finalización que comience en v . Si no se encuentra la ruta, el vértice v se puede eliminar del gráfico hasta el final del algoritmo. Después de tal reducción del gráfico, el problema se puede describir en términos de un gráfico de cambio , aunque Sbihy no usó esta terminología. Un gráfico de interruptor es un gráfico no dirigido en el que los arcos de cualquier vértice se dividen en dos grupos, y cualquier camino que pase por el vértice debe contener aristas de ambos grupos. Es posible construir un grafo interruptor sobre el conjunto de vértices saturados y no saturados de un grafo sin garras cuyas aristas conectan los vértices si no son adyacentes en el grafo original y hay un camino de longitud 2 entre ellos que pasa por un vértice de I . Los dos conjuntos de aristas en cada vértice están formados por los dos vértices I a través de los cuales pasan estos caminos de longitud 2. El camino en el gráfico de cambio entre dos vértices no saturados corresponde al camino complementario en el gráfico original. El gráfico de conmutación tiene complejidad cuadrática y la ruta en él se puede encontrar en tiempo lineal, y durante todo el tiempo del algoritmo puede ser necesario encontrar O ( n ) rutas de reabastecimiento. Por lo tanto, el algoritmo de Sbiha requiere un tiempo de ejecución O( n 3 ). $yo$

Colorear, clics y dominación

Un grafo perfecto es un grafo en el que el número cromático y el tamaño de la clique máxima son iguales, y en el que esta igualdad existe en cualquier subgrafo inducido. Se sabe (por el riguroso teorema del grafo perfecto ) que los grafos perfectos pueden caracterizarse como grafos que no tienen ciclos impares o complementos de ciclos impares (los llamados agujeros impares) como subgrafos inducidos (los llamados agujeros impares ) [ 5] . Sin embargo, durante muchos años este hecho siguió siendo una conjetura, demostrada solo para subclases especiales de gráficos. Una de esas subclases fue la familia de gráficos sin garras: varios autores encontraron que los gráficos sin garras y sin ciclos extraños y agujeros son perfectos. La perfección de un gráfico sin garras se puede comprobar en tiempo polinomial. En un grafo perfecto sin garras, la vecindad de cualquier vértice forma el complemento de un grafo bipartito . Puede colorear un gráfico perfecto sin garras o encontrar la camarilla máxima en él en tiempo polinomial [19] .

Si el gráfico sin garras no es perfecto, el problema de encontrar la camarilla máxima se vuelve NP-difícil [6] . El problema de encontrar la coloración óptima de tal gráfico también es NP-difícil, ya que (a través del gráfico lineal) este problema generaliza el problema NP-difícil de calcular el número cromático de un gráfico [6] . Por la misma razón, es NP-difícil encontrar un algoritmo de coloreo cuya eficiencia garantizada sea mejor que 4/3. Sin embargo, se puede obtener una eficiencia garantizada de dos en el algoritmo de coloración voraz , ya que el número cromático de un gráfico sin garras es superior a la mitad de su potencia máxima.

Si bien no todos los gráficos sin garras son perfectos, los gráficos sin garras satisfacen otra propiedad relacionada con la perfección. Un grafo se llama grafo de dominación perfecta si tiene un conjunto dominante mínimo , que es un conjunto independiente de vértices, y si todos los subgrafos generados tienen la misma propiedad. Los gráficos sin destellos tienen esta propiedad. Para mostrar esto, supongamos que D es un conjunto dominante en un gráfico sin garras, y sean v y w dos vértices conjugados de 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 la garra). Si cada vértice de esta camarilla ya está dominado por al menos un miembro de D , entonces se puede eliminar v para generar un conjunto dominante independiente más pequeño. De lo contrario, v puede ser reemplazado por uno de los vértices no dominados de la camarilla, generando un conjunto dominante con menos vértices adyacentes. Repitiendo estas sustituciones, llegaremos a un conjunto dominante no mayor que D , de modo que si el D inicial es el conjunto dominante mínimo, el proceso terminará con un conjunto dominante independiente de igual tamaño [20] .

A pesar de la propiedad de dominancia perfecta, determinar el tamaño del conjunto dominante mínimo en un gráfico sin garras es un problema NP-difícil [6] . Sin embargo, a diferencia de las clases más generales de gráficos, encontrar el conjunto dominante mínimo en un gráfico sin garras tiene una complejidad paramétrica con parámetros fijos : el problema se puede resolver en un tiempo que depende polinomialmente del tamaño del gráfico y exponencialmente de el tamaño del conjunto dominante [21] [22 ] .

Estructura

En una serie de artículos, Chudnovskaya y Seymour [23] demostraron una teoría de grafos estructurales sin garras similar al teorema de estructura de grafos para familias de grafos cerrados menores demostrado por Robertson y Seymour , y la teoría estructural para grafos perfectos de Chudnovsky ). Seymour y sus coautores solían probar el teorema del grafo estrictamente perfecto [5] . La teoría es demasiado compleja para describirla en detalle aquí, pero para mostrar su belleza, describimos algunos de sus resultados. Primero, para una subclase especial de gráficos sin garras, a los que llamaron gráficos cuasi-lineales (o gráficos cuasi-bipartidos localmente), afirman que cada gráfico tiene una de dos formas:

Un gráfico de intervalo circular difuso es una clase de gráficos que se pueden representar geométricamente como puntos y arcos en un círculo.
Un gráfico que se puede construir a partir de un multigráfico reemplazando cada borde con un gráfico de intervalo lineal difuso . Esto generaliza la construcción de gráficos lineales, en los que cada borde del multigrafo se reemplaza por un vértice. Los gráficos de intervalos lineales borrosos se construyen de la misma manera que los gráficos de intervalos circulares borrosos, solo en un segmento y no en un círculo.

Chudnovskaya y Seymour clasificaron gráficos conectados arbitrarios sin garras de la siguiente manera:

Seis gráficos específicos sin garras. Tres de ellos son gráficos de líneas, algunos gráficos de arco y subgráficos generados del icosaedro . Los tres restantes requieren definiciones adicionales.
Gráficos formados de cuatro formas sencillas a partir de gráficos más pequeños sin garras.
Los gráficos antiprismáticos , una clase de gráficos densos , se definen como gráficos sin garras en los que cuatro vértices generan un subgráfico con al menos dos aristas.

La mayor parte de su trabajo de clasificación está dedicado al análisis de gráficos antiprismáticos. El gráfico de Schläfli , un gráfico sin garras fuertemente regular con parámetros srg(27,16,10,8), juega un papel importante en esta parte del análisis. Esta teoría estructural ha llevado a nuevos avances en la combinatoria de poliedros y nuevos límites en los números cromáticos de gráficos sin garras [5] , así como nuevos algoritmos de complejidad paramétrica de parámetros fijos para conjuntos dominantes en gráficos sin garras [22] .

Notas

↑ 1 2 Faudree, Flandrin, Ryjaček, 1997 , p. 88.
↑ 1 2 Faudree, Flandrin, Ryjáček, 1997 .
↑ LW Beineke. Beitrage zur Graphentheorie. - Teubner, 1968. - S. 17-33 .
↑ 1 2 Faudree, Flandrin, Ryjaček, 1997 , p. 89.
↑ 1 2 3 4 5 María Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. El teorema del grafo perfecto fuerte. - 2006. - T. 164 , núm. 1 . - S. 51-229 . doi : 10.4007 / annals.2006.164.51 .
↑ 1 2 3 4 Faudree, Flandrin, Ryjáček, 1997 , p. 132.
↑ Alon Itai, Michael Rodeh. Encontrar un circuito mínimo en un gráfico // SIAM Journal on Computing . - 1978. - V. 7 , núm. 4 . - S. 413-423 . -doi : 10.1137/ 0207033 .
↑ Ton Kloks, Dieter Kratsch, Haiko Müller. Encontrar y contar pequeños subgrafos inducidos de manera eficiente // Letras de procesamiento de información. - 2000. - T. 74 , núm. 3-4 . - S. 115-121 . - doi : 10.1016/S0020-0190(00)00047-8 .
↑ Edgar M. Palmer, Ronald C. Read, Robert W. Robinson. Contando gráficos cúbicos sin garras // SIAM Journal on Discrete Mathematics . - 2002. - T. 16 , núm. 1 . - S. 65-73 . -doi : 10.1137/ S0895480194274777 .
↑ David P. Sumner. Gráficos con 1 factor. - 1974. - T. 42 , núm. 1 . - S. 8-12 . -doi : 10.2307/ 2039666 . — .
↑ M. Las Vergnas. Una nota sobre coincidencias en gráficos // Cahiers du Centre d'Études de Recherche Opérationnelle. - 1975. - T. 17 , núm. 2-3-4 . - S. 257-260 .
↑ 1 2 Faudree, Flandrin, Ryjaček, 1997 , p. 120-124.
↑ Marek Chrobak, Joseph Naor, Mark B. Novick. Algoritmos y estructuras de datos : Taller WADS '89, Ottawa, Canadá, agosto de 1989, Actas. - Springer, 1989. - T. 382 . - S. 147-162 . -doi : 10.1007 / 3-540-51542-9_13 .
↑ Jack Edmonds. Caminos, árboles y flores // Canadian J. Math. - 1965. - T. 17 , núm. 0 _ - S. 449-467 . -doi : 10.4153 / CJM-1965-045-4 .
↑ Najiba Sbihi. Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile // Matemáticas discretas. - 1980. - T. 29 , núm. 1 . - S. 53-76 . - doi : 10.1016/0012-365X(90)90287-R .
↑ 1 2 Faudree, Flandrin, Ryjaček, 1997 , p. 133-134.
↑ George J. Minty. Sobre conjuntos independientes máximos de vértices en gráficos sin garras // Journal of Combinatorial Theory. Serie B. - 1980. - T. 28 , núm. 3 . - S. 284-304 . -doi : 10.1016 / 0095-8956(80)90074-X .
↑ Daishin Nakamura, Akihisa Tamura. Una revisión del algoritmo de Minty para encontrar un conjunto estable ponderado máximo de un gráfico sin garras // Revista de la Sociedad de Investigación de Operaciones de Japón. - 2001. - T. 44 , núm. 2 . - S. 194-204 .
↑ Faudree, Flandrin, Ryjáček, 1997 , p. 135-136.
↑ Faudree, Flandrin, Ryjáček, 1997 , p. 124-125.
↑ Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. El conjunto dominante es un parámetro fijo manejable en gráficos sin garras. — 2010.
↑ 1 2 Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen, Gerhard Woeginger. Dominación cuando las estrellas están fuera. — 2010.
↑ María Chudnovsky, Paul Seymour. Encuestas en combinatoria 2005. — Universidad de Cambridge. Prensa, 2005. - T. 327 . - S. 153-171 .

Literatura

Ralph Faudree, Evelyne Flandrin, Zdeněk Ryjáček. Gráficos sin garras: una encuesta // Matemáticas discretas. - 1997. - T. 164 , núm. 1-3 . - S. 87-147 . - doi : 10.1016/S0012-365X(96)00045-3 .

Enlaces

Gráficos sin garras , sistema de información sobre inclusiones de clases de gráficos
Mugan, Jonathan William; WeissteinEric W. Claw-Free Graph (inglés) en el sitio web de Wolfram MathWorld .