descomposición modular

En teoría de grafos , la descomposición modular consiste en descomponer un grafo en subconjuntos de vértices llamados módulos. Un módulo es una generalización de un componente conexo de un grafo. Sin embargo, a diferencia de los componentes conexos, un módulo puede ser un subconjunto propio de otro. Por lo tanto, los módulos dan lugar a una descomposición recursiva (jerárquica) del grafo, en lugar de una simple partición .

Existen variantes de descomposición modular para grafos no dirigidos y grafos dirigidos . Para cada grafo no dirigido, esta descomposición es única.

Esta noción se puede generalizar a otras estructuras (por ejemplo, grafos dirigidos) y es útil para diseñar algoritmos eficientes para el reconocimiento de algunas clases de grafos, para encontrar orientaciones transitivas de grafos de comparabilidad , para problemas de optimización en grafos y para el dibujo de grafos .

Dado que la noción de módulos se ha redescubierto en muchas áreas, también se les ha llamado conjuntos autónomos , conjuntos homogéneos , conjuntos estables , cúmulos , comités , conjuntos relacionados externamente , intervalos , subredes no simplificables y conjuntos partitivos ( Brandstädt, Le y Spinrad 1999 ) . Quizás la referencia más antigua a ellos, y la primera descripción de los cocientes modulares y la descomposición de grafos a la que dan lugar, apareció en ( Gallai 1967).

Un módulo de un grafo es una generalización de un componente conexo . Un componente conexo tiene la propiedad de ser un conjunto.${\displaystyle X}$de vértices de tal manera que cada miembro de${\displaystyle X}$es un no vecino de cada vértice que no está en${\displaystyle X}$. (Es una unión de componentes conexas si y solo si tiene esta propiedad.) Más generalmente,${\displaystyle X}$es un módulo si, para cada vértice${\displaystyle v\not \in X}$, ya sea cada miembro de${\displaystyle X}$es un no vecino de${\displaystyle v}$o cada miembro de${\displaystyle X}$es vecino de${\displaystyle v}$.

De forma equivalente,${\displaystyle X}$es un módulo si todos los miembros de${\displaystyle X}$tener el mismo conjunto de vecinos entre vértices que no están en${\displaystyle X}$.

A diferencia de los componentes conexos, los módulos de un grafo son los mismos que los módulos de su complemento , y los módulos pueden estar "anidados": un módulo puede ser un subconjunto propio de otro. Nótese que el conjunto${\displaystyle V}$Un conjunto de vértices de un grafo constituye un módulo, al igual que sus subconjuntos de un solo elemento y el conjunto vacío ; estos se denominan módulos triviales . Un grafo puede tener o no otros módulos. Un grafo se denomina 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${\displaystyle G[X]}$inducido por un componente conectado${\displaystyle X}$son independientes del resto del grafo. Un fenómeno similar también se aplica a los subgrafos inducidos por módulos.

Los módulos de un grafo son, por lo tanto, de gran interés algorítmico. Un conjunto de módulos anidados, del cual la descomposición modular es un ejemplo, puede utilizarse para guiar la solución recursiva de muchos problemas combinatorios sobre grafos, como el reconocimiento y la orientación transitiva de grafos de comparabilidad , el reconocimiento y la obtención de representaciones de permutación de grafos de permutación , el reconocimiento de si un grafo es un cografo y la obtención de un certificado de la respuesta a la pregunta, el reconocimiento de grafos de intervalo y la obtención de representaciones de intervalo para ellos, la definición de grafos hereditarios de distancia (Spinrad, 2003) y para el dibujo de grafos (Papadopoulos, 2006). Desempeñan un papel importante en la célebre demostración de Lovász del teorema del grafo perfecto (Golumbic, 1980).

Para reconocer grafos hereditarios de distancia y grafos 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, damos las siguientes definiciones formales de módulos. Sea${\displaystyle G=(V,E)}$ser un grafo. Un conjunto${\displaystyle M\subseteq V}$es un módulo de${\displaystyle G}$si los vértices de${\displaystyle M}$no puede distinguirse por ningún vértice en${\displaystyle V\backslash M}$, es decir,${\displaystyle \forall u,v\in M,\forall x\in V\backslash M}$, cualquiera${\displaystyle x}$está adyacente a ambos${\displaystyle u}$y${\displaystyle v}$o${\displaystyle x}$no es adyacente a${\displaystyle u}$ni a${\displaystyle v}$.

Esta condición se puede escribir sucintamente como${\displaystyle N(u)\setminus M=N(v)\setminus M}$a pesar de${\displaystyle u,v\in M}$. Aquí,${\displaystyle N(u)}$denota el conjunto de vecinos de${\displaystyle u\in V}$.

Por ejemplo,${\displaystyle \emptyset }$,${\displaystyle V}$y todos los solteros${\displaystyle \{v\}}$para${\displaystyle v\in V}$son módulos. Se les llama módulos triviales . Un grafo es primo si todos sus módulos son triviales. Componentes conexas de un grafo${\displaystyle G}$, o de su gráfico complementario también son módulos de${\displaystyle G}$.

${\displaystyle M}$es un módulo fuerte de un grafo${\displaystyle G}$si no se superpone a ningún otro módulo de${\displaystyle G}$: ${\displaystyle \forall M'}$módulo de${\displaystyle G}$, cualquiera${\displaystyle M\cap M'=\emptyset }$o${\displaystyle M\subseteq M'}$o${\displaystyle M'\subsetequ M}$.

Si${\displaystyle X}$y${\displaystyle Y}$son módulos disjuntos, entonces es fácil ver que o bien cada miembro de${\displaystyle X}$es vecino de cada elemento de${\displaystyle Y}$, o ningún miembro de${\displaystyle X}$es adyacente a cualquier miembro de${\displaystyle Y}$Por lo tanto, la relación entre dos módulos disjuntos es adyacente o no adyacente . No puede existir ninguna relación intermedia entre estos dos extremos.

Debido a esto, particiones modulares de${\displaystyle V}$donde cada clase de partición es un módulo son de particular interés. Supongamos${\displaystyle P}$es una partición modular. Dado que las clases de partición son disjuntas, sus adyacencias constituyen un nuevo grafo, un grafo cociente.${\displaystyle G/P}$, cuyos vértices son los miembros de${\displaystyle P}$. Es decir, cada vértice de${\displaystyle G/P}$es un módulo de G, y las adyacencias de estos módulos son las aristas de${\displaystyle G/P}$.

En la figura siguiente, 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 forman una partición modular. En el diagrama superior derecho, las aristas entre estos conjuntos representan el cociente dado por esta partición, mientras que las aristas internas a los conjuntos representan los factores correspondientes.

Las particiones${\displaystyle \{V\}}$y ${\displaystyle \{\{x\}|x\in V\}}$son las particiones modulares triviales . ${\displaystyle G/\{V\}}$es simplemente el grafo de un vértice, mientras que${\displaystyle G/\{\{x\}|x\in V\}=G}$. Suponer${\displaystyle X}$es un módulo no trivial. Entonces${\displaystyle X}$y los subconjuntos de un elemento de${\displaystyle V\backslash X}$son una partición modular no trivial de${\displaystyle V}$Por lo tanto, la existencia de cualquier módulo no trivial implica la existencia de particiones modulares no triviales. En general, muchos o todos los miembros de${\displaystyle P}$pueden ser módulos no triviales.

Si${\displaystyle P}$es una partición modular no trivial, entonces${\displaystyle G/P}$es una representación compacta de todos los bordes que tienen puntos finales en diferentes clases de partición de${\displaystyle P}$. Para cada clase de partición${\displaystyle X}$en${\displaystyle P}$, el subgrafo${\displaystyle G[X]}$inducido por${\displaystyle X}$se denomina factor y proporciona una representación de todos los bordes con ambos extremos en${\displaystyle X}$. Por lo tanto, los bordes de${\displaystyle G}$puede reconstruirse a partir únicamente del gráfico cociente${\displaystyle G/P}$y sus factores. El término grafo primo proviene del hecho de que un grafo primo solo tiene cocientes y factores triviales.

Cuando${\displaystyle G[X]}$es un factor de un cociente modular${\displaystyle G/P}$, es posible que${\displaystyle G[X]}$puede descomponerse recursivamente en factores y cocientes. Cada nivel de la recursión da lugar a un cociente. Como caso base, el grafo tiene un solo vértice. Colectivamente,${\displaystyle G}$puede reconstruirse inductivamente reconstruyendo los factores de abajo hacia arriba, invirtiendo los pasos de la descomposición al combinar 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 recursivamente los factores de una partición modular inicial en particiones modulares más pequeñas.

Un método para descomponer recursivamente un grafo en factores y cocientes puede no ser único. (Por ejemplo, todos los subconjuntos de los vértices de un grafo completo son módulos, lo que significa que existen muchas maneras diferentes de descomponerlo recursivamente). Algunos métodos pueden ser más útiles que otros.

Afortunadamente, existe una descomposición recursiva de un grafo que representa implícitamente todas las formas de descomponerlo: la descomposición modular. Si bien es una forma de descomponer un grafo recursivamente en cocientes, engloba a todas las demás. La descomposición que se muestra en la figura siguiente es esta descomposición especial para el grafo dado.

La siguiente es una observación clave para comprender la descomposición modular:

Si${\displaystyle X}$es un módulo de${\displaystyle G}$y${\displaystyle Y}$es un subconjunto de${\displaystyle X}$, entonces${\displaystyle Y}$es un módulo de${\displaystyle G}$, si y solo si es un módulo de${\displaystyle G[X]}$.

En (Gallai, 1967), Gallai definió la descomposición modular recursivamente en un grafo con conjunto de vértices${\displaystyle V}$, de la siguiente manera:

1. Como caso base, si${\displaystyle G}$Tiene un solo vértice, su descomposición modular es un único nodo de árbol.
2. Gallai demostró que si${\displaystyle G}$está conectado y también lo está su complemento, entonces los módulos máximos que son subconjuntos propios de${\displaystyle V}$son una partición de${\displaystyle V}$. Por lo tanto, son una partición modular. El cociente que definen es primo. La raíz del árbol se etiqueta como un nodo primo , y estos módulos se asignan como hijos de${\displaystyle V}$Dado que son máximos, cada módulo no representado hasta ahora está contenido en un hijo.${\displaystyle X}$de${\displaystyle V}$. Por cada niño${\displaystyle X}$de${\displaystyle V}$, reemplazando${\displaystyle X}$con el árbol de descomposición modular de${\displaystyle G[X]}$proporciona una representación de todos los módulos de${\displaystyle G}$, según la observación clave anterior.
3. Si${\displaystyle G}$está desconectado, su complemento está conectado. Toda unión de componentes conectados es un módulo de${\displaystyle G}$Todos los demás módulos son subconjuntos de un único componente conectado. Esto representa todos los módulos, excepto los subconjuntos de componentes conectados. Para cada componente${\displaystyle X}$, reemplazando${\displaystyle X}$por el árbol de descomposición modular de${\displaystyle G[X]}$proporciona una representación de todos los módulos de${\displaystyle G}$, por la observación clave anterior. La raíz del árbol está etiquetada como un nodo paralelo y está adjunta en lugar de${\displaystyle X}$como hijo de la raíz. El cociente definido por los hijos es el complemento de un grafo completo.
4. Si el complemento de${\displaystyle G}$está desconectado,${\displaystyle G}$está conectado. Los subárboles que son hijos de${\displaystyle V}$se definen de una manera que es simétrica con el caso donde${\displaystyle G}$Está desconectado, ya que los módulos de un grafo son los mismos que los módulos de su complemento. La raíz del árbol se denomina nodo serial , y el cociente definido por los hijos es un grafo completo.

El árbol final tiene conjuntos de vértices de un solo elemento.${\displaystyle G}$como sus hojas, debido al caso base. Un conjunto${\displaystyle Y}$de vértices de${\displaystyle G}$es un módulo si y solo si es un nodo del árbol o una unión de hijos de un nodo en serie o en paralelo. Esto da implícitamente todas las particiones modulares de${\displaystyle V}$Es en este sentido que el árbol de descomposición modular "engloba" todas las demás formas de descomponer recursivamente.${\displaystyle G}$en cocientes.

Una estructura de datos para representar el árbol de descomposición modular debe admitir la operación que toma como entrada un nodo y devuelve el conjunto de vértices de${\displaystyle G}$que el nodo representa. Una forma obvia de hacerlo es asignar a cada nodo una lista de los${\displaystyle k}$vértices de${\displaystyle G}$que representa. Dado un puntero a un nodo, esta estructura podría devolver el conjunto de vértices de${\displaystyle G}$que representa en${\displaystyle {\mathcal {O}}(k)}$tiempo. Sin embargo, esta estructura de datos requeriría${\displaystyle \Theta (n^{2})}$espacio en el peor de los casos.

Un${\displaystyle {\mathcal {O}}(n)}$-La alternativa espacial que iguala este rendimiento se obtiene representando el árbol de descomposición modular utilizando cualquier estándar${\displaystyle {\mathcal {O}}(n)}$estructura de datos de árbol con raíz y etiquetar cada hoja con el vértice de${\displaystyle G}$que representa. El conjunto representado por un nodo interno${\displaystyle v}$viene dado por el conjunto de etiquetas de sus descendientes de hojas. Es bien sabido que cualquier árbol enraizado con${\displaystyle k}$Las hojas tienen como máximo${\displaystyle k-1}$nodos internos. Se puede utilizar una búsqueda en profundidad comenzando en${\displaystyle v}$para informar las etiquetas de los descendientes de hojas de${\displaystyle v}$en${\displaystyle {\mathcal {O}}(k)}$tiempo.

Cada nodo${\displaystyle X}$es un conjunto de vértices de${\displaystyle G}$y, si${\displaystyle X}$es un nodo interno, el conjunto${\displaystyle P}$de niños de${\displaystyle X}$es una partición de${\displaystyle X}$donde cada clase de partición es un módulo. Por lo tanto, inducen el cociente${\displaystyle G[X]/P}$en${\displaystyle G[X]}$. Los vértices de este cociente son los elementos de${\displaystyle P}$, entonces${\displaystyle G[X]/P}$puede representarse instalando aristas entre los hijos de${\displaystyle X}$. Si${\displaystyle Y}$y${\displaystyle Z}$son dos miembros de${\displaystyle P}$y${\displaystyle u\in Y}$y${\displaystyle v\in Z}$, entonces${\displaystyle u}$y${\displaystyle v}$son adyacentes en${\displaystyle G}$si y solo si${\displaystyle Y}$y${\displaystyle Z}$son adyacentes en este cociente. Para cualquier par${\displaystyle \{u,v\}}$de vértices de${\displaystyle G}$, esto se determina por el cociente en hijos del ancestro común más bajo de${\displaystyle \{u\}}$y${\displaystyle \{v\}}$en el árbol de descomposición modular. Por lo tanto, la descomposición modular, etiquetada de esta manera con cocientes, proporciona una representación completa de${\displaystyle G}$.

Muchos problemas combinatorios pueden resolverse en${\displaystyle G}$resolviendo el problema por separado en cada uno de estos cocientes. Por ejemplo,${\displaystyle G}$Un grafo es un grafo de comparabilidad si y solo si cada uno de sus cocientes es un grafo de comparabilidad (Gallai, 67; Möhring, 85). Por lo tanto, para determinar si un grafo es un grafo de comparabilidad, basta con determinar si cada uno de sus cocientes lo es. De hecho, para hallar una orientación transitiva de un grafo de comparabilidad, es suficiente orientar transitivamente cada uno de sus cocientes en su descomposición modular (Gallai, 67; Möhring, 85). Un fenómeno similar se aplica a los grafos de permutación (McConnell y Spinrad '94), los grafos de intervalo (Hsu y Ma '99), los grafos perfectos y otras clases de grafos. Algunos problemas importantes de optimización combinatoria en grafos pueden resolverse utilizando una estrategia similar (Möhring, 85).

Los cografos son grafos 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 grafo se publicó en 1972 (James, Stanton y Cowan 1972) y ahora se dispone de algoritmos lineales (McConnell y Spinrad 1999, Tedder et al. 2007, Cournier y Habib 1994).

La descomposición modular de grafos dirigidos se puede realizar en tiempo lineal ( McConnell y de Montgolfier 2005 ) .

Con un pequeño número de excepciones simples, todo grafo con una descomposición modular no trivial también tiene una partición sesgada ( Reed 2008 ) .

• Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy P. (1999). Clases de grafos: una revisión . Sociedad de Matemáticas Industriales y Aplicadas. doi : 10.1137/1.9780898719796 . ISBN 978-0-89871-432-6.
• Gallai, Tibor (1967). "Grafeno transitivo orientado". 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 grafos para grafos no dirigidos". Actas de la 3.ª Conferencia Internacional del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Universidad Atlántica de Florida, Boca Ratón, Florida, 1972) . Universidad Atlántica de Florida . págs. 281–290 . MR 0351909 .  
• Golumbic, Martin C. (1980). Teoría algorítmica de grafos y grafos perfectos . Academic Press. ISBN 0-444-51530-5.
• Hsu, WL; Ma, T. (1999). "Algoritmos rápidos y sencillos para el reconocimiento de grafos de comparabilidad de cuerdas y grafos de intervalos". SIAM Journal on Computing . 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 . MR 1687819 . 
• Möhring, Rolf H. (1985). «Aspectos algorítmicos de los grafos de comparabilidad y los grafos de intervalos». En I. Rival (ed.). Grafos y orden . D. Reidel. pp. 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 la optimización sobre relaciones, sistemas de conjuntos y funciones booleanas". Annals of Operations Research . 4 : 195–225 . doi : 10.1007/BF02022041 . S2CID 119982014 . 
• Papadopoulos, Charis; Voglis, Constantinos (2005). «Dibujo de grafos mediante descomposición modular» (PDF) . Actas del XIII Simposio Internacional sobre Dibujo de Grafos (GD'05) . Lecture Notes in Computer Science. Vol.  3843. Springer-Verlag. pp. 343–354 . doi : 10.1007/11618058_31 . ISBN  978-3-540-31425-7MR 2229205 .​ 
• Reed, Bruce (2008). "Particiones sesgadas en grafos perfectos" . Matemáticas Aplicadas Discretas . 156 (7): 1150– 1156. doi : 10.1016/j.dam.2007.05.054 . MR 2404228 . 
• Spinrad, Jeremy P. (2003). Representaciones gráficas eficientes . Monografías del Fields Institute. Sociedad Matemática Americana. ISBN 0-8218-2815-0.
• Tedder, Marc; Corneil, Derek ; Habib, Michel; Paul, Christophe (2008). «Descomposición modular lineal más simple mediante permutaciones factorizantes recursivas». Actas del 35.º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP 2008) . Lecture Notes in Computer Science. Vol. 5125.  Springer-Verlag. pp. 634–645 . arXiv : 0710.3901 . doi : 10.1007/978-3-540-70575-8_52 . ISBN  978-3-540-70574-1.
• Zahedi, Emad; Smith, Jason (31 de julio de 2019). "Descomposición modular de grafos y la propiedad de preservación de la distancia" . Matemáticas Aplicadas Discretas . 265 (7): 192– 198. arXiv : 1805.09853 . Bibcode : 2018arXiv180509853Z . doi : 10.1016/j.dam.2019.03.019 .

• Implementación en Perl de un algoritmo de descomposición modular.
• Implementación en Java de un algoritmo de descomposición modular.
• Implementación en Julia de un algoritmo de descomposición modular.