Gráfica de n vértices con una correspondencia perfecta para cada subgráfica de n-1 vértices
Un gráfico factorialmente crítico, junto con correspondencias perfectas de los subgráficos formados al eliminar uno de sus vértices.
En teoría de grafos , una disciplina matemática, un grafo factor-crítico (o grafo hipoemparejable [1] [2] ) es un grafo con n vértices en el que cada subgrafo inducido de n − 1 vértices tiene una correspondencia perfecta . (Una correspondencia perfecta en un grafo es un subconjunto de sus aristas con la propiedad de que cada uno de sus vértices es el punto final de exactamente una de las aristas del subconjunto).
Una coincidencia que cubre todos los vértices de un grafo excepto uno se denomina coincidencia casi perfecta . Por lo tanto, un grafo de factor crítico es un grafo en el que hay coincidencias casi perfectas que evitan todos los vértices posibles.
Cualquier gráfico de ciclo de longitud impar es factor crítico, [1] como lo es cualquier gráfico completo con un número impar de vértices. [3] En términos más generales, todo gráfico hamiltoniano con un número impar de vértices es factor crítico. Los gráficos de amistad (gráficos formados al conectar una colección de triángulos en un único vértice común) proporcionan ejemplos de gráficos que son factor críticos pero no hamiltonianos.
Si un grafo G es factor-crítico, entonces también lo es el Mycielskiano de G . Por ejemplo, el grafo de Grötzsch , el Mycielskiano de un ciclo-grafo de cinco vértices, es factor-crítico. [4]
Todo grafo con 2 vértices conexos y sin garras con un número impar de vértices es factor crítico. Por ejemplo, el grafo de 11 vértices formado al eliminar un vértice del icosaedro regular (el grafo de la pirámide pentagonal giroelongada ) es a la vez 2-conexo y sin garras, por lo que es factor crítico. Este resultado se desprende directamente del teorema más fundamental de que todo grafo conexo sin garras con un número par de vértices tiene una correspondencia perfecta. [5]
Caracterizaciones
Los gráficos factor-críticos se pueden caracterizar de varias maneras diferentes, además de su definición como gráficos en los que cada eliminación de vértice permite una correspondencia perfecta:
Tibor Gallai demostró que un grafo es factor-crítico si y sólo si es conexo y, para cada nodo v del grafo, existe una correspondencia máxima que no incluye a v . De estas propiedades se deduce que el grafo debe tener un número impar de vértices y que cada correspondencia máxima debe coincidir con todos los vértices menos uno. [6]
László Lovász demostró que un grafo es factor-crítico si y solo si tiene una descomposición en orejas impares , una partición de sus aristas en una secuencia de subgrafos, cada uno de los cuales es un camino o ciclo de longitud impar , siendo el primero en la secuencia un ciclo, cada camino en la secuencia tiene ambos puntos finales pero ningún punto interior en vértices en subgrafos anteriores, y cada ciclo distinto del primero en la secuencia tiene exactamente un vértice en subgrafos anteriores. Por ejemplo, el grafo en la ilustración puede ser particionado de esta manera en un ciclo de cinco aristas y un camino de tres aristas. En el caso de que también se dé una coincidencia casi perfecta del grafo factor-crítico, la descomposición en orejas puede ser elegida de tal manera que cada oreja alterne entre aristas coincidentes y no coincidentes. [7] [8]
Un grafo también es factor-crítico si y solo si puede ser reducido a un único vértice por una secuencia de contracciones de ciclos de longitud impar. Además, en esta caracterización, es posible elegir cada ciclo en la secuencia de modo que contenga el vértice formado por la contracción del ciclo anterior. [1] Por ejemplo, si uno contrae las orejas de una descomposición en orejas, en el orden dado por la descomposición, entonces en el momento en que cada oreja se contrae forma un ciclo impar, por lo que la caracterización de descomposición en orejas puede usarse para encontrar una secuencia de ciclos impares para contraer. A la inversa, a partir de una secuencia de contracciones de ciclos impares, cada una conteniendo el vértice formado a partir de la contracción anterior, uno puede formar una descomposición en orejas en la que las orejas son los conjuntos de aristas contraídas en cada paso.
Supongamos que se proporciona un grafo G junto con una elección de un vértice v y un M coincidente que cubre todos los vértices distintos de v . Entonces G es factor-crítico si y solo si hay un conjunto de caminos en G , alternando entre aristas coincidentes y no coincidentes, que conectan v con cada uno de los otros vértices en G . Con base en esta propiedad, es posible determinar en tiempo lineal si un grafo G con una coincidencia casi perfecta dada es factor-crítico. [9]
Propiedades
Los grafos factor-críticos 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 por 2 vértices ; los grafos de amistad proporcionan un contraejemplo. No es posible que un grafo factor-crítico sea bipartito , porque en un grafo bipartito con una coincidencia casi perfecta, los únicos vértices que se pueden eliminar para producir un grafo perfectamente coincidente son los del lado más grande de la bipartición.
Todo grafo factor-crítico con 2 vértices conectados y m aristas tiene al menos m emparejamientos casi perfectos diferentes y, de manera más general, todo grafo factor-crítico con m aristas y c bloques (componentes conectados por 2 vértices) tiene al menos m − c + 1 emparejamientos casi perfectos diferentes. Los grafos para los cuales estos límites son estrictos pueden caracterizarse por tener descomposiciones de orejas impares de una forma específica. [3]
Cualquier grafo conectado puede transformarse en un grafo factor-crítico contrayendo una cantidad suficiente de sus aristas. Los conjuntos mínimos de aristas que deben contraerse para hacer que un grafo G dado sea factor-crítico forman las bases de un matroide , un hecho que implica que se puede utilizar un algoritmo voraz para encontrar el conjunto de peso mínimo de aristas que se deben contraer para hacer que un grafo sea factor-crítico, en tiempo polinomial . [11]
Aplicaciones
Una flor es un subgrafo factorialmente crítico de un grafo mayor. Las flores desempeñan un papel clave en los algoritmos de Jack Edmonds para la correspondencia perfecta de peso mínimo y correspondencia máxima en grafos no bipartitos. [12]
Se dice que un grafo es k -factor-crítico si cada subconjunto de n − k vértices tiene una correspondencia perfecta. Bajo esta definición, un grafo hipoemparejable es 1-factor-crítico. [13] Incluso de manera más general, un grafo es ( a , b ) -factor-crítico si cada subconjunto de n − k vértices tiene un r -factor, es decir, es el conjunto de vértices de un subgrafo r -regular del grafo dado.
Por lo general, se supone que un grafo crítico (sin calificación) significa un grafo para el cual la eliminación de cada uno de sus vértices reduce el número de colores que necesita en una coloración de grafo . El concepto de criticidad se ha utilizado de forma mucho más general en la teoría de grafos para referirse a grafos para los cuales la eliminación de cada vértice posible cambia o no cambia alguna propiedad relevante del grafo. Un grafo de coincidencia crítica es un grafo para el cual la eliminación de cualquier vértice no cambia el tamaño de una coincidencia máxima ; según la caracterización de Gallai, los grafos de coincidencia crítica son exactamente los grafos en los que cada componente conectado es factor-crítico. [14] El grafo complementario de un grafo crítico es necesariamente de coincidencia crítica, un hecho que fue utilizado por Gallai para demostrar límites inferiores en el número de vértices en un grafo crítico. [15]
Más allá de la teoría de grafos, el concepto de criticidad de factores se ha extendido a los matroides definiendo un tipo de descomposición de orejas en los matroides y definiendo que un matroide es factor-crítico si tiene una descomposición de orejas en la que todas las orejas son impares. [16]
^ ab Cornuéjols, G. ; Pulleyblank, WR (1983), "Gráficos críticos, emparejamientos y recorridos o una jerarquía de relajaciones para el problema del viajante de comercio", Combinatorica , 3 (1): 35–52, doi :10.1007/BF02579340, MR 0716420, S2CID 35825797.
^ ab Liu, Yan; Hao, Jianxiu (2002), "La enumeración de emparejamientos casi perfectos de gráficos de factor crítico", Discrete Mathematics , 243 (1–3): 259–266, doi :10.1016/S0012-365X(01)00204-7, MR 1874747.
^ Došlić, Tomislav (2005), "Mycielskianos y emparejamientos", Discussiones Mathematicae Graph Theory , 25 (3): 261–266, doi : 10.7151/dmgt.1279 , MR 2232992.
^ Favaron, Odile ; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Factor-criticidad y extensión de emparejamiento en grafos DCT", Discussiones Mathematicae Graph Theory , 17 (2): 271–278, CiteSeerX 10.1.1.25.6314 , doi :10.7151/dmgt.1054, MR 1627955 .
^ Gallai, T. (1963), "Neuer Beweis eines Tutte'schen Satzes", Magyar Tud. Akád. Estera. Aeropuerto Internacional de Kutató. Kozl. , 8 : 135–139, SEÑOR 0166777. Según lo citado por Frank, András ; Szegő, László (2002), "Nota sobre la fórmula de coincidencia de rutas" (PDF) , Journal of Graph Theory , 41 (2): 110–119, CiteSeerX 10.1.1.20.7918 , doi :10.1002/jgt.10055, MR 1926313, S2CID 206076722 .
^ Lovász, L. (1972), "Una nota sobre gráficos de factores críticos", Studia Sci. Matemáticas. Hungría. , 7 : 279–280, SEÑOR 0335371.
^ Korte, Bernhard H. ; Vygen, Jens (2008), "10.4 Descomposiciones de orejas de grafos de factor crítico", Optimización combinatoria: teoría y algoritmos, Algoritmos y combinatoria, vol. 21 (4.ª ed.), Springer-Verlag, págs. 235–241, ISBN978-3-540-71843-7.
^ Lou, Dingjun; Rao, Dongning (2004), "Caracterización de gráficos críticos de factores y un algoritmo" (PDF) , The Australasian Journal of Combinatorics , 30 : 51–56, MR 2080453.
^ Seyffarth, Karen (1993), "Empaquetamientos y dobles recubrimientos de trayectorias perfectas de grafos planos maximalistas", Discrete Mathematics , 117 (1–3): 183–195, doi : 10.1016/0012-365X(93)90334-P , MR 1226141.
^ Szigeti, Zoltán (1996), "Sobre un matroide definido por descomposiciones de grafos en orejas", Combinatorica , 16 (2): 233–241, doi :10.1007/BF01844849, MR 1401896, S2CID 206806006. Para un algoritmo anterior para contraer el número mínimo de aristas (no ponderadas) para alcanzar un grafo de factor crítico, véase Frank, András (1993), "Conservative weightings and ear-decompositions of graphs", Combinatorica , 13 (1): 65–81, doi :10.1007/BF01202790, MR 1221177, S2CID 10857300.
^ Gallai, T. (1963b), "Kritische Graphen II", Publ. Matemáticas. Inst. Hungría. Acad. Ciencia. , 8 : 373–395. Según cita Stehlík, Matěj (2003), "Grafos críticos con complementos conexos", Journal of Combinatorial Theory , Serie B, 89 (2): 189–194, doi :10.1016/S0095-8956(03)00069-8, MR 2017723.
^ Szegedy, Balázs ; Szegedy, Christian (2006), "Espacios simplécticos y descomposición en orejas de matroides", Combinatorica , 26 (3): 353–377, doi :10.1007/s00493-006-0020-3, MR 2246153, S2CID 11578490.
