Ruptura (teoría de grafos)
En teoría de grafos, una ruptura de un grafo no dirigido es un corte cuyo conjunto de corte forma un grafo bipartito completo. Un grafo es primo si no tiene ninguna ruptura. Las rupturas de un grafo pueden ser acomodadas siguiendo una estructura de árbol llamada descomposición de ruptura o descomposición conjunta, la cual puede ser construida en tiempo lineal. Esta descomposición ha sido utilizada para el reconocimiento rápido de grafos circulares y grafos de distancia hereditaria, así como para otros problemas en algoritmos de grafos.
Las rupturas y descomposiciones de ruptura fueron introducidas por Cunningham (1982), quien también estudió variantes de estas mismas nociones para grafos dirigidos.[1]
Definiciones
[editar]Un corte de un grafo no dirigido es una partición de los vértices en dos subconjuntos no vacíos, los cuales son los lados del corte. El subconjunto de aristas que tiene un vértice en cada lado se llama el conjunto de corte. Cuando un conjunto de corte forma un grafo bipartito completo, a este corte le llamamos ruptura. Así, una ruptura puede ser descrita como una partición de los vértices del grafo en dos subconjuntos X e Y, tal que cada vecino de X en Y es adyacente a cada vecino de Y en X.[2]
Un corte o ruptura es trivial cuando uno de sus dos lados tiene sólo un vértice en él; todo corte trivial es una ruptura. Decimos que un grafo es primo (con respecto a rupturas) si no tiene rupturas notriviales.[2]
Decimos que dos rupturas se cruzan si cada lado de una de las rupturas tiene una intersección no vacía con cada lado de la otra ruptura. Una ruptura es fuerte cuando no es cruzada por ninguna otra ruptura. Como caso especial, toda ruptura trivial es fuerte. Las rupturas fuertes de un grafo inducen una estructura llamada la descomposición de ruptura o descomposición conjunta del grafo. Esta descomposición puede ser representada por un árbol cuyas hojas corresponden uno-a-uno con el grafo dado y cuyas aristas corresponden uno-a-uno con las rupturas fuertes del grafo, tal que la partición de hojas formada removiendo cualquier arista del árbol es igual a la partición de los vértices dada por la ruptura fuerte asociada.[2]
Cada nodo interno i del árbol de descomposición de ruptura de un grafo G está asociado con un grafo Gi, llamado el grafo cociente para el nodo i. El grafo cociente puede ser formado eliminando al vértice 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 hacia un solo vértice. Cada grafo cociente tiene una de tres formas: puede ser un grafo primo, un grafo completo, o una estrella.[2]
Un grafo puede tener una cantidad exponencial de rupturas diferentes, pero todas estas son representadas en el árbol de descomposición de ruptura, ya sea como una arista de este árbol (para una ruptura fuerte) o como partición arbitraria de un grafo cociente completo o estrella (para una ruptura que no es fuerte).[2]
Ejemplos
[editar]En un grafo completo o grafo bipartito completo, cada corte es una ruptura.
En un grafo ciclo de longitud cuatro, la partición de los vértices dada a partir de la 2-coloración el ciclo es una ruptura no trivial, pero para ciclos de longitud mayor, no existen rupturas no triviales.
Un puente de un grafo que no es 2-arista-conectado corresponde a una ruptura, con cada lado de la ruptura formada por los vértices de un lado del puente. El conjunto de corte de la ruptura es justo la única arista en el puente, lo cual es un caso especial de un subgrafo completo bipartito. Del mismo modo, si v es un punto de articulación de un grafo que no es 2-vértice-conectado, entonces el grafo tiene múltiples rupturas 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 ruptura forma una estrella.
Algoritmos
[editar]Cunningham (1982) ya había probado que era posible encontrar la descomposición de ruptura en tiempo polinomial.[1] Después de una serie de mejorías en el diseño del algoritmo,[3][4] algoritmos de tiempo linear fueron descubiertos por Dahlhaus (2000)[5] y Charbit, de Montgolfier y Raffinot (2012).[2]
Aplicaciones
[editar]La descomposición de ruptura ha encontrado aplicaciones en el reconocimiento de varias clases importantes de grafos:
- Una distancia-hereditario graph es un graph cuya descomposición de ruptura contiene no cocientes primos. Basado en esta caracterización, es posible de utilizar la descomposición de ruptura para reconocer distancia-hereditario graphs en tiempo lineal.[6][7]
- Paridad graphs puede ser reconocido en tiempo lineal como el graphs en qué cada cociente de ruptura es cualquier completo o bipartite.[8]
- Un círculo graph es la intersección graph de una familia de acordes de un círculo. Un dado graph es un círculo graph si y sólo si cada cual de los cocientes de su descomposición de ruptura es un círculo graph, así que probando si un graph es un círculo graph puede ser reducido al mismo problema en el cociente primo graphs del graph. Más, cuándo un círculo graph es primo, el combinatorial estructura del conjunto de los acordes que representan es singularmente determinado, el cual simplifica la tarea de reconocer esta estructura. Basado en estas ideas, es posible de reconocer círculo graphs en tiempo polinómico.[3]
La descomposición de ruptura también ha sido utilizada para simplificar la solución de problemas que son NP-difíciles en grafos arbitrarios:[9]
- Como Cunningham (1982) ha observado, el máximo conjunto independiente de cualquier grafo puede ser encontrado por medio de un algoritmo de programación dinámica en una transversal de abajo a arriba de su árbol de descomposición de ruptura. En cada nodo escogemos el conjunto independiente de máximo peso en su grafo cociente, donde los pesos son dados por los tamaños de los conjuntos independientes ya computados en nodos sucesores.[1]
- A pesar de que otro algoritmo dado por Cunningham (1982) es erróneo, una transversal de abajo a arriba similar puede ser usada para computar el tamaño máximo de clique de un grafo combinando las computaciones de cliques máximos según su peso en sus grafos cocientes.[9]
- Rao (2008) también presenta algoritmos para conjuntos dominantes conexos, conjuntos dominantes completos, y coloración de grafos.[9]
Estos métodos pueden llevarnos a descubrir algoritmos de tiempo polinomial para grafos en los que cada grafo cociente tiene una estructura sencilla que permite que el subproblema pueda ser computado eficientemente. Por ejemplo, esto es cierto para grafos en los que cada grafo cociente tiene tamaño constante.[9]
Referencias
[editar]- ↑ a b c Cunningham, William H. (1982), «Decomposition of directed graphs», SIAM Journal on Algebraic and Discrete Methods 3 (2): 214-228, doi:10.1137/0603021.
- ↑ a b c d e f Charbit, Pierre; de Montgolfier, Fabien; Raffinot, Mathieu (2012), «Linear time split decomposition revisited», SIAM Journal on Discrete Mathematics 26 (2): 499-514, doi:10.1137/10080052X.
- ↑ a b Gabor, Csaba P.; Supowit, Kenneth J.; Hsu, Wen Lian (1989), «Recognizing circle graphs in polynomial time», Journal of the ACM 36 (3): 435-473, doi:10.1145/65950.65951.
- ↑ Ma, Tze Heng; Spinrad, Jeremy (1994), «An O(n2) algorithm for undirected split decomposition», Journal of Algorithms 16 (1): 145-160, doi:10.1006/jagm.1994.1007..
- ↑ Dahlhaus, Elias (2000), «Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition», Journal of Algorithms 36 (2): 205-240, doi:10.1006/jagm.2000.1090..
- ↑ Gavoille, Cyril; Paul, Christophe (2003), «Distance labeling scheme and split decomposition», Discrete Mathematics 273 (1–3): 115-130, doi:10.1016/S0012-365X(03)00232-2..
- ↑ Gioan, Emeric; Paul, Christophe (2012), «Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs», Discrete Applied Mathematics 160 (6): 708-733, doi:10.1016/j.dam.2011.05.007..
- ↑ Cicerone, Serafino; Di Stefano, Gabriele (1997), «On the equivalence in complexity among basic problems on bipartite and parity graphs», Algorithms and computation (Singapore, 1997), Lecture Notes in Comput. Sci. 1350, Springer, Berlin, pp. 354-363, ISBN 978-3-540-63890-2, doi:10.1007/3-540-63890-3_38..
- ↑ a b c d Rao, Michaël (2008), «Solving some NP-complete problems using split decomposition», Discrete Applied Mathematics 156 (14): 2768-2780, doi:10.1016/j.dam.2007.11.013.