Conectividad de aristas / Conectividad de vértices

Definición

Dado un grafo no dirigido $G$ con $n$ vértices y $m$ aristas. Tanto la conectividad de aristas como la conectividad de vértices son características que describen el grafo.

Conectividad de aristas

La conectividad de aristas $\lambda$ del grafo $G$ es el número mínimo de aristas que hay que borrar para que el grafo $G$ se desconecte.

Por ejemplo, un grafo ya desconectado tiene conectividad de aristas $0$, un grafo conexo con al menos un puente tiene conectividad de aristas $1$, y un grafo conexo sin puentes tiene conectividad de aristas de al menos $2$.

Decimos que un conjunto $S$ de aristas separa los vértices $s$ y $t$ si, después de quitar todas las aristas de $S$ del grafo $G$, los vértices $s$ y $t$ quedan en componentes conexas distintas.

Está claro que la conectividad de aristas de un grafo es igual al tamaño mínimo de un conjunto que separa dos vértices $s$ y $t$, tomado entre todos los pares posibles $(s, t)$.

Conectividad de vértices

La conectividad de vértices $\kappa$ del grafo $G$ es el número mínimo de vértices que hay que borrar para que el grafo $G$ se desconecte.

Por ejemplo, un grafo ya desconectado tiene conectividad de vértices $0$, y un grafo conexo con un punto de articulación tiene conectividad de vértices $1$. Definimos que un grafo completo tiene conectividad de vértices $n-1$. Para todos los demás grafos la conectividad de vértices no supera $n-2$, porque se puede encontrar un par de vértices que no están conectados por una arista y quitar los otros $n-2$ vértices.

Decimos que un conjunto $T$ de vértices separa los vértices $s$ y $t$ si, después de quitar todos los vértices de $T$ del grafo $G$, los vértices quedan en componentes conexas distintas.

Está claro que la conectividad de vértices de un grafo es igual al tamaño mínimo de un conjunto que separa dos vértices $s$ y $t$, tomado entre todos los pares posibles $(s, t)$.

Propiedades

Las desigualdades de Whitney

Las desigualdades de Whitney (1932) dan una relación entre la conectividad de aristas $\lambda$, la conectividad de vértices $\kappa$ y el grado mínimo de cualquier vértice del grafo $\delta$:

$$\kappa \le \lambda \le \delta$$

Intuitivamente, si tenemos un conjunto de aristas de tamaño $\lambda$ que desconectan el grafo, podemos elegir uno de cada extremo y crear un conjunto de vértices que también desconecte el grafo. Y ese conjunto tiene tamaño $\le \lambda$.

Y si elegimos el vértice de grado mínimo $\delta$ y quitamos todas las aristas conectadas a él, también terminamos con un grafo desconectado. De ahí la segunda desigualdad $\lambda \le \delta$.

Es interesante notar que las desigualdades de Whitney no se pueden mejorar: es decir, para cualquier terna de números que satisfaga esta desigualdad existe al menos un grafo correspondiente. Un grafo así se puede construir de la siguiente manera: El grafo consistirá de $2(\delta + 1)$ vértices; los primeros $\delta + 1$ vértices forman una clique (todos los pares de vértices están conectados por una arista), y los segundos $\delta + 1$ vértices forman una segunda clique. Además conectamos las dos cliques con $\lambda$ aristas, de modo que usen $\lambda$ vértices distintos en la primera clique, y solo $\kappa$ vértices en la segunda clique. El grafo resultante tendrá las tres características.

El teorema de Ford-Fulkerson

El teorema de Ford-Fulkerson implica que el mayor número de caminos disjuntos en aristas que conectan dos vértices es igual al menor número de aristas que separan esos vértices.

Computar los valores

Conectividad de aristas usando flujo máximo

Este método se basa en el teorema de Ford-Fulkerson.

Iteramos sobre todos los pares de vértices $(s, t)$ y entre cada par encontramos el mayor número de caminos disjuntos entre ellos. Este valor se puede encontrar usando un algoritmo de flujo máximo: usamos $s$ como fuente, $t$ como sumidero, y asignamos a cada arista capacidad $1$. Entonces el flujo máximo es el número de caminos disjuntos.

La complejidad del algoritmo usando Edmonds-Karp es $O(V^2 V E^2) = O(V^3 E^2)$. Pero hay que notar que esto incluye un factor oculto, porque es prácticamente imposible crear un grafo tal que el algoritmo de flujo máximo sea lento para todas las fuentes y sumideros. En especial el algoritmo corre bastante rápido para grafos aleatorios.

Algoritmo especial para conectividad de aristas

La tarea de encontrar la conectividad de aristas es igual a la tarea de encontrar el corte mínimo global.

Se desarrollaron algoritmos especiales para esta tarea. Uno de ellos es el algoritmo de Stoer-Wagner, que trabaja en $O(V^3)$ o $O(V E + V^2 \log V)$.

Conectividad de vértices

De nuevo iteramos sobre todos los pares de vértices $s$ y $t$, y para cada par encontramos el número mínimo de vértices que separan $s$ y $t$.

Haciendo esto, podemos aplicar el mismo enfoque de flujo máximo descrito en las secciones anteriores.

Partimos cada vértice $x$ con $x \neq s$ y $x \neq t$ en dos vértices $x_1$ y $x_2$. Conectamos estos dos vértices con una arista dirigida $(x_1, x_2)$ de capacidad $1$, y reemplazamos todas las aristas $(u, v)$ por las dos aristas dirigidas $(u_2, v_1)$ y $(v_2, u_1)$, ambas con capacidad 1. Por construcción, el valor del flujo máximo será igual al número mínimo de vértices necesarios para separar $s$ y $t$.

Este enfoque tiene la misma complejidad que el enfoque de flujo para encontrar la conectividad de aristas.