En la teoría de grafos , una disciplina matemática, un grafo de factor crítico (o grafo hipomatable [1] [2] ) es un grafo con n vértices en el que cada subgrafo de n - 1 vértices tiene una correspondencia perfecta . (Una coincidencia perfecta en un gráfico es un subconjunto de sus bordes con la propiedad de que cada uno de sus vértices es el punto final de exactamente uno de los bordes del subconjunto).
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/a/a9/Factor_critical.svg/300px-Factor_critical.svg.png)
Una coincidencia que cubre todos los vértices de un gráfico menos uno se denomina coincidencia casi perfecta . De manera equivalente, un gráfico de factor crítico es un gráfico en el que hay coincidencias casi perfectas que evitan todos los vértices posibles.
Ejemplos de
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/b/b1/Friendship_graphs.svg/240px-Friendship_graphs.svg.png)
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/3/38/Gyroelongated_pentagonal_pyramid.png/220px-Gyroelongated_pentagonal_pyramid.png)
Cualquier gráfico de ciclo de longitud impar es factor crítico, [1] al igual que cualquier gráfico completo con un número impar de vértices. [3] De manera más general, cada grafo hamiltoniano con un número impar de vértices es un factor crítico. Las gráficas de amistad (gráficas formadas conectando una colección de triángulos en un solo vértice común) proporcionan ejemplos de gráficas que son factores críticos pero no hamiltonianos.
Si un gráfico G es el factor crítico, entonces también lo es la Mycielskian de G . Por ejemplo, el gráfico de Grötzsch , el Mycielskian de un gráfico de ciclo de cinco vértices, es factor crítico. [4]
Cada gráfico sin garras conectado a 2 vértices con un número impar de vértices es un factor crítico. Por ejemplo, el gráfico de 11 vértices formado al eliminar un vértice del icosaedro regular (el gráfico de la pirámide pentagonal giroelongada ) tiene 2 conexiones y no tiene garras, por lo que es un factor crítico. Este resultado se deriva directamente del teorema más fundamental de que cada grafo sin garras conectado con un número par de vértices tiene una correspondencia perfecta. [5]
Caracterizaciones
Los gráficos de factores críticos pueden caracterizarse de varias formas diferentes, además de su definición como gráficos en los que cada eliminación de vértice permite una coincidencia perfecta:
- Tibor Gallai demostró que un gráfico es factor crítico si y solo si está conectado y, para cada nodo v del gráfico, existe una coincidencia máxima que no incluye v . De estas propiedades se deduce que el gráfico debe tener un número impar de vértices y que cada coincidencia máxima debe coincidir con todos los vértices menos uno. [6]
- László Lovász demostró que un gráfico es factor crítico si y solo si tiene una descomposición de oreja extraña , una partición de sus bordes en una secuencia de subgráficos, cada uno de los cuales es una trayectoria o ciclo de longitud impar , con el primero en la secuencia. siendo un ciclo, cada camino en la secuencia tiene ambos puntos finales pero ningún punto interior en los vértices en los subgrafos anteriores, y cada ciclo que no sea el primero en la secuencia tiene exactamente un vértice en los subgrafos anteriores. Por ejemplo, el gráfico de la ilustración se puede dividir de esta manera en un ciclo de cinco aristas y una trayectoria de tres aristas. En el caso de que también se proporcione una coincidencia casi perfecta del gráfico de factor crítico, la descomposición de la oreja se puede elegir de tal manera que cada oreja alterne entre bordes coincidentes y no coincidentes. [7] [8]
- Un gráfico también es factor crítico si y solo si puede reducirse a un solo vértice mediante una secuencia de contracciones de ciclos de longitud impar. Además, en esta caracterización, es posible elegir cada ciclo de la secuencia para que contenga el vértice formado por la contracción del ciclo anterior. [1] Por ejemplo, si uno contrae las orejas de la descomposición de una oreja, en el orden dado por la descomposición, entonces en el momento en que se contrae cada oreja forma un ciclo impar, por lo que la caracterización de la descomposición de la oreja puede usarse para encontrar una secuencia. de ciclos impares para contraer. A la inversa, a partir de una secuencia de contracciones de ciclo impares, cada una de las cuales contiene el vértice formado a partir de la contracción anterior, se puede formar una descomposición de la oreja en la que las orejas son los conjuntos de bordes contraídos en cada paso.
- Suponga que se da una gráfica G junto con la opción de un vértice v y una M coincidente que cubre todos los vértices excepto v . Entonces G es el factor crítico si y sólo si hay un conjunto de caminos en G , alterna entre los bordes coincidentes y no coincidentes, que Connect v a cada uno de los otros vértices en G . Con base en esta propiedad, es posible determinar en tiempo lineal si un gráfico G con una coincidencia casi perfecta dada es un factor crítico. [9]
Propiedades
Los gráficos de factores críticos siempre deben tener un número impar de vértices y deben estar conectados por 2 bordes (es decir, no pueden tener puentes ). [10] Sin embargo, no están necesariamente conectados por 2 vértices ; los gráficos de amistad proporcionan un contraejemplo. No es posible que un gráfico de factor crítico sea bipartito , porque en un gráfico bipartito con una coincidencia casi perfecta, los únicos vértices que se pueden eliminar para producir un gráfico perfectamente emparejado son los que están en el lado más grande de la bipartición.
Cada gráfico de factor crítico conectado a 2 vértices con m aristas tiene al menos m diferentes coincidencias casi perfectas y, de manera más general, cada gráfico de factor crítico con m aristas y c bloques (componentes conectados a 2 vértices) tiene al menos m - c + 1 emparejamientos casi perfectos diferentes. Los gráficos para los que estos límites son estrechos pueden caracterizarse por tener descomposiciones de oído extrañas de una forma específica. [3]
Cualquier gráfico conectado puede transformarse en un gráfico de factor crítico al contraer una cantidad suficiente de sus bordes. Los conjuntos mínimos de aristas que deben contraerse para hacer que un gráfico determinado sea crítico con el factor G forman las bases de un matroide , un hecho que implica que se puede usar un algoritmo codicioso para encontrar el conjunto de aristas de peso mínimo a contraer para hacer un gráfico factor crítico, en tiempo polinomial . [11]
Aplicaciones
Una flor es un factor crítico subgrafo de un gráfico más grande. Las flores juegan un papel clave en los algoritmos de Jack Edmonds para lograr una correspondencia máxima y una combinación perfecta de peso mínimo en gráficos no bipartitos. [12]
En la combinatoria poliédrica , los gráficos de factores críticos juegan un papel importante en la descripción de las facetas del politopo coincidente de un gráfico dado. [1] [2]
Se dice que una gráfica es crítica para el factor k si cada subconjunto de n - k vértices tiene una coincidencia perfecta. Según esta definición, una gráfica hipomatable es crítica de 1 factor. [13] Incluso de manera más general, un gráfico es ( un , b ) -factor crítico si cada subconjunto de n - k vértices tiene una r -factor, que es, es el conjunto de vértices de un r subgrafo -regular de lo dado grafico.
Un gráfico crítico (sin calificación) se suele suponer a significar un gráfico para el cual la eliminación de cada uno de sus vértices reduce el número de colores que necesita en un colorante gráfico . El concepto de criticidad se ha utilizado de manera mucho más general en la teoría de grafos para referirse a gráficos en los que la eliminación de cada posible vértice cambia o no cambia alguna propiedad relevante del gráfico. Un gráfico de coincidencia crítica es un gráfico para el que 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 gráficos críticos de coincidencia son exactamente los gráficos en los que cada componente conectado tiene un factor crítico. [14] El gráfico de complemento de un gráfico crítico es necesariamente crítico de emparejamiento, un hecho que fue utilizado por Gallai para demostrar límites inferiores en el número de vértices en un gráfico crítico. [15]
Más allá de la teoría de grafos, el concepto de factor-criticidad se ha extendido a las matroides definiendo un tipo de descomposición de la oreja en las matroides y definiendo una matroide como factor crítico si tiene una descomposición de la oreja en la que todos los oídos son impares. [dieciséis]
Referencias
- ^ a b c d Pulleyblank, WR ; Edmonds, J. (1974), "Facets of 1-matching polyhedra", en Berge, C .; Ray-Chaudhuri, DK (eds.), Hypergraph Seminar , Lecture Notes in Mathematics, 411 , Springer-Verlag, págs. 214–242, doi : 10.1007 / BFb0066196 , ISBN 978-3-540-06846-4.
- ^ a b 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.
- ^ a b Liu, Yan; Hao, Jianxiu (2002), "La enumeración de coincidencias casi perfectas de gráficos de factores críticos", Matemáticas discretas , 243 (1-3): 259-266, doi : 10.1016 / S0012-365X (01) 00204-7 , Señor 1874747.
- ^ Došlić, Tomislav (2005), "Mycielskians and matchings" , 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 coincidencia en gráficos 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. Akad. Estera. Kutató Int. Közl. , 8 : 135-139, MR 0166777. Citado por Frank, András ; Szegő, László (2002), "Note on the path-matching formula" (PDF) , Journal of Graph Theory , 41 (2): 110–119, CiteSeerX 10.1.1.20.7918 , doi : 10.1002 / jgt.10055 , MR 1926313.
- ^ Lovász, L. (1972), "Una nota sobre gráficas de factor crítico", Studia Sci. Matemáticas. Hungar. , 7 : 279–280, MR 0335371.
- ^ Korte, Bernhard H .; Vygen, Jens (2008), "10.4 Ear-Decompositions of Factor-Critical Graphs", Optimización combinatoria: teoría y algoritmos , algoritmos y combinatoria, 21 (4ª ed.), Springer-Verlag, págs. 235–241, ISBN 978-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), "Empaquetaduras y cubiertas dobles de trayectoria perfecta de gráficos planos máximos", Matemáticas discretas , 117 (1-3): 183-195, doi : 10.1016 / 0012-365X (93) 90334-P , MR 1226141.
- ^ Szigeti, Zoltán (1996), "Sobre una matroide definida por descomposiciones de grafos en el oído", Combinatorica , 16 (2): 233–241, doi : 10.1007 / BF01844849 , MR 1401896. Para obtener un algoritmo anterior para contraer el número mínimo de bordes (no ponderados) para alcanzar un gráfico de factor crítico, consulte Frank, András (1993), "Ponderaciones conservadoras y descomposiciones auditivas de gráficos", Combinatorica , 13 (1): 65–81, doi : 10.1007 / BF01202790 , MR 1221177.
- ^ Edmonds, Jack (1965), "Senderos, árboles y flores", Canadian Journal of Mathematics , 17 : 449–467, doi : 10.4153 / CJM-1965-045-4 , MR 0177907.
- ^ Favaron, Odile (1996), "On k -factor-critic graphs" , Discussiones Mathematicae Graph Theory , 16 (1): 41–51, doi : 10.7151 / dmgt.1022 , MR 1429805.
- ^ Erdős, P .; Füredi, Z .; Gould, RJ ; Gunderson, DS (1995), "Gráficos extremos para triángulos que se cruzan" , Journal of Combinatorial Theory , Serie B, 64 (1): 89–100, doi : 10.1006 / jctb.1995.1026 , MR 1328293.
- ^ Gallai, T. (1963b), "Kritische Graphen II", Publ. Matemáticas. Inst. Hungar. Acad. Sci. , 8 : 373–395. Citado por Stehlík, Matěj (2003), "Gráficos críticos con complementos conectados", 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 auricular de matroides", Combinatorica , 26 (3): 353–377, doi : 10.1007 / s00493-006-0020-3 , MR 2246153.