Partición oblicua

Una partición sesgada de un grafo es una partición de sus vértices en dos subconjuntos en forma de subgrafo y complemento generado desconectado ; juega un papel importante en la teoría de grafos perfectos .

Definición

Una partición sesgada de un gráfico es una partición de los vértices del gráfico en dos subconjuntos y , para los cuales el subgráfico generado es desconectado, y el subgráfico generado es el complemento de un gráfico desconectado (en lo sucesivo, "coconectado"). . Una partición sesgada equivalente de un gráfico se puede describir como una partición de los vértices del gráfico en cuatro subconjuntos , y , en los que no hay bordes desde hasta , pero hay todos los bordes posibles desde hasta . Para una partición de este tipo, los subgrafos generados están tanto desconectados como coconectados, respectivamente, por lo que podemos tomar y . $GRAMO$ $X$ $Y$ ${\ estilo de visualización G [X]}$ ${\ estilo de visualización G [Y]}$ $GRAMO$ $GRAMO$ $A$ $B$ $C$ $D$ $A$ $B$ $C$ $D$ $G[A\taza B]$ $G[C\taza D]$ $X=A\taza B$ $Y=C\taza D$

Ejemplos

Cualquier camino con cuatro o más vértices tiene una partición oblicua, en la que el conjunto co-desconectado es uno de los bordes internos del camino, y el conjunto desconectado consta de ambos vértices de este borde. Sin embargo, no es posible que los ciclos de cualquier longitud tengan una partición sesgada; no importa qué subconjuntos de ciclos se elijan como conjunto , el complemento del conjunto tendrá el mismo número de componentes conectados, por lo que es imposible descomponer y estar co-desconectado. $Y$ $X$ $X$ $Y$ $X$ $Y$

Si el gráfico tiene una partición sesgada, tiene esa partición y su complemento . Por ejemplo, los complementos de ruta tienen particiones sesgadas, pero los complementos de ciclo no.

Ocasiones especiales

Si el grafo es desconectado, entonces, excepto en tres casos simples (un grafo vacío, un grafo con una arista y tres vértices, o una coincidencia perfecta en cuatro vértices), tiene una partición sesgada, en la que el lado co-desconectado de la partición consta de los extremos de un borde y el lado desconectado consta de todos los demás vértices. Por la misma razón, si el complemento de un grafo es desconectado, entonces, excepto por el correspondiente conjunto de tres casos, debe tener una partición sesgada [1] .

Si el gráfico tiene un separador clique (un clique cuya eliminación hace que los vértices restantes se desconecten) con más de un vértice, la partición en un clique y los vértices restantes forman una partición sesgada. Una sección clique con un vértice es una bisagra . Si tal vértice existe, entonces, con algunas excepciones simples, existe una partición sesgada en la que el lado co-desconectado consiste en este vértice y uno de sus vecinos [1] .

Una sección de estrella en un gráfico es un separador de vértices en el que uno de los vértices es adyacente a todos los demás vértices del separador. Cualquier separador de clics es una sección de estrella. Necesariamente, un grafo con sección en estrella (con más de un vértice) tiene una partición sesgada, en la que el subgrafo co-desconectado consta de los vértices de la sección en estrella, y el subgrafo desconectado consta de todos los vértices restantes [1] . $GRAMO$

Un módulo (o conjunto homogéneo) es un subconjunto no trivial de los vértices del gráfico , tal que para cualquier vértice que no pertenezca a , es adyacente a todos los vértices de , o ninguno de ellos. Si el grafo tiene un módulo y fuera de él hay vértices adyacentes a todos los vértices y otros vértices fuera de él no son adyacentes a ningún vértice de , entonces tiene una sección en estrella que consta de un vértice en el módulo junto con sus vecinos fuera del módulo. Por otro lado, si hay un módulo en el que uno de estos dos subconjuntos está vacío, entonces el gráfico está desconectado o co-desconectado, y nuevamente (excepto en tres casos simples) tiene una sección sesgada [1] . $H$ $GRAMO$ $v$ $H$ $v$ $H$ $GRAMO$ $H$ $H$ $H$ $GRAMO$

Historia

Las particiones sesgadas fueron introducidas por Khvatal [2] en relación con los gráficos perfectos . Chvatal demostró que un gráfico mínimamente imperfecto no puede tener una sección de estrella. Está claro que los gráficos desconectados no pueden ser mínimamente imperfectos, y también se sabía que los gráficos con separadores de clique o módulos no pueden ser mínimamente imperfectos [3] . Claudy Berge conjeturó a principios de la década de 1960 que los gráficos perfectos deben ser lo mismo que los gráficos de Berge, gráficos sin un ciclo impar generado (de longitud cinco o más) o su complemento, y (debido a que los ciclos y sus complementos no tienen particiones sesgadas) ningún gráfico ese no es un gráfico de Berge mínimo puede tener una partición sesgada. Interesado en estos resultados, Chvatal conjeturó que ningún gráfico mínimamente imperfecto puede tener una partición sesgada. Algunos autores han probado casos especiales de esta conjetura, pero ha permanecido sin resolver durante mucho tiempo [4] .

Las particiones sesgadas adquirieron particular importancia cuando fueron utilizadas por Chudnovskaya, Robertson, Seymour y Thomas [5] para probar el teorema del gráfico perfecto fuerte de que los gráficos de Berge son lo mismo que los gráficos perfectos. Chudnovskaya y su grupo no pudieron probar la conjetura de Khvatal directamente, pero probaron un resultado más débil, que el contraejemplo mínimo del teorema (si hubiera uno) tendría que tener una partición sesgada balanceada en la que cada camino generado con un final en un lado del tabique y vértices interiores del otro lado tiene una longitud uniforme. Este resultado se convirtió en el lema clave en su prueba, y la versión completa del lema de Chvatala se deriva de su teorema [6] .

En teoría estructural de grafos

Las particiones sesgadas forman un componente clave de la descomposición estructural de grafos perfectos, que fue utilizado por Chudnovskaya, Robertson, Seymour y Thomas [5] como parte de la prueba del teorema del grafo perfecto fuerte. Chudnovskaya et al demostraron que cualquier gráfico perfecto pertenece a cinco clases básicas de gráficos perfectos o tiene uno de los cuatro tipos de descomposición en gráficos más simples, y una de estas descomposiciones es una descomposición sesgada.

Seymour [6] dio un ejemplo simple de descomposición estructural utilizando particiones oblicuas . Observó que cualquier gráfico de comparabilidad es completo o bipartito o tiene una partición sesgada. De hecho, si cualquier elemento de un conjunto parcialmente ordenado es un elemento mínimo o un elemento máximo, entonces el gráfico de comparabilidad correspondiente es bipartito. Si el pedido está completo , entonces el gráfico de comparabilidad correspondiente está completo. Si ninguno de estos casos tiene lugar, pero cualquier elemento que no es mínimo ni máximo es comparable con todos los demás elementos, entonces la partición en elementos mínimos y no mínimos (si hay más de un elemento mínimo), o la partición en los elementos máximos y no máximos (si hay más de un elemento máximo) forman la sección estelar. En el caso restante, hay un elemento de orden parcial que no es ni mínimo ni máximo y no es comparable con todos los demás elementos. En este caso, hay una partición sesgada (complemento de la sección en estrella) en la que el lado co-desconectado consta de elementos comparables a (sin incluirse a sí mismo ), y el lado desconectado consta de los elementos restantes. $X$ $X$ $X$

Los gráficos de cuerdas tienen descomposiciones aún más simples de un tipo similar: son completos o tienen un separador de clique. Hayward [7] mostró de manera similar que cualquier grafo cordal débil conectado y co-conectado (un grafo con un ciclo generado de longitud mayor que cuatro o su complemento) con cuatro o más vértices tiene una sección en estrella o su complemento, de donde, por el lema de Chvatala , se deduce que cualquier gráfico de este tipo es perfecto.

Algoritmos y complejidad

Una partición sesgada de un gráfico dado, si existe, se puede encontrar en tiempo polinomial . Esto fue mostrado originalmente por Figueiredo, Klein, Kohayakawa y Reid [8] , pero con un tiempo de ejecución muy largo , donde es el número de vértices en el gráfico de entrada. Kennedy y Reid [9] mejoraron el tiempo de ejecución a . Aquí está el número de aristas. ${\ estilo de visualización O (n ^ {101})}$ $norte$ $O(n^{4}m)$ $metro$

El problema de comprobar si un grafo contiene una partición sesgada en la que una de las partes del lado co-desconectado es independiente es un problema NP-completo [10] . Verificar si un gráfico dado contiene una partición sesgada balanceada también es NP-completo para gráficos arbitrarios, pero el problema se puede resolver en tiempo polinomial para gráficos perfectos [11] .

Notas

↑ 1 2 3 4 Caña, 2008 .
↑ Chavatal, 1985 .
↑ Caña (2008 ). La inexistencia de módulos en grafos mínimos imperfectos fue utilizada por Lovas Lovász (1972 ) en su demostración del teorema del grafo perfecto débil .
↑ Véase Cornuéjols, Reed (1993 ) para el caso en que el lado co-desconectado del tabique consta de varias partes, y Roussel, Rubio (2001 ) para el caso en que una de las dos partes del lado co-desconectado es independiente.
↑ 1 2 Chudnovsky, Robertson, Seymour, Thomas, 2006 .
↑ 12 Seymour , 2006 .
↑ Hayward, 1985 .
↑ de Figueiredo, Klein, Kohayakawa, Reed, 2000 .
↑ Kennedy, Reed, 2008 .
↑ Dantas, de Figueiredo, Klein, Gravier, Reed, 2004 .
↑ Trotiñon, 2008 .

Literatura

María Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. El teorema del gráfico perfecto fuerte // Annals of Mathematics . - 2006. - T. 164 , núm. 1 . — S. 51–229 . doi : 10.4007 / annals.2006.164.51 . -arXiv : matemáticas / 0212070 .
Chvátal V. Star-cutsets y gráficos perfectos // Journal of Combinatorial Theory . - 1985. - T. 39 , núm. 3 . — S. 189–199 . - doi : 10.1016/0095-8956(85)90049-8 .
Gerard Cornuejols, Bruce Reed. Cutsets multipartitos completos en gráficos imperfectos mínimos // Journal of Combinatorial Theory . - 1993. - T. 59 , núm. 2 . — S. 191–198 . -doi : 10.1006/ jctb.1993.1065 .
Simone Dantas, Celina MH de Figueiredo, Sulamita Klein, Sylvain Gravier, Bruce Reed. Problema de partición sesgada estable // Matemática aplicada discreta. - 2004. - T. 143 , núm. 1-3 . — P. 17–22 . -doi : 10.1016/ j.dam.2004.01.001 .
Celina MH de Figueiredo, Sulamita Klein, Yoshiharu Kohayakawa, Bruce Reed. Encontrar particiones sesgadas de manera eficiente // Journal of Algorithms. - 2000. - T. 37 , núm. 2 . — S. 505–521 . -doi : 10.1006/ jagm.1999.1122 .
Ryan B. Hayward. Gráficos débilmente triangulados // Journal of Combinatorial Theory . - 1985. - T. 39 , núm. 3 . — S. 200–208 . - doi : 10.1016/0095-8956(85)90050-4 .
William S. Kennedy, Bruce Reed. Reconocimiento rápido de particiones sesgadas // Geometría computacional y teoría de grafos: Conferencia internacional, KyotoCGGT 2007, Kyoto, Japón, 11 al 15 de junio de 2007, Documentos seleccionados revisados. - Berlín: Springer, 2008. - T. 4535. - S. 101-107. — ( Apuntes de clase en informática ). -doi : 10.1007 / 978-3-540-89550-3_11 .
Laszlo Lovasz . Hipergrafías normales y la conjetura del grafo perfecto // Matemáticas discretas . - 1972. - Vol. 2 , núm. 3 . — S. 253–267 . - doi : 10.1016/0012-365X(72)90006-4 .
bruce caña Particiones sesgadas en gráficas perfectas // Matemática aplicada discreta. - 2008. - T. 156 , núm. 7 . - S. 1150-1156 . -doi : 10.1016/ j.dam.2007.05.054 . Archivado desde el original el 19 de septiembre de 2015.
Roussel F., Rubio P. Acerca de las particiones sesgadas en gráficos mínimos imperfectos // Journal of Combinatorial Theory . - 2001. - T. 83 , núm. 2 . — S. 171–190 . -doi : 10.1006/ jctb.2001.2044 .
Pablo Seymour. Cómo se encontró la prueba de la conjetura del grafo perfecto fuerte // Gazette des Mathématiciens. - 2006. - Edición. 109 . — págs. 69–83 .
Nicolás Trotignon. Descomposición de gráficos de Berge y detección de particiones sesgadas equilibradas // Journal of Combinatorial Theory . - 2008. - T. 98 , núm. 1 . — S. 173–225 . -doi : 10.1016/ j.jctb.2007.07.004 . .