Componente débil

Partición de vértices de un grafo dirigido

En teoría de grafos , los componentes débiles de un grafo dirigido dividen los vértices del grafo en subconjuntos que están totalmente ordenados por accesibilidad . Forman la partición más fina del conjunto de vértices que está totalmente ordenado de esta manera.

Definición

Los componentes débiles fueron definidos en un artículo de 1972 por Ronald Graham , Donald Knuth y (póstumamente) Theodore Motzkin , por analogía con los componentes fuertemente conectados de un grafo dirigido, que forman la partición más fina posible de los vértices del grafo en subconjuntos que están parcialmente ordenados por alcanzabilidad. En cambio, definieron los componentes débiles como la partición más fina de los vértices en subconjuntos que están totalmente ordenados por alcanzabilidad. ^{[1] [2]}

Con más detalle, Knuth (2022) define los componentes débiles a través de una combinación de cuatro relaciones simétricas en los vértices de cualquier gráfico dirigido, denotados aquí como , , , y : ${\displaystyle \Leftrightarrow }$ ${\displaystyle \parallel }$ ${\displaystyle \approx }$ ${\displaystyle \asymp }$

• Para dos vértices cualesquiera y del grafo, si y solo si cada vértice es alcanzable desde el otro: existen caminos en el grafo desde a y desde a . La relación es una relación de equivalencia y sus clases de equivalencia se utilizan para definir los componentes fuertemente conectados del grafo. ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u\Leftrightarrow v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle \Leftrightarrow }$
• Para cualesquiera dos vértices y del grafo, si y sólo si ninguno de los vértices es alcanzable desde el otro: no existen caminos en el grafo en ninguna dirección entre y . ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u\parallel v}$ ${\displaystyle u}$ ${\displaystyle v}$
• Para dos vértices cualesquiera y del grafo, si y solo si o . Es decir, puede haber una conexión bidireccional entre estos vértices, o pueden ser mutuamente inalcanzables, pero pueden no tener una conexión unidireccional. ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u\approx v}$ ${\displaystyle u\Leftrightarrow v}$ ${\displaystyle u\parallel v}$
• La relación se define como el cierre transitivo de . Es decir, cuando existe una secuencia de vértices, que empiezan con y terminan con , de modo que cada par consecutivo de la secuencia está relacionado por . ${\displaystyle \asymp }$ ${\displaystyle \approx }$ ${\displaystyle u\asymp v}$ ${\displaystyle u\approx \cdots \approx v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle \approx }$

Entonces es una relación de equivalencia: cada vértice está relacionado consigo mismo por (porque puede alcanzarse a sí mismo en ambas direcciones por caminos de longitud cero), dos vértices cualesquiera que estén relacionados por pueden intercambiarse entre sí sin cambiar esta relación (porque se construye a partir de las relaciones simétricas y ), y es una relación transitiva (porque es un cierre transitivo). Como con cualquier relación de equivalencia, se puede utilizar para dividir los vértices del grafo en clases de equivalencia, subconjuntos de los vértices tales que dos vértices están relacionados por si y solo si pertenecen a la misma clase de equivalencia. Estas clases de equivalencia son los componentes débiles del grafo dado . ^[2] ${\displaystyle \asymp }$ ${\displaystyle \asymp }$ ${\displaystyle \asymp }$ ${\displaystyle \asymp }$ ${\displaystyle \Leftrightarrow }$ ${\displaystyle \parallel }$ ${\displaystyle \asymp }$ ${\displaystyle \asymp }$

La definición original de Graham, Knuth y Motzkin es equivalente, pero formulada de forma algo diferente. Dado un grafo dirigido , ${\displaystyle G}$ primero construyen otro grafo como el grafo complementario del cierre transitivo de . Como describe Tarjan (1974), las aristas en representan caminos no , pares de vértices que no están conectados por un camino en . ^[3] Entonces, dos vértices pertenecen al mismo componente débil cuando pertenecen al mismo componente fuertemente conectado de o de . ^{[1] [3]} Como muestran Graham, Knuth y Motzkin, esta condición define una relación de equivalencia, ^[1] la misma definida anteriormente como . ^[4] ${\displaystyle {\hat {G}}}$ ${\displaystyle G}$ ${\displaystyle {\hat {G}}}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle {\hat {G}}}$ ${\displaystyle \asymp }$

De acuerdo con estas definiciones, un grafo dirigido se denomina débilmente conexo si tiene exactamente un componente débil. Esto significa que sus vértices no se pueden dividir en dos subconjuntos, de modo que todos los vértices del primer subconjunto puedan alcanzar todos los vértices del segundo subconjunto, pero ninguno de los vértices del segundo subconjunto pueda alcanzar ninguno de los vértices del primer subconjunto. Se diferencia de otras nociones de conectividad débil en la literatura, como la conectividad y los componentes en el grafo no conexo subyacente, para los cuales Knuth sugiere la terminología alternativa de componentes no dirigidos . ^[2]

Propiedades

Si y son dos componentes débiles de un grafo dirigido, entonces o bien todos los vértices en pueden alcanzar todos los vértices en por caminos en el grafo, o bien todos los vértices en pueden alcanzar todos los vértices en . Sin embargo, no pueden existir relaciones de alcanzabilidad en ambas direcciones entre estos dos componentes. Por lo tanto, podemos definir un ordenamiento en los componentes débiles, según el cual cuando todos los vértices en pueden alcanzar todos los vértices en . Por definición, . Esta es una relación asimétrica (dos elementos solo pueden estar relacionados en una dirección, no en la otra) y hereda la propiedad de ser una relación transitiva de la transitividad de la alcanzabilidad. Por lo tanto, define un ordenamiento total en los componentes débiles. Es la partición más fina posible de los vértices en un conjunto totalmente ordenado de vértices consistente con la alcanzabilidad. ^[1] ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle X<Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X\nless X}$

Este ordenamiento de los componentes débiles puede interpretarse alternativamente como un ordenamiento débil de los propios vértices, con la propiedad de que cuando se está en el ordenamiento débil, necesariamente existe un camino desde a , pero no desde a . Sin embargo, esta no es una caracterización completa de este ordenamiento débil, porque dos vértices y podrían tener este mismo ordenamiento de alcanzabilidad aunque pertenezcan al mismo componente débil entre sí . ^[2] ${\displaystyle u<v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle v}$

Cada componente débil es una unión de componentes fuertemente conectados. ^[2] Si los componentes fuertemente conectados de cualquier grafo dado se contraen a vértices individuales, produciendo un grafo acíclico dirigido (la condensación del grafo dado), y luego esta condensación se ordena topológicamente , entonces cada componente débil aparece necesariamente como una subsecuencia consecutiva del orden topológico de los componentes fuertes. ^[3]

Algoritmos

Pacault (1974) describió un algoritmo para calcular los componentes débiles de un grafo dirigido dado en tiempo lineal , que posteriormente fue simplificado por Tarjan (1974) y Knuth (2022). ^{[2] [3] [5]} Como observa Tarjan, el algoritmo de componentes fuertemente conectados de Tarjan basado en la búsqueda en profundidad generará los componentes fuertemente conectados en (el orden inverso de) un orden topológico ordenado. El algoritmo para componentes débiles genera los componentes fuertemente conectados en este orden y mantiene una partición de los componentes que se han generado hasta ahora en los componentes débiles de su subgrafo inducido . Una vez que se generan todos los componentes, esta partición describirá los componentes débiles de todo el grafo. ^{[2] [3]}

Es conveniente mantener la partición actual en componentes débiles en una pila , con cada componente débil manteniendo adicionalmente una lista de sus fuentes , componentes fuertemente conectados que no tienen aristas entrantes de otros componentes fuertemente conectados en el mismo componente débil, con la fuente generada más recientemente primero. Cada componente fuertemente conectado recién generado puede formar un nuevo componente débil por sí solo, o puede terminar fusionado con algunos de los componentes débiles construidos previamente cerca de la parte superior de la pila, aquellos para los que no puede alcanzar todas las fuentes. ^{[2] [3]}

Así, el algoritmo realiza los siguientes pasos: ^{[2] [3]}

• Inicializa una pila vacía de componentes débiles, cada uno asociado con una lista de sus componentes de origen.
• Utilice el algoritmo de componentes fuertemente conectados de Tarjan para generar los componentes fuertemente conectados del gráfico dado en orden topológico inverso. Cuando se genere cada componente fuertemente conectado, realice los siguientes pasos con él: ${\displaystyle S}$
  • Mientras la pila no esté vacía y no tenga bordes hacia el componente débil superior de la pila, extraiga ese componente de la pila. ${\displaystyle S}$
  • Si la pila aún no está vacía, y algunas fuentes de su componente débil superior no son alcanzadas por los bordes de , ${\displaystyle S}$ saque nuevamente ese componente de la pila.
  • Construya un nuevo componente débil , ${\displaystyle W}$ que contenga fuentes como y todas las fuentes no impactadas del componente superior que se eliminó, y empújelo hacia la pila. ${\displaystyle S}$ ${\displaystyle W}$

Cada prueba para determinar si algún borde golpea un componente débil se puede realizar en tiempo constante una vez que encontramos un borde hacia el componente fuertemente conectado anteriormente generado más recientemente, comparando el componente de destino de ese borde con la primera fuente del segundo componente desde arriba en la pila. ${\displaystyle S}$ ${\displaystyle S}$

Referencias

1. Graham, RL ; Knuth, DE ; Motzkin, TS (1972), "Complementos y clausuras transitivas" (PDF) , Discrete Mathematics , 2 : 17–29, doi :10.1016/0012-365X(72)90057-X, MR  0323577
2. Knuth, Donald E. (15 de enero de 2022), "Componentes débiles", El arte de la programación informática, volumen 4, prefascículo 12A: Componentes y recorrido (PDF) , págs. 11-14
3. Tarjan, Robert Endre (julio de 1974), "Un nuevo algoritmo para encontrar componentes débiles", Information Processing Letters , 3 (1): 13–15, doi :10.1016/0020-0190(74)90040-4
4. Knuth (2022), Ejercicio 81, pág. 21.
5. Pacault, Jean François (1974), "Cálculo de los componentes débiles de un gráfico dirigido", SIAM Journal on Computing , 3 : 56–61, doi :10.1137/0203005, MR  0376418