En la teoría de grafos , la descomposición modular es una descomposición de un grafo en subconjuntos de vértices llamados módulos. Un módulo es una generalización de un componente conectado de un gráfico. Sin embargo, a diferencia de los componentes conectados, un módulo puede ser un subconjunto adecuado de otro. Por lo tanto, los módulos conducen a una descomposición recursiva (jerárquica) del gráfico, en lugar de solo a una partición.
Existen variantes de descomposición modular para gráficos no dirigidos y gráficos dirigidos . Para cada gráfico no dirigido, esta descomposición es única.
Esta noción se puede generalizar a otras estructuras (por ejemplo, gráficos dirigidos) y es útil para diseñar algoritmos eficientes para el reconocimiento de algunas clases de gráficos, para encontrar orientaciones transitivas de gráficos de comparabilidad , para problemas de optimización en gráficos y para dibujar gráficos .
Módulos
Como la noción de módulos se ha redescubierto en muchas áreas, los módulos también se han denominado conjuntos autónomos , conjuntos homogéneos , intervalos y conjuntos partitivos . Quizás la primera referencia a ellos y la primera descripción de los cocientes modulares y la descomposición gráfica que dan lugar aparecieron en ( Gallai 1967).
Un módulo de un gráfico es una generalización de un componente conectado . Un componente conectado tiene la propiedad de que es un conjunto de vértices de modo que cada miembro de es un no vecino de todos los vértices que no están en. (Es una unión de componentes conectados si y solo si tiene esta propiedad). De manera más general, es un módulo si, para cada vértice , ya sea cada miembro de es un no vecino de o cada miembro de es vecino de .
Equivalentemente, es un módulo si todos los miembros de tienen el mismo conjunto de vecinos entre vértices que no están en .
A diferencia de los componentes conectados, los módulos de un gráfico son los mismos que los módulos de su complemento , y los módulos se pueden "anidar": un módulo puede ser un subconjunto propio de otro. Tenga en cuenta que el conjuntode vértices de un gráfico es un módulo, al igual que sus subconjuntos de un elemento y el conjunto vacío; estos se denominan módulos triviales . Un gráfico puede tener o no otros módulos. Un gráfico se llama primo si todos sus módulos son triviales.
A pesar de estas diferencias, los módulos conservan una propiedad deseable de los componentes conectados, que es que muchas propiedades del subgrafo inducida por un componente conectadoson independientes del resto del gráfico. Un fenómeno similar también se aplica a los subgrafos inducidos por módulos.
Los módulos de un gráfico son, por tanto, de gran interés algorítmico. Un conjunto de módulos anidados, de los cuales la descomposición modular es un ejemplo, se puede utilizar para guiar la solución recursiva de muchos problemas combinatorios en gráficos, como reconocer y orientar de manera transitiva gráficos de comparabilidad , reconocer y encontrar representaciones de permutación de gráficos de permutación , reconociendo si una gráfica es una cografía y encontrar un certificado de la respuesta a la pregunta, reconociendo gráficas de intervalo y encontrando representaciones de intervalo para ellas, definiendo gráficas de distancia-hereditarias (Spinrad, 2003) y para el dibujo de gráficas (Papadopoulos, 2006). Desempeñan un papel importante en la celebrada demostración del teorema del grafo perfecto de Lovász (Golumbic, 1980).
Para reconocer gráficos hereditarios de distancia y gráficos circulares , una generalización adicional de la descomposición modular, llamada descomposición dividida , es especialmente útil (Spinrad, 2003).
Para evitar la posibilidad de ambigüedad en las definiciones anteriores, proporcionamos las siguientes definiciones formales de módulos. . es un módulo de Si:
- los vértices de no se puede distinguir por ningún vértice en , es decir, , ya sea es adyacente a ambos y o no es adyacente a ni a .
- los vértices de tienen el mismo conjunto de vecinos externos, es decir, .
, y todos los singletons por son módulos y se denominan módulos triviales . Un gráfico es primo si todos sus módulos son triviales. Componentes conectados de un gráfico, o de su gráfico de complemento son también módulos de .
es un módulo sólido de un gráfico si no se superpone a ningún otro módulo de : módulo de , ya sea o o .
Cocientes y factores modulares
Si y son módulos disjuntos, entonces es fácil ver que cada miembro de es vecino de cada elemento de , o ningún miembro de es adyacente a cualquier miembro de . Por tanto, la relación entre dos módulos disjuntos es adyacente o no adyacente . No puede existir una relación intermedia entre estos dos extremos.
Debido a esto, las particiones modulares dedonde cada clase de partición es un módulo son de particular interés. Suponeres un tabique modular. Dado que las clases de partición son disjuntas, sus adyacencias constituyen un nuevo gráfico, un gráfico de cociente , cuyos vértices son los miembros de . Es decir, cada vértice de es un módulo de G, y las adyacencias de estos módulos son los bordes de .
En la siguiente figura, el vértice 1, los vértices del 2 al 4, el vértice 5, los vértices 6 y 7 y los vértices del 8 al 11 son una partición modular. En el diagrama superior derecho, los bordes entre estos conjuntos representan el cociente dado por esta partición, mientras que los bordes internos de los conjuntos representan los factores correspondientes.
Las particiones y son las triviales particiones modulares . es solo el gráfico de un vértice, mientras que . Suponeres un módulo no trivial. Luego y los subconjuntos de un elemento de son una partición modular no trivial de . Por lo tanto, la existencia de ningún módulos no triviales implica la existencia de tabiques modulares no triviales. En general, muchos o todos los miembros de pueden ser módulos no triviales.
Si es una partición modular no trivial, entonces es una representación compacta de todos los bordes que tienen puntos finales en diferentes clases de partición de . Para cada clase de partición en , el subgrafo Inducido por se llama factor y da una representación de todos los bordes con ambos extremos en. Por lo tanto, los bordes de se puede reconstruir dado solo el gráfico del cociente y sus factores. El término gráfico primo proviene del hecho de que un gráfico primo tiene solo cocientes y factores triviales.
Cuándo es un factor de un cociente modular , es posible que se puede descomponer de forma recursiva en factores y cocientes. Cada nivel de la recursividad da lugar a un cociente. Como caso base, la gráfica tiene solo un vértice. Colectivamente, se puede reconstruir inductivamente reconstruyendo los factores de abajo hacia arriba, invirtiendo los pasos de la descomposición combinando factores con el cociente en cada nivel.
En la figura siguiente, dicha descomposición recursiva está representada por un árbol que muestra una forma de descomponer de forma recursiva los factores de una partición modular inicial en particiones modulares más pequeñas.
Una forma de descomponer de forma recursiva un gráfico en factores y cocientes puede no ser única. (Por ejemplo, todos los subconjuntos de los vértices de un gráfico completo son módulos, lo que significa que hay muchas formas diferentes de descomponerlo de forma recursiva). Algunas formas pueden ser más útiles que otras.
La descomposición modular
Afortunadamente, existe tal descomposición recursiva de un gráfico que representa implícitamente todas las formas de descomponerlo; esta es la descomposición modular. Es en sí mismo una forma de descomponer un gráfico de forma recursiva en cocientes, pero subsume a todos los demás. La descomposición que se muestra en la siguiente figura es esta descomposición especial para el gráfico dado.
La siguiente es una observación clave para comprender la descomposición modular:
Si es un módulo de y es un subconjunto de , luego es un módulo de , si y solo si es un módulo de .
En (Gallai, 1967), Gallai definió la descomposición modular de forma recursiva en un gráfico con vértices establecidos , como sigue:
- Como caso base, si solo tiene un vértice, su descomposición modular es un solo nodo de árbol.
- Gallai demostró que si está conectado y también su complemento, entonces los módulos máximos que son subconjuntos propios de son una partición de . Por tanto, son una partición modular. El cociente que definen es primo. La raíz del árbol se etiqueta como nodo principal y estos módulos se asignan como hijos de. Dado que son máximos, todos los módulos no representados hasta ahora están contenidos en un elemento secundario. de . Para cada niño de , reemplazando con el árbol de descomposición modular de da una representación de todos los módulos de , por la observación clave anterior.
- Si está desconectado, su complemento está conectado. Cada unión de componentes conectados es un módulo de. Todos los demás módulos son subconjuntos de un solo componente conectado. Esto representa todos los módulos, excepto los subconjuntos de componentes conectados. Para cada componente, reemplazando por el árbol de descomposición modular de da una representación de todos los módulos de , por la observación clave anterior. La raíz del árbol se etiqueta como un nodo paralelo y se adjunta en lugar decomo hijo de la raíz. El cociente definido por los niños es el complemento de una gráfica completa.
- Si el complemento de está desconectado, está conectado. Los subárboles que son hijos de se definen de forma simétrica con el caso en el que está desconectado, ya que los módulos de un gráfico son los mismos que los módulos de su complemento. La raíz del árbol está etiquetada como un nodo en serie y el cociente definido por los hijos es un gráfico completo.
El árbol final tiene conjuntos de vértices de un elemento de como sus hojas, debido al caso base. Un conjunto de vértices de es un módulo si y solo si es un nodo del árbol o una unión de hijos de una serie o nodo paralelo. Esto implícitamente da a todas las particiones modulares de. Es en este sentido que el árbol de descomposición modular "subsume" todas las demás formas de descomponer recursivamente en cocientes.
Problemas algorítmicos
Una estructura de datos para representar el árbol de descomposición modular debe soportar la operación que ingresa un nodo y devuelve el conjunto de vértices de que representa el nodo. Una forma obvia de hacer esto es asignar a cada nodo una lista de los vértices de que representa. Dado un puntero a un nodo, esta estructura podría devolver el conjunto de vértices de que representa en hora. Sin embargo, esta estructura de datos requeriría espacio en el peor de los casos.
Un -La alternativa de espacio que coincide con este rendimiento se obtiene representando el árbol de descomposición modular utilizando cualquier estándar estructura de datos de árbol enraizado y etiquetar cada hoja con el vértice de que representa. El conjunto representado por un nodo internoviene dado por el conjunto de etiquetas de sus descendientes de hojas. Es bien sabido que cualquier árbol enraizado con hojas tiene como máximo nodos internos. Se puede utilizar una búsqueda en profundidad a partir de para informar las etiquetas de los descendientes de hojas de en hora.
Cada nodo es un conjunto de vértices de y si es un nodo interno, el conjunto de hijos de es una partición de donde cada clase de partición es un módulo. Por tanto, inducen el cociente en . Los vértices de este cociente son los elementos de, entonces puede representarse instalando bordes entre los hijos de . Si y son dos miembros de y y , luego y son adyacentes en si y solo si y son adyacentes en este cociente. Para cualquier par de vértices de , esto está determinado por el cociente en los hijos del antepasado menos común de y en el árbol de descomposición modular. Por tanto, la descomposición modular, etiquetada de esta forma con cocientes, da una representación completa de.
Muchos problemas combinatorios se pueden resolver en resolviendo el problema por separado en cada uno de estos cocientes. Por ejemplo,es un gráfico de comparabilidad si y solo si cada uno de estos cocientes es un gráfico de comparabilidad (Gallai, 67; Möhring, 85). Por lo tanto, para encontrar si una gráfica es una gráfica de comparabilidad, solo es necesario encontrar si cada uno de los cocientes lo es. De hecho, para encontrar una orientación transitiva de un gráfico de comparabilidad, basta con orientar transitivamente cada uno de estos cocientes de su descomposición modular (Gallai, 67; Möhring, 85). Un fenómeno similar se aplica a los gráficos de permutación (McConnell y Spinrad '94), los gráficos de intervalo (Hsu y Ma '99), los gráficos perfectos y otras clases de gráficos. Algunos problemas importantes de optimización combinatoria en gráficos se pueden resolver utilizando una estrategia similar (Möhring, 85).
Los cographs son los gráficos que solo tienen nodos paralelos o en serie en su árbol de descomposición modular.
El primer algoritmo polinomial para calcular el árbol de descomposición modular de un gráfico se publicó en 1972 (James, Stanton y Cowan 1972) y ahora hay disponibles algoritmos lineales (McConnell y Spinrad 1999, Tedder et al. 2007, Cournier y Habib 1994).
Generalizaciones
La descomposición modular de gráficos dirigidos se puede realizar en tiempo lineal ( McConnell y de Montgolfier 2005 ).
Con una pequeña cantidad de excepciones simples, cada gráfico con una descomposición modular no trivial también tiene una partición sesgada ( Reed 2008 ).
Referencias
- Gallai, Tibor (1967). "Transitiv orientierbare Graphen". Acta Mathematica Academiae Scientiarum Hungaricae . 18 (1–2): 25–66. doi : 10.1007 / BF02020961 . Señor 0221974 . S2CID 119485995 .
- James, Lee O .; Stanton, Ralph G .; Cowan, Donald D. (1972). "Descomposición de gráficos para gráficos no dirigidos". Proc. 3ra Conferencia Internacional del Sureste sobre Combinatoria, Teoría de Gráficos y Computación (Florida Atlantic Univ., Boca Raton, Fla., 1972) . Universidad Atlántica de Florida . págs. 281–290. Señor 0351909 .
- Golumbic, Martin C. (1980). Teoría algorítmica de grafos y grafos perfectos . Prensa académica. ISBN 0-444-51530-5.
- Hsu, WL; Ma, T. (1999). "Algoritmos rápidos y sencillos para reconocer gráficos de comparabilidad de cuerdas y gráficos de intervalo". Revista SIAM de Computación . 28 (3): 1004–1020. CiteSeerX 10.1.1.104.4647 . doi : 10.1137 / S0097539792224814 .
- McConnell, Ross M .; de Montgolfier, Fabien (2005). "Descomposición modular en tiempo lineal de grafos dirigidos". Matemáticas aplicadas discretas . 145 (2): 198-209. doi : 10.1016 / j.dam.2004.02.017 .
- McConnell, Ross M .; Spinrad, Jeremy P. (1999). "Descomposición modular y orientación transitiva" (PDF) . Matemáticas discretas . 201 (1–3): 189–241. doi : 10.1016 / S0012-365X (98) 00319-7 . Señor 1687819 .
- Möhring, Rolf H. (1985). I. Rival (ed.). "Aspectos algorítmicos de gráficos de comparabilidad y gráficos de intervalo". Gráficos y orden . D. Reidel: 41–101. doi : 10.1007 / 978-94-009-5315-4_2 . ISBN 978-94-010-8848-0.
- Möhring, Rolf H. (1985). "Aspectos algorítmicos de la descomposición por sustitución en optimización sobre relaciones, sistemas de conjuntos y funciones booleanas". Anales de investigación operativa . 4 : 195-225. doi : 10.1007 / BF02022041 . S2CID 119982014 .
- Papadopoulos, Charis; Voglis, Constantinos (2005). "Dibujar gráficos mediante descomposición modular" (PDF) . Proc. XIII Simposio Internacional de Dibujo Gráfico (GD'05) . Apuntes de conferencias en Ciencias de la Computación. 3843 . Springer-Verlag. págs. 343–354. doi : 10.1007 / 11618058_31 . Señor 2229205 .
- Reed, Bruce (2008). "Inclinar particiones en gráficos perfectos" (PDF) . Matemáticas aplicadas discretas . 156 (7): 1150-1156. doi : 10.1016 / j.dam.2007.05.054 . Señor 2404228 . Archivado desde el original (PDF) el 19 de septiembre de 2015 . Consultado el 13 de agosto de 2012 .
- Spinrad, Jeremy P. (2003). Representaciones gráficas eficientes . Monografías del Fields Institute. Sociedad Matemática Estadounidense. ISBN 0-8218-2815-0.
- Tedder, Marc; Corneil, Derek ; Habib, Michel; Paul, Christophe (2008). "Descomposición modular de tiempo lineal más simple a través de permutaciones de factorización recursivas". Proc. 35º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP 2008) . Apuntes de conferencias en Ciencias de la Computación. 5125 . Springer-Verlag. págs. 634–645. arXiv : 0710.3901 . doi : 10.1007 / 978-3-540-70575-8_52 .
- Zahedi, Emad ; Smith, Jason (2018). "Descomposición modular de gráficos y la propiedad de preservación de la distancia" . Matemáticas aplicadas discretas (7). arXiv : 1805.09853 . Código Bib : 2018arXiv180509853Z .
enlaces externos
- Una implementación de Perl de un algoritmo de descomposición modular
- Una implementación de Java de un algoritmo de descomposición modular