Conectividade Aresta / Vértice

Definição

Dado um grafo não direcionado $G$ com $n$ vértices e $m$ arestas. Tanto a conectividade da aresta quanto a conectividade do vértice são características que descrevem o grafo.

Conectividade de aresta

A conectividade de aresta $\lambda$ do grafo $G$ é o número mínimo de arestas que precisam ser excluídas, de modo que o grafo $G$ seja desconectado.

Por exemplo, um grafo já desconectado tem uma conectividade de aresta de $0$, um grafo conectado com pelo menos uma ponte tem uma conectividade de aresta de $1$, e um grafo conectado sem pontes tem uma conectividade de aresta de pelo menos $2$.

Dizemos que um conjunto $S$ de arestas separa os vértices $s$ e $t$, se, após remover todas as arestas em $S$ do grafo $G$, os vértices $s$ e $t$ terminam em diferentes componentes conectados.

A conectividade de aresta de um grafo é igual ao tamanho mínimo de um conjunto que separa dois vértices $s$ e $t$, obtidos entre todos os pares possíveis $(s, t)$.

Conectividade de vértice

A conectividade de vértice $\kappa$ do grafo $G$ é o número mínimo de vértices que precisam ser excluídos, de modo que o grafo $G$ seja desconectado.

Por exemplo, um grafo já desconectado tem a conectividade de vértice $0$, e um grafo conectado com um ponto de articulação tem a conectividade de vértice $1$. Definimos que um grafo completo possui uma conectividade de vértice $n-1$. Para todos os outros grafos, a conectividade do vértice não excede $n-2$, porque você pode encontrar um par de vértices que não estão conectados por uma aresta e remover todos os outros $n-2$ vértices.

Dizemos que um conjunto $T$ de vértices separam os vértices $s$ e $t$, se, após remover todos os vértices em $T$ do grafo $G$, os vértices terminam em diferentes componentes conectados.

A conectividade de vértice de um grafo é igual ao tamanho mínimo de um conjunto que separa dois vértices $s$ e $t$, obtidos entre todos os pares possíveis $(s, t)$.

Propriedades

As desigualdades de Whitney

As desigualdades de Whitney (1932) fornecem uma relação entre a conectividade de aresta $\lambda$, a conectividade de vértice $\kappa$ e o menor grau dos vértices $\delta$: $$\kappa \le \lambda \le \delta$$

Intuitivamente, se tivermos um conjunto de arestas de tamanho $\lambda$ que desconectam o grafo, podemos escolher cada um dos pontos de extremidade, e criar um conjunto de vértices que também desconectam o grafo. E este conjunto terá tamanho $\le \lambda$.

E se escolhermos o vértice e o grau mínimo $\delta$, e removermos todas as arestas conectadas a ele, também terminaremos com um grafo desconectado. Portanto, a segunda desigualdade $\lambda \le \delta$.

É interessante notar que as desigualdades de Whitney não podem ser melhoradas: ou seja, para qualquer triplo de números que satisfaça essa desigualdade, existe pelo menos um grafo correspondente. Um desses grafos pode ser construído da seguinte maneira: ele irá consistir de $2(\delta + 1)$ vértices, os primeiros $\delta + 1$ vértices formam uma "panelinha" (todos os pares de vértices são conectados por uma aresta), e os segundos $\delta + 1$ vértices formam uma segunda panelinha. Além disso, conectamos as duas panelinhas com $\lambda$ arestas, de forma que são usados $\lambda$ vértices diferentes no primeiro grupo, e apenas $\kappa$ vértices no segundo. O grafo resultante terá as três características.

O teorema de Ford-Fulkerson

O teorema de Ford-Fulkerson implica que o maior número de caminhos disjuntos de arestas conectando dois vértices é igual ao menor número de arestas separando esses vértices.

Computando os valores

Conectividade de aresta usando o fluxo máximo

Este método é baseado no teorema de Ford-Fulkerson.

Nós iteramos sobre todos os pares de vértices $(s, t)$ e, entre cada par, encontramos o maior número de caminhos disjuntos entre eles. Esse valor pode ser encontrado usando um algoritmo de fluxo máximo: usamos $s$ como fonte, $t$ como coletor e atribuímos a cada aresta uma capacidade de $1$. Então o fluxo máximo é o número de caminhos disjuntos.

A complexidade do algoritmo usando Edmonds-Karp é $O(V^2 V E^2) = O(V^3 E^2)$. Mas devemos observar que isso inclui um fator oculto, uma vez que é praticamente impossível criar um grafo de modo que o algoritmo de fluxo máximo seja lento para todas as fontes e coletores/sinks. Especialmente, o algoritmo será executado muito rápido para grafos aleatórios.

Algoritmo especial para conectividade de aresta

A tarefa de encontrar a conectividade de aresta é igual a tarefa de encontrar o corte mínimo global.

Algoritmos especiais foram desenvolvidos para esta tarefa. Um deles é o algoritmo de Stoer-Wagner, que funciona em tempo $O(V^3)$ ou $O(V E)$.

Conectividade de vértice

Novamente, iteramos sobre todos os pares de vértices $s$ e $t$, e para cada par encontramos o número mínimo de vértices que separam $s$ e $t$.

Ao fazer isso, podemos aplicar a mesma abordagem de fluxo máximo, conforme descrito nas seções anteriores.

Dividimos cada vértice $x$ com $x \neq s$ e $x \neq t$ em dois vértices: $x_1$ e $x_2$. Conectamos esses dois vértices com uma aresta direcionada $(x_1, x_2)$ com a capacidade $1$, e substituímos todas as arestas $(u, v)$ pelas duas arestas direcionadas $(u_2, v_1)$ e $(v_2, u_1)$, ambos com capacidade de 1. Na construção, o valor do fluxo máximo será igual ao número mínimo de vértices necessários para separar $s$ e $t$.

Essa abordagem tem a mesma complexidade que a abordagem de fluxo para encontrar a conectividade de aresta.