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:

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.