División (teoría de grafos)

En teoría de grafos , una división de un grafo no dirigido es un corte cuyo conjunto de cortes forma un grafo bipartito completo . Un grafo es primo si no tiene divisiones. Las divisiones de un grafo se pueden agrupar en una estructura arbórea llamada descomposición de división o descomposición de unión , que se puede construir en tiempo lineal. Esta descomposición se ha utilizado para el reconocimiento rápido de grafos circulares y grafos hereditarios de distancia , así como para otros problemas en algoritmos de grafos.

Las divisiones y descomposiciones divididas fueron introducidas por primera vez por Cunningham (1982) , quien también estudió variantes de las mismas nociones para grafos dirigidos . ^{[ 1 ]}

Un corte de un grafo no dirigido es una partición de los vértices en dos subconjuntos no vacíos, los lados del corte. El subconjunto de aristas que tienen un extremo en cada lado se llama conjunto de corte. Cuando un conjunto de corte forma un grafo bipartito completo , su corte se llama división. Por lo tanto, una división puede describirse como una partición de los vértices del grafo en dos subconjuntos X e Y , de tal manera que cada vecino de X en Y es adyacente a cada vecino ^de Y en X. ^{[ 2} ]

Un corte o división es trivial cuando uno de sus dos lados tiene un solo vértice; todo corte trivial es una división. Se dice que un grafo es primo (con respecto a las divisiones) si no tiene divisiones no triviales. ^{[ 2 ]}

Se dice que dos divisiones se cruzan si cada lado de una división tiene una intersección no vacía con cada lado de la otra división. Una división se llama fuerte cuando no es cruzada por ninguna otra división. Como caso especial, toda división trivial es fuerte. Las divisiones fuertes de un grafo dan lugar a una estructura llamada descomposición de división o descomposición de unión del grafo. Esta descomposición puede representarse mediante un árbol cuyas hojas se corresponden biunívocamente con el grafo dado, y cuyas aristas se corresponden biunívocamente con las divisiones fuertes del grafo, de modo que la partición de hojas formada al eliminar cualquier arista del árbol es la misma que la partición de vértices dada por la división fuerte asociada. ^{[ 2 ]}

Cada nodo interno i del árbol de descomposición dividida de un grafo G está asociado con un grafo G _i , llamado grafo cociente para el nodo i . El grafo cociente se puede formar eliminando i del árbol, formando subconjuntos de vértices en G que corresponden a las hojas en cada uno de los subárboles resultantes y colapsando cada uno de estos conjuntos de vértices en un solo vértice. Todo grafo cociente tiene una de tres formas: puede ser un grafo primo, un grafo completo o una estrella . ^{[ 2 ]} 

Un grafo puede tener exponencialmente muchas divisiones diferentes, pero todas están representadas en el árbol de descomposición de divisiones, ya sea como una arista del árbol (para una división fuerte) o como una partición arbitraria de un grafo cociente completo o estrella (para una división que no es fuerte). ^{[ 2 ]}

En un grafo completo o en un grafo bipartito completo , cada corte es una división.

En un grafo cíclico de longitud cuatro, la partición de los vértices dada por la coloración con dos colores del ciclo es una división no trivial, pero para ciclos de longitud mayor no existen divisiones no triviales.

Un puente de un grafo que no es 2-arista-conexo corresponde a una división, con cada lado de la división formado por los vértices en un lado del puente. El conjunto de corte de la división es solo la única arista del puente, que es un caso especial de un subgrafo bipartito completo. De manera similar, si v es un punto de articulación de un grafo que no es 2-vértice-conexo , entonces el grafo tiene múltiples divisiones en las que v y algunos pero no todos los componentes formados por su eliminación están en un lado, y los componentes restantes están en el otro lado. En estos ejemplos, el conjunto de corte de la división forma una estrella .

Cunningham (1982) ya demostró que es posible encontrar la descomposición dividida en tiempo polinomial . ^{[ 1 ]} Después de mejoras posteriores al algoritmo, ^{[ 3 ] [ 4 ]} Dahlhaus (2000) ^{[ 5 ]} y Charbit, de Montgolfier y Raffinot (2012) descubrieron algoritmos de tiempo lineal . ^{[ 2 ]}

La descomposición dividida se ha aplicado en el reconocimiento de varias clases importantes de grafos:

• Un grafo hereditario de distancia es un grafo cuya descomposición en escisión no contiene cocientes primos. Basándonos en esta caracterización, es posible utilizar la descomposición en escisión para reconocer grafos hereditarios de distancia en tiempo lineal. ^{[ 6 ] [ 7 ]}
• Los grafos de paridad pueden reconocerse en tiempo lineal como los grafos en los que cada cociente dividido es completo o bipartito . ^{[ 8 ]}
• Un grafo circular es el grafo de intersección de una familia de cuerdas de un círculo. Un grafo dado es un grafo circular si y solo si cada uno de los cocientes de su descomposición es un grafo circular, por lo que comprobar si un grafo es circular se reduce al mismo problema aplicado a los grafos cociente primos del grafo. Además, cuando un grafo circular es primo, la estructura combinatoria del conjunto de cuerdas que lo representa está determinada de forma única, lo que simplifica la tarea de reconocer esta estructura. Basándonos en estas ideas, es posible reconocer grafos circulares en tiempo polinomial. ^{[ 3 ]}

La descomposición dividida también se ha utilizado para simplificar la solución de algunos problemas que son NP-difíciles en grafos arbitrarios: ^{[ 9 ]}

• Como ya observó Cunningham (1982) , el conjunto independiente máximo de cualquier grafo puede hallarse mediante un algoritmo de programación dinámica en un recorrido ascendente de su árbol de descomposición bifurcado. En cada nodo, elegimos el conjunto independiente de peso máximo en su grafo cociente, ponderado por los tamaños de los conjuntos independientes ya calculados en los nodos hijos. ^{[ 1 ]}
• Aunque otro algoritmo propuesto por Cunningham (1982) es defectuoso, se puede utilizar un recorrido ascendente similar para calcular la camarilla máxima de un grafo combinando los cálculos de las camarillas máximas ponderadas en sus grafos cociente. ^{[ 9 ]}
• Rao (2008) también presenta algoritmos para conjuntos dominantes conectados , conjuntos dominantes completos y coloración de grafos . ^{[ 9 ]}

Estos métodos pueden dar lugar a algoritmos de tiempo polinomial para grafos en los que cada grafo cociente tiene una estructura simple que permite calcular su subproblema de manera eficiente. Por ejemplo, esto se cumple en el caso de grafos en los que cada grafo cociente tiene un tamaño constante. ^{[ 9 ]}