Gráfico de factor crítico

Un gráfico de cociente crítico (o gráfico casi coincidente [1] [2] .) es un gráfico con n vértices en el que cada subgráfico con n − 1 vértices tiene una coincidencia perfecta . (Una coincidencia perfecta en un gráfico es un subconjunto de aristas con la propiedad de que cada uno de los vértices del gráfico es el vértice final de exactamente una arista del subconjunto).

Una combinación que cubre todos los vértices excepto uno se llama coincidencia casi perfecta . Por lo tanto, de manera equivalente, un gráfico de cociente crítico es aquel en el que hay coincidencias casi perfectas que no contienen ninguno de los vértices.

Ejemplos

Cualquier ciclo de longitud impar es un factor crítico [1] , como lo es cualquier gráfico completo con un número impar de vértices [3] . De manera más general, cualquier gráfico hamiltoniano con un número impar de vértices es un cociente crítico. Los gráficos de amistad (gráficos formados al conectar un conjunto de triángulos con un vértice común) brindan ejemplos de gráficos que son críticos para los factores pero no hamiltonianos.

Si un gráfico G es cociente crítico, entonces es un mychelskiano de G. Por ejemplo, el gráfico de Grötzsch , el mycelskiano de un ciclo con cinco vértices, es cociente crítico [4] .

Cualquier gráfico sin garras conectado a 2 vértices con un número impar de vértices es un cociente crítico. Por ejemplo, el gráfico de 11 vértices formado por los vértices de un icosaedro regular (el gráfico de una pirámide pentagonal tortuosamente alargada ) es biconexo y sin garras, por lo que es un cociente crítico. Este resultado se deriva directamente del teorema más fundamental de que cualquier gráfico conectado sin garras con un número par de vértices tiene una coincidencia perfecta [5] .

Descripción

Los gráficos de factor crítico se pueden describir de varias maneras diferentes, además de definirse como gráficos cuya eliminación de cualquier vértice permite una coincidencia perfecta:

Propiedades

Los gráficos de factor crítico siempre deben tener un número impar de vértices y deben estar conectados por 2 aristas (es decir, no pueden tener ningún puente ) [10] . Sin embargo, no están necesariamente conectados a 2 vértices . Los gráficos de amistad proporcionan un contraejemplo. Un gráfico de cociente crítico no puede ser bipartito , porque en un gráfico bipartito de coincidencia casi perfecta, los únicos vértices que se pueden eliminar para producir un gráfico perfectamente coincidente están en el lado más grande del gráfico bipartito.

Cualquier gráfico de factor crítico conectado con 2 vértices con m aristas tiene al menos m coincidencias casi perfectas diferentes y, de manera más general, cualquier gráfico de factor crítico con m aristas y c bloques (componentes conectados de 2 vértices) tiene al menos m - c + 1 combinaciones diferentes casi perfectas. Los gráficos para los que estos límites son exactos pueden describirse como que tienen una descomposición de oído de un tipo específico [3] .

Cualquier gráfico conectado se puede transformar en un gráfico de factor crítico contrayendo suficientes bordes. El conjunto mínimo de aristas que deben contraerse para hacer que un gráfico dado sea crítico para el factor G forma una base matroide , el hecho de que un algoritmo codicioso de tiempo polinomial se puede usar para encontrar el conjunto ponderado más pequeño de aristas cuya contracción hace que el gráfico factorice crítico crítico [11] . Un algoritmo temprano para contraer el número mínimo de aristas (no ponderadas) para obtener un gráfico de cociente crítico se puede encontrar en el artículo de Frank [12] .

Aplicaciones

Una flor es un subgrafo crítico de cociente de un gráfico más grande. Las flores juegan un papel clave en los algoritmos de Edmonds para encontrar la coincidencia más grande y la coincidencia perfecta ponderada mínima en gráficos no bipartitos [13] .

En la combinatoria de poliedros, los gráficos de cociente crítico juegan un papel importante en la descripción de facetas de politopos coincidentes de un gráfico dado [1] [2] .

Generalizaciones y conceptos relacionados

Se dice que un gráfico es k -factor crítico si cualquier subconjunto de n − k vértices tiene una coincidencia perfecta. Con esta definición, un gráfico casi compatible (en:hipomatchable) es crítico de 1 factor [14] . Aún más generalmente, un gráfico es ( a , b ) -factor crítico si cualquier subconjunto de n − k vértices tiene un factor r , es decir, es el conjunto de vértices de un r - subgráfico regular del gráfico dado.

Cuando las personas hablan de un gráfico crítico (sin k- ), por lo general se refieren a un gráfico cuya eliminación de cualquier vértice conduce a una disminución en la cantidad de colores necesarios para colorear el gráfico . El concepto de criticidad se usa mucho más ampliamente en la teoría de grafos para grafos en los que la eliminación de cualquier vértice cambia alguna propiedad del gráfico. Un gráfico de combinación crítica es un gráfico para el cual la eliminación de cualquier vértice no cambia el tamaño de la coincidencia más grande . Según Gallai, los gráficos de combinación crítica son precisamente gráficos en los que cualquier componente conexa es cociente crítico [15] . El complemento de un grafo crítico es necesariamente crítico de combinación, un hecho utilizado por Gallai para demostrar un límite inferior en el número de vértices de un grafo crítico [16] .


Fuera de la teoría de grafos, el concepto de criticidad de los factores tiene una extensión a las matroides al definir el tipo de descomposición del oído en las matroides. Un matroid es un factor crítico si tiene una descomposición del oído en el que todos los oídos son impares [17] .

Notas

  1. ↑ 1 2 3 4 Pulleyblank, Edmonds, 1974 , p. 214–242.
  2. ↑ 1 2 Cornuejols, Pulleyblank, 1983 , p. 35–52.
  3. ↑ 12 Liu , Hao, 2002 , pág. 259–266.
  4. ↑ Došlić, 2005 , pág. 261–266.
  5. ↑ Favaron, Flandrin, Ryjáček, 1997 , p. 271–278.
  6. ↑ Gallai, 1963 , pág. 135–139.
  7. ↑ Lovász, 1972 , pág. 279–280.
  8. ↑ Korte, Vygen, 2008 , pág. 235–241.
  9. ↑ Lou, Rao, 2004 , pág. 51–56.
  10. ↑ Seyffarth, 1993 , pág. 183–195.
  11. ↑ Szigeti, 1996 , pág. 233–241.
  12. ↑ Frank, 1993 , pág. 65–81.
  13. ↑ Edmonds, 1965 , pág. 449–467.
  14. ↑ Favarón, 1996 , p. 41–51.
  15. ↑ Erdős, Furedi, Gould, Gunderson, 1995 , p. 89–100.
  16. ↑ Gallai, 1963b , pág. 373–395.
  17. ↑ Szegedy, Szegedy, 2006 , pág. 353–377.

Literatura