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.