Descomposición modular

La descomposición modular es la descomposición de un gráfico en subconjuntos de vértices, llamados módulos. Un módulo es una generalización de un componente conexo de un gráfico. Sin embargo, a diferencia de los componentes de conectividad, un módulo puede ser su propio subconjunto de otro. Los módulos, por lo tanto, conducen a una descomposición recursiva (jerárquica) del gráfico, no solo a particiones.

Existen variantes de descomposición modular para gráficos no dirigidos y gráficos dirigidos . Para cada gráfico no dirigido, tal descomposición es única.

La noción se puede generalizar a otras estructuras (como gráficos dirigidos) y es útil para desarrollar algoritmos eficientes para reconocer ciertas clases de gráficos, para encontrar orientaciones transitivas de gráficos de comparabilidad , para problemas de optimización en gráficos y para visualizar gráficos .

Módulos

El concepto de módulo ha sido redescubierto en muchas áreas. Para este concepto se utilizaron los nombres de conjuntos autónomos , conjuntos homogéneos , intervalos y conjuntos fraccionarios . Aparentemente, la primera mención y la primera descripción de cocientes modulares y la partición de gráficos que surgen en este caso fue en el artículo de Galai en 1967.

El módulo gráfico es una generalización de la componente conexa . Un componente conexo tiene la propiedad de que es un conjunto de vértices tal que ningún miembro es vecino de ningún vértice que no esté en . Una generalización será, es un módulo cuando, para cada vértice , cualquier miembro no es vecino o cualquier miembro es vecino .

De manera equivalente, es un módulo si todos los miembros tienen el mismo conjunto de vecinos entre los 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 su propio subconjunto de otro. Tenga en cuenta que el conjunto de vértices de un gráfico es un módulo, al igual que los conjuntos singleton y el conjunto vacío . Se llaman módulos triviales . El gráfico puede o no tener otros módulos. Un grafo se dice simple si todos sus módulos son triviales.

A pesar de las diferencias, los módulos conservan la propiedad deseada de los componentes conectados, que es que muchas propiedades del subgrafo generado por un componente conectado son independientes del resto del gráfico. Un fenómeno similar se observa para los subgrafos generados por módulos.

Por lo tanto, los módulos de grafos son de gran interés algorítmico. Se puede usar un conjunto de módulos anidados, de los cuales la expansión modular es un ejemplo, para obtener una solución recursiva a muchos problemas combinatorios en gráficos, como reconocer y encontrar la orientación transitiva de gráficos de comparabilidad , reconocer y encontrar la representación de permutación de gráficos de permutación. , reconociendo si un gráfico es un cografo , reconociendo gráficos de intervalos y encontrando una representación de intervalos para ellos, la definición de gráficos heredados de la distancia [1] y para la visualización de gráficos [2] . Desempeñan un papel importante en la demostración del teorema del gráfico perfecto [3] .

Para el reconocimiento de gráficos heredados de distancia y gráficos circulares , es especialmente útil una mayor generalización de la descomposición modular, llamada descomposición dividida [1] .

Para evitar la ambigüedad de la definición anterior, damos la siguiente definición formal de módulos. . es un módulo de un grafo si:

, y todos los singletons para son módulos y se llaman módulos triviales . Un grafo es simple si todos sus módulos son triviales. Los componentes de conectividad de un gráfico o sus complementos también son módulos de un gráfico .

es un módulo gráfico sólido si no se superpone (parcialmente) con ningún otro módulo gráfico ; el módulo gráfico es , o , o .

Cocientes modulares y factores

Si y son módulos disjuntos, es fácil ver que cualquier miembro es vecino de cualquier elemento de , o que ningún miembro es adyacente a ningún miembro de . Por lo tanto, todos los elementos de dos módulos que no se intersecan son adyacentes o no adyacentes . No existe un estado intermedio entre estos dos extremos.

En vista de esto, las descomposiciones modulares , donde cada clase de descomposición es un módulo, son de particular interés. Supongamos que es una descomposición modular. Dado que las clases de partición no se cruzan, su adyacencia forma un nuevo gráfico, el gráfico de cociente , cuyos vértices son los términos . Es decir, cada vértice es un módulo del grafo G, y la adyacencia de estos módulos define las aristas .

En la siguiente figura, el vértice 1, los vértices 2 a 4, el vértice 5, los vértices 6 y 7 y los vértices 8 a 11 son modulares. En el diagrama superior derecho, los bordes entre estos conjuntos muestran los cocientes dados por la descomposición dada, mientras que los bordes dentro de los conjuntos muestran los factores correspondientes.

Las particiones y son particiones modulares triviales . es un gráfico de un vértice, mientras que . Supongamos que es un módulo no trivial. Entonces el subconjunto de un elemento es también una partición modular no trivial . Por lo tanto, la existencia de módulos no triviales implica la existencia de particiones de módulos no triviales. En general, la mayoría o todos los miembros 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 terminan en diferentes clases de partición . Para cada subgráfico , la clase de partición generada por se llama factor y da una representación de todos los bordes con ambos extremos en . Por tanto, las aristas de una gráfica se pueden reconstruir si se conocen la gráfica del cociente y sus factores. El término gráfico simple proviene del hecho de que un gráfico simple tiene solo cocientes y factores triviales.

Si es un multiplicador del módulo cociente , puede resultar que se puede factorizar recursivamente y cocientes. Cada nivel de recursión produce un cociente. Como caso base, el gráfico tiene un vértice. El gráfico se puede reconstruir reconstruyendo factores desde abajo, invirtiendo los pasos de partición ensamblando factores con cocientes en cada nivel.

En la figura siguiente, dicha descomposición recursiva se representa como un árbol, que refleja una de las formas de factorizar recursivamente los factores de descomposición modular inicial en particiones modulares más pequeñas.

El método de partición recursiva de un gráfico en factores y cocientes puede no ser el único. (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 descomponer ese gráfico de forma recursiva). Algunas formas de descomposición pueden ser más útiles que otras.

Modularización

Afortunadamente, existe una descomposición recursiva de un gráfico que representa implícitamente todas las formas en que se puede descomponer. Esto es modularización. Es en sí mismo una forma de descomponer recursivamente un gráfico en cocientes, pero incluye todos los demás. La descomposición que se muestra en la siguiente figura es una descomposición especial del gráfico dado.

A continuación se muestra una observación clave para comprender la descomposición modular:

Si es un módulo del grafo y es un subconjunto de , entonces es un módulo si y solo si es un módulo de .

Gallai [4] definió una descomposición modular recursivamente en un gráfico con muchos vértices de la siguiente manera:

  1. En el caso base, si tiene un solo vértice, su descomposición modular es un árbol con un nodo.
  2. Gallai demostró que si es conexo y también lo es su complemento, entonces los módulos máximos, que son subconjuntos propios de , son una partición de . Por lo tanto, son modulares. Los cocientes que definen son simples. La raíz del árbol se marca como un nodo simple y estos módulos son aceptados por los descendientes del conjunto . Debido a que son maximales, cualquier módulo no representado de esta forma está contenido en el descendiente de . Para cada descendiente del conjunto, reemplazar el árbol de modularización con un árbol de descomposición modular da una representación de todos los módulos del gráfico, de acuerdo con la observación clave anterior.
  3. Si no es conexo, su complemento es conexo. Cualquier unión de componentes conectados es un módulo gráfico . Todos los demás módulos son subconjuntos de un componente de conectividad independiente. Esto representa todos los módulos excepto los subconjuntos de componentes de conectividad. Para cada componente, reemplazar con un árbol de descomposición modular da una representación de todos los módulos del gráfico de acuerdo con la observación clave anterior. La raíz del árbol está marcada como un nodo paralelo , pero es un hijo de la raíz. El cociente definido por el descendiente es el complemento del grafo completo.
  4. Si el complemento de la gráfica no es conexo, la gráfica es conexa. Los subárboles que son hijos de se definen simétricamente al caso donde el grafo no es conexo, ya que los módulos del grafo son los mismos que los módulos de su complemento. La raíz del árbol se etiqueta como un nodo secuencial y el cociente definido por los descendientes es el gráfico completo.

El árbol final tiene un conjunto único de vértices de gráficos como hojas, que son el caso base. Un conjunto de vértices de un gráfico es un módulo si y solo si es un nodo de árbol o una unión de descendientes de un nodo en serie o paralelo. Esto asigna implícitamente todas las expansiones modulares a la parte superior . En este sentido, el árbol de descomposición modular “concentra en sí mismo” todas las demás formas de descomponer recursivamente un grafo en parciales.

Problemas algorítmicos

La estructura de datos para representar un árbol de descomposición modular debe admitir operaciones que toman un nodo como entrada y devuelven el conjunto de vértices del gráfico que representa el nodo. La forma obvia de hacer esto es asignar a cada nodo una lista de vértices en el gráfico que representa el nodo. Dado un puntero a un nodo, el conjunto de vértices del gráfico que representa el nodo se puede recuperar en el tiempo . Sin embargo, dicha estructura requerirá memoria en el peor de los casos .

La alternativa de memoria se obtiene representando el árbol de descomposición modular con cualquier estructura de datos estándar basada en árboles con raíces y etiquetando cada hoja con el vértice del gráfico que representa. El conjunto representado por el nodo interno está definido por el conjunto de etiquetas de sus hojas descendientes. Es bien sabido que cualquier árbol con raíces y hojas tiene como máximo nudos internos. Puede utilizar la búsqueda en profundidad a partir de para obtener etiquetas de hojas descendientes en el momento .

Cada nodo es un conjunto de vértices en el gráfico y, si es un nodo interno, el conjunto de descendientes es una división , donde cada clase dividida es un módulo. Por lo tanto, generan un cociente en . Los vértices de este cociente son elementos de , por lo que se pueden representar estableciendo aristas entre los hijos de . Si y son dos términos y , , entonces y son adyacentes en si y sólo si y son adyacentes en el cociente. Para cualquier par de vértices de gráfico, esto está determinado por los descendientes privados del mayor ancestro común y en el árbol de descomposición modular. Por lo tanto, una descomposición modular etiquetada como cocientes de esta forma da una representación completa de la gráfica .

Muchos problemas combinatorios se pueden resolver en un gráfico resolviéndolos por separado para cada cociente. Por ejemplo, es un gráfico de comparabilidad si y solo si cada uno de estos cocientes es un gráfico de comparabilidad [4] [5] . Por lo tanto, para determinar si un gráfico es un gráfico de comparabilidad, basta comprobarlo para cada uno de sus cocientes. De hecho, para encontrar la orientación transitiva de un grafo de comparabilidad, basta con encontrar la orientación transitiva de cada uno de sus cocientes en la descomposición modular [4] [5] . Un fenómeno similar se encuentra para los gráficos de permutación [6] , gráficos de intervalos [7] , gráficos perfectos y otras clases de gráficos. Algunos problemas importantes de optimización combinatoria en grafos se pueden resolver usando estrategias similares [8] .

Los cographs son gráficos que tienen solo nodos paralelos o secuenciales en su árbol de descomposición modular.

El primer algoritmo de tiempo polinomial para calcular el árbol de descomposición modular de un gráfico se publicó en 1972 [9] , y los algoritmos de tiempo lineal ahora están disponibles [6] [10] .

Generalizaciones

La descomposición modular de gráficos dirigidos se puede obtener en tiempo lineal [11] .

Con algunas excepciones simples, cualquier gráfico con una descomposición modular no trivial también tiene una partición sesgada [12] .

Notas

  1. ↑ 12 Spinrad , 2003 .
  2. ↑ Papadopoulos, Voglis, 2005 .
  3. ↑ Golumbic, 1980 .
  4. ↑ 1 2 3 Gallai, 1967 , pág. 25–66.
  5. ↑ 12 Möhring , 1985a , pág. 41–101.
  6. ↑ 1 2 McConnell, Spinrad, 1999 , pág. 189–241.
  7. ↑ Hsu, Ma, 1999 , pág. 1004–1020.
  8. ↑ Möhring, 1985b , pág. 195–225.
  9. ↑ James, Stanton, Cowan, 1972 , pág. 281–290.
  10. ↑ Tedder, Corneil, Habib, Paul, 2008 , pág. 634–645.
  11. ↑ McConnell, de Montgolfier, 2005 , p. 198–209.
  12. ↑ Caña, 2008 .

Literatura

Enlaces