En la teoría de grafos , una partición sesgada de un grafo es una partición de sus vértices en dos subconjuntos, de modo que el subgrafo inducido formado por uno de los dos subconjuntos está desconectado y el subgrafo inducido formado por el otro subconjunto es el complemento de un grafo desconectado. . Las particiones sesgadas juegan un papel importante en la teoría de gráficos perfectos .
Definición
Una partición sesgada de un gráfico es una partición de sus vértices en dos subconjuntos y para el cual el subgrafo inducido se desconecta y el subgrafo inducido es el complemento de un gráfico desconectado (co-desconectado). De manera equivalente, una partición sesgada de un gráfico puede describirse mediante una partición de los vértices de en cuatro subconjuntos , , , y , de modo que no haya bordes de a y tal que todos los posibles bordes de a existe; para tal partición, los subgrafos inducidos y están desconectados y co-desconectados respectivamente, por lo que podemos tomar y .
Ejemplos de
Cada gráfico de ruta con cuatro o más vértices tiene una partición sesgada, en la que el conjunto co-desconectado es uno de los bordes interiores del camino y el conjunto desconectado consta de los vértices a cada lado de este borde. Sin embargo, no es posible que un gráfico de ciclo de cualquier longitud tenga una partición sesgada: no importa qué subconjuntos del ciclo se elijan como conjunto, el conjunto complementario tendrá el mismo número de componentes conectados, por lo que no es posible estar desconectado y ser co-desconectado.
Si una gráfica tiene una partición sesgada, también la tiene su complemento . Por ejemplo, los complementos de los gráficos de ruta tienen particiones sesgadas y los complementos de los gráficos de ciclos no.
Casos especiales
Si una gráfica está desconectada en sí misma, entonces con solo tres simples excepciones (una gráfica vacía , una gráfica con un borde y tres vértices, o una coincidencia perfecta de cuatro vértices ) tiene una partición sesgada, en la que el lado co-desconectado de la la partición consta de los puntos finales de un solo borde y el lado desconectado consta de todos los demás vértices. Por la misma razón, si el complemento de un gráfico está desconectado, entonces, con un conjunto correspondiente de tres excepciones, debe tener una partición sesgada. [1]
Si un gráfico tiene un separador de clique (un clique cuya eliminación desconectaría los vértices restantes) con más de un vértice, entonces la partición en el clique y los vértices restantes forman una partición sesgada. Un corte de camarilla con un vértice es un punto de articulación ; si tal vértice existe, entonces, con un pequeño número de excepciones simples, hay una partición sesgada en la que el lado co-desconectado consiste en este vértice y uno de sus vecinos. [1]
Un corte de estrella en un gráficoes un separador de vértices en el que uno de los vértices del separador es adyacente a todos los demás. Cada separador de camarillas es un conjunto de estrellas. Necesariamente, un gráfico con un corte en estrella (con más de un vértice) tiene una partición sesgada en la que el subgrafo co-desconectado consiste en los vértices en el corte en estrella y el subgrafo desconectado consiste en todos los vértices restantes. [1]
Un módulo (o conjunto homogéneo) es un subconjunto no trivial de los vértices de tal que, por cada vértice eso no esta en , ya sea es adyacente a todos los vértices en oa ninguno de ellos. Si un gráfico tiene un modulo y, fuera de él, existen ambos vértices adyacentes a todos los vértices en y otros vértices adyacentes a ninguno de ellos, entonces tiene un corte en estrella que consta de un vértice en el módulo junto con sus vecinos fuera del módulo. Por otro lado, si existe un módulo en el que uno de estos dos subconjuntos está vacío, entonces el gráfico se desconecta o co-desconecta y nuevamente (con las tres simples excepciones) tiene un corte sesgado. [1]
Historia
Las particiones sesgadas fueron introducidas por Chvátal (1985) , en conexión con gráficos perfectos . Chvátal demostró que un gráfico mínimamente imperfecto no puede tener un corte de estrellas. Trivialmente, 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 podían ser mínimamente imperfectos. [2] Claude Berge había conjeturado a principios de la década de 1960 que los gráficos perfectos eran los mismos que los gráficos de Berge, gráficos sin ciclo impar inducido (de longitud cinco o más) o su complemento, y (debido a que los ciclos y sus complementos no tienen sesgo particiones) ningún gráfico mínimo que no sea de Berge puede tener una partición sesgada. Motivado por estos resultados, Chvátal conjeturó que ningún gráfico mínimamente imperfecto podría tener una partición sesgada. Varios autores probaron casos especiales de esta conjetura, pero permaneció sin resolver durante muchos años. [3]
Las particiones sesgadas cobraron importancia cuando fueron utilizadas por Chudnovsky et al. (2006) para demostrar el fuerte teorema de la gráfica perfecta de que las gráficas de Berge son, de hecho, las mismas que las gráficas perfectas. Chudnovsky y col. fueron incapaces de probar la conjetura de Chvátal directamente, sino que demostraron un resultado más débil, que un contraejemplo mínimo del teorema (si existiera) no podría tener una partición sesgada equilibrada, una partición sesgada en la que cada camino inducido con puntos finales en un lado del La partición y los vértices interiores del otro lado tienen una longitud uniforme. Este resultado formó un lema clave en su demostración, y la versión completa del lema de Chvátal se deriva de su teorema. [4]
En teoría de grafos estructurales
Las particiones sesgadas forman uno de los componentes clave de una descomposición estructural de gráficos perfectos utilizada por Chudnovsky et al. (2006) como parte de su demostración del teorema del grafo perfecto fuerte. Chudnovsky y col. mostró que cada gráfico perfecto pertenece a una de las cinco clases básicas de gráficos perfectos, o tiene uno de los cuatro tipos de descomposición en gráficos más simples, uno de los cuales es una partición sesgada.
Seymour (2006) da un ejemplo más simple de una descomposición estructural usando particiones sesgadas . Observa que cada gráfico de comparabilidad está completo , es bipartito o tiene una partición sesgada. Porque, si cada 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 es un pedido total , entonces el gráfico de comparabilidad correspondiente está completo. Si no surge ninguno de estos dos casos, pero cada elemento que no es ni mínimo ni máximo es comparable a todos los demás elementos, entonces la partición en los 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 un conjunto de estrellas. Y en el caso restante, existe un elementodel orden parcial que no es mínimo, no máximo y no comparable con todos los demás elementos; en este caso, hay una partición oblicua (el complemento de un corte en estrella) en la que el lado co-desconectado consta de los elementos comparables a (No incluído sí mismo) y el lado desconectado consta de los elementos restantes.
Los gráficos cordales tienen una descomposición aún más simple de un tipo similar: o están completos o tienen un separador de camarillas. Hayward (1985) mostró, de manera análoga, que todo grafo débilmente cordal conectado y coconectado (un grafo sin ciclo inducido o su complemento de longitud mayor de cuatro) con cuatro o más vértices tiene un corte de estrella o su complemento, a partir del cual sigue el lema de Chvátal de que cada 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 demostrado originalmente por de Figueiredo et al. (2000) pero con un tiempo de ejecución imprácticamente grande de, dónde es el número de vértices en el gráfico de entrada. Kennedy y Reed (2008) mejoraron el tiempo de ejecución para; aquí es el número de bordes de entrada.
Es NP-completo probar si un gráfico contiene una partición sesgada en la que una de las partes del lado co-desconectado es independiente. [5] Probar si un gráfico dado contiene una partición sesgada equilibrada también es NP-completo en gráficos arbitrarios, pero puede resolverse en tiempo polinómico en gráficos perfectos. [6]
Notas
- ↑ a b c d Reed (2008) .
- ^ Reed (2008) . Lovász (1972) utilizó la inexistencia de módulos en grafos mínimamente imperfectosen su demostración del teorema del grafo perfecto débil .
- ↑ Ver Cornuéjols & Reed (1993) para el caso en el que el lado co-desconectado de la partición es multipartito, y Roussel & Rubio (2001) para el caso en el que una de las dos partes del lado co-desconectado es independiente.
- ^ Seymour (2006) .
- ^ Dantas y col. (2004) .
- ^ Trotignon (2008) .
Referencias
- Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2006), "El teorema del gráfico fuerte perfecto" , Annals of Mathematics , 164 (1): 51-229, arXiv : math / 0212070 , doi : 10.4007 / annals.2006.164.51.
- Chvátal, V. (1985), "Star-cutsets and perfect graphs", Journal of Combinatorial Theory , Serie B, 39 (3): 189-199, doi : 10.1016 / 0095-8956 (85) 90049-8 , MR 0815391.
- Cornuéjols, G .; Reed, B. (1993), "Cortes completos de múltiples partes en gráficos mínimos imperfectos", Journal of Combinatorial Theory , Serie B, 59 (2): 191-198, doi : 10.1006 / jctb.1993.1065 , MR 1244930.
- Dantas, Simone; de Figueiredo, Celina MH; Klein, Sulamita; Gravier, Sylvain; Reed, Bruce A. (2004), "Problema de partición sesgada estable", Matemáticas aplicadas discretas , 143 (1-3): 17-22, doi : 10.1016 / j.dam.2004.01.001 , MR 2087864.
- de Figueiredo, Celina MH; Klein, Sulamita; Kohayakawa, Yoshiharu ; Reed, Bruce A. (2000), "Encontrar particiones sesgadas de manera eficiente", Journal of Algorithms , 37 (2): 505–521, doi : 10.1006 / jagm.1999.1122 , MR 1788847.
- Hayward, Ryan B. (1985), "Gráficos débilmente triangulados", Journal of Combinatorial Theory , Serie B, 39 (3): 200–208, doi : 10.1016 / 0095-8956 (85) 90050-4 , MR 0815392.
- Kennedy, William S .; Reed, Bruce (2008), "Reconocimiento rápido de particiones sesgadas", Teoría de gráficos y geometría computacional: Conferencia internacional, KyotoCGGT 2007, Kyoto, Japón, 11 al 15 de junio de 2007, Revised Selected Papers , Lecture Notes in Computer Science , 4535 , Berlín : Springer, págs. 101-107, doi : 10.1007 / 978-3-540-89550-3_11 , MR 2672388.
- Lovász, László (1972), "Hipergrafías normales y la conjetura de la gráfica perfecta", Matemáticas discretas , 2 (3): 253-267, doi : 10.1016 / 0012-365X (72) 90006-4.
- Reed, Bruce (2008), "Particiones sesgadas en gráficos perfectos" (PDF) , Matemáticas aplicadas discretas , 156 (7): 1150-1156, doi : 10.1016 / j.dam.2007.05.054 , MR 2404228.
- Roussel, F .; Rubio, P. (2001), "Acerca de particiones sesgadas en gráficos imperfectos mínimos", Journal of Combinatorial Theory , Serie B, 83 (2): 171-190, doi : 10.1006 / jctb.2001.2044 , MR 1866394.
- Seymour, Paul (2006), "Cómo se encontró la prueba de la conjetura de gráfico perfecto fuerte" (PDF) , Gazette des Mathématiciens (109): 69–83, MR 2245898.
- Trotignon, Nicolas (2008), "Descomposición de gráficos de Berge y detección de particiones sesgadas equilibradas" (PDF) , Journal of Combinatorial Theory , Serie B, 98 (1): 173-225, arXiv : 1309.0680 , doi : 10.1016 / j.jctb. 2007.07.004 , MR 2368032.