OIA-Wiki

En grafos dirigidos, una componente fuertemente conexa (SCC por sus siglas en inglés, “Strongly Connected Component) es un conjunto de nodos y aristas del grafo que cumplen 2 condiciones:

• Desde cada nodo de la componente existe un camino hacia todos los otros nodos que usa aristas únicamente de la componente.
• No hay un nodo del grafo fuera de la componente desde el cual se pueda llegar a la componente y al que se pueda llegar desde ella (es “maximal”, si existiera estaría en la componente).

Ejemplo:

Algo súper interesante, es que si tratamos a cada SCC como un nodo, y las aristas van de una SCC a otra si y sólo si hay una arista desde un nodo de la primera SCC hacia un nodo de la segunda, entonces en este nuevo grafo no hay ciclos! Si lo hubiera, significaría que las SCCs del ciclo pueden llegar de cualquiera a cualquiera, por lo que sería todo el ciclo una misma SCC.

Entonces, tenemos un ordenamiento topológico.

La aplicación típica es el problema de 2-SAT, 2-satisfiability. El problema consiste en, dadas $n$ variables $x_1, x_2, \ldots, x_n$ true/false y una concatenación por medio de “ands” de varios paréntesis con un “or” entre dos variables, decir si existen valores de asignación de variables tal que se cumpla la condición (que los ands sean true).

Por ejemplo:

$(x_1\ or\ x_2)\ and\ (x_1\ or\ x_3)\ and\ (x_1\ or\ ¬x_2)$, donde $¬x$ representa la negación de la varibale $x$. En este ejemplo es fácil ver que si asignamos $x_1=true$, al estar en todos los paréntesis, todos los paréntesis darán true sin importar el valor del otro término de los mismos, y la condición será verdadera.

Otro ejemplo:

$(x_1\ or\ x_2)\ and\ (¬x_1\ or\ x_2)\ and\ (x_1\ or\ ¬x_2)\ and\ (¬x_1\ and\ ¬x_2)$ Puede verse acá que es imposible satisfacer la condición: Si $x_1$ es verdadera, por el segundo paréntesis $x_2$ también debe serlo y el último da false. Y si $x_1$ es falsa, por el tercero $x_2$ también debe ser falsa y no se cumple el primero.

Pero qué pasa cuando hay muchas variables y no es un sistema tan fácil?

$(x_1\ or\ x_2)\ and\ (x_2\ or\ ¬x_3)\ and\ (¬x_1\ or\ x_4)\ and\ (¬x_4\ or\ x_5)\ and\ (x_5\ or\ ¬x_1)\ and$ $(x_1\ or\ x_6)\ and\ (x_6\ or\ ¬x_3)\ and\ (x_7\ or\ x_8)\ and\ (x_6\ or\ ¬x_8)$.

(Se recomienda asegurarse de haber entendido el problema y pensar un poco el problema. Pensar qué pasa cuando una variable aparece en un sólo paréntesis. Qué pasa un conjunto de variables sólo aparece en paréntesis con otras variables de este conjunto y con ninguna más.) ....

Qué pasa si planteamos un grafo, con dos nodos por variable, una para la variable y otro para su negación, y al ver un paréntesis $(a or b)$ trazamos una flecha del nodo de $~a$ a $b$ y de $~b$ a $a$? La flecha es como la flecha de “implica” en matemática/lógica: Si se cumple ~a, entonces para satisfacer el paréntesis en cuestión se debe cumplir $b$. Y si el paréntesis no se satisface como está en un “and” será imposible satisfacer todo, por lo que debemos satisfacer cada paréntesis.

Entonces, si podemos asignar valores tal que no se cumpla que $a$ y $~a$ deban tener el mismo valor, asignamos los valores y listo. Caso contrario, no será posible satisfacer la condición.

Como el título de este post puede haberles dado la idea, vamos a encontrar esto con SCC! Si $x_i$ y $~x_i$ pertenecen a la misma SCC, el problema será imposible de satisfacer, ya que indica que si $x_i$ es verdadera, $~x_i$ también debe serlo. Y si $x_i$ es falsa, $~x_i$ es verdadera y como están en la misma SCC hay un camino hasta $x_i$, por lo que $x_i$ debe ser verdadera.

Veamos que lo que podemos hacer, gracias al toposort que sabemos que existe usando las SCCs como nodos, es pensar en ubicar las SCCs en una fila, donde no hay una arista de una SCC que está más adelante a una que está más atrás, y entonces vamos desde adelante hacia atrás recorriendo las SCCs del orden topológico. Si ninguna variable de la SCC actual tiene valor asignado, le asignamos a todas las variables de la SCC el valor de verdadera, lo que hace que debamos asignar falso a todas las negaciones de estas variables, y a todas las SCCs que van hacia las false, ya que no puede haber una flecha de una SCC true a una false. Notar que vamos de adelante hacia atrás porque setear en true una SCC de adelante, de la que no salen flechas, no impone restricciones.

Para encontrar las SCCs de un grafo dirigido, vamos a hacer dos DFSs.

Primero un DFS en el grafo dado, marcando el tiempo de finalización de cada nodo. Qué es el tiempo de finalización de un nodo? Es la cantidad de operaciones que hicimos de visitar un nodo/terminar de visitar un nodo (cuando vimos todos sus vecinos y vamos a volver “hacia atrás” en el DFS) antes de terminar de visitar este nodo. Puede haber varias posibles asignaciones de tiempos de finalización, dependiendo de por dónde empecemos, qué vecino visitemos primero, etcétera. Por ejemplo en el siguiente grafo:

foto y recorrido

Luego de tener los tiempos de finalización, vamos a invertir el grafo. No hace falta invertirlo, podemos tener otro grafo con las aristas apuntando al revés que el grafo inicial. En este grafo vamos a ir desde el nodo de tiempo de finalización más grande hasta el más chico, recorriendo los nodos, e iniciando un dfs en cada nodo todavía no visitado. Todos los nodos a los que llegue este segundo dfs estarán en la misma SCC.

Una manera de marcar esto es asignar un “líder” de la SCC, como un nodo de referencia para saber a qué SCC pertenecen/si pertenecen a la misma. También podemos asignarles a estos nodos un número de componente, que aumente al encontrar una nueva.

Código