Conectividade (teoria dos grafos)

Na matemática e na ciência da computação, conectividade é um dos conceitos básicos da teoria dos grafos: que fala sobre o número minimo de elementos (vértices ou arestas) que precisam ser removidos para desconectar os vértices restantes uns dos outros. É um tema fortemente ligado a teoria dos problemas de fluxo de redes. A conectividade de um grafo é uma importante medida da robustez de uma rede.

Definições dos componentes, cortes e conectividade

Em um grafo não-direcionado G, dois vértices u e v são ditos conectados se G contém um caminho de u para v. Senão, eles são chamados de desconetados. Se além disso esses vértices forem conetados por um caminho de tamanho 1, i.e.por uma única aresta, eles são chamados de vértices adjacentes. Um grafo é dito conexo se todos os pares de vértices estão ligados por um caminho.

Um componente conexo é um subgrafo maximal conexo de G. Cada vértice pertence a exatamente um componente conexo, e o mesmo é valido para as arestas.

Um grafo orientado é chamado de conectado se a substituição de todas as suas arestas direcionadas com arestas não direcionadas produz um grafo (não-direcionado) conectado. Ele é chamado de fracamente conexo se possui um caminho direcionado de u para v ou um caminho direcionado de v para u para cada par de vértices u, v. Ele é fortemente conexo se contém um caminho direto de u para v e um caminho direto v para u para cada par de vértices u, v. Os componentes fortemente conexos são os subgrafos maximais fortemente conectados.

Um vértice de corte ou conjunto separador de um grafo conexo G é um conjunto de vértices que quando removidos torna G desconexo. A conectividade ou conectividade do vertice κ(G) (onde G não é um grafo completo) é o tamanho mínimo de um vértice de corte. Um grafo é chamado de k-conexo ou k-vértice-conexo se a conectividade dos vértices é k ou maior. Isso significa que um grafo G é dito k-conectado se não existe nenhum conjunto de tamanho k-1 de vértices que quando removidos desconectam o grafo. Um grafo completo com n vértices, escrito como $K_{n}$, não possui vértices de corte, mas por convenção κ($K_{n}$) = n-1. O vértice de corte de dois vértices u e v é um conjunto de vértices que quando removidos do grafo desconectam u e v. A conectividade local κ(u, v) é o tamanho do menor conjunto separador separando u e v. Conectividade local é simetrica para grafos não-direcionados; ou seja κ(u,v)=κ(v,u). Entretanto, a não ser pelos grafos completos, κ(G) igual ao minimo de κ(u,v) para todos os pares de vértice não adjacentes u, v.

2-conectividade também é chamada de biconectividade e 3-conectividade é também chamada de triconectividade.

Conceitos analogos podem ser definidos para arestas. Em um caso onde simplesmente cortar uma simples e especifica aresta poderia desconectar o grafo, essa aresta é chamada de ponte. De forma mais geral, a aresta de corte de G é um grupo de arestas que quando removidas tornam o grafo desconectado. A aresta-conectividade λ(G) é o tamanho do menor conjunto separador, e a aresta-conectividade local λ(u,v) de dois vértices u, v é o menor vértice de corte desconectando u de v. Novamente, aresta=conectividade local é simetrica. Um grafo é chamado de k-aresta-conexo se a conectividade de suas arestas for k ou maior.

Teorema de Menger

Um dos mais importantes fatos sobre conectividade em grafo é o teorema de Menger, que caracteriza a conectividade e a aresta-conectividade de um grafo em termos do número de caminhos independentes entre os vértices.

Se u e v são vértices de um grafo G, então o conjunto de caminhos entre u e v é chamado de independente se nenhum dos caminhos compartilha vértices (que não sejam u e v). De forma similar, o conjuto de caminhos é dito aresta-independentes se não há dois caminhos que compartilhem uma aresta. O número de caminhos mutualmente independentes entre u e v é escrito como κ′(u,v), e o número de caminhos mutualmente aresta-independentes entre u e v é escrito como λ′(u,v).

O teorema de Menger afirma que a conectividade local κ(u,v) é igual a κ′(u,v) e a aresta-conectividade local λ(u,v) é igual a λ′(u,v) para cada par de vértices u e v. Esse fato é na realidade um caso especial do Teorema do Fluxo Máximo–Corte Mínimo.

Aspectos computacionais

O problema de determinar quando dois vértices em um grafo estão conectados pode ser resolvido eficientemente usando um Algoritmo de busca, como o de Busca em largura. De forma mais geral, é fácil determinar computacionalmente quando um grafo está conectado (por exemplo, usando um conjunto disjunto de estrutura de dados), ou para determinar o número de componentes conexos. Por exemplo esse simples algoritimo escrito em Pseudocódigo:

1. Comece em um nó arbitrário do grafo, G.
2. A partir desse nó faça uma busca em profundidade ou uma busca em largura, contando todos nós alcançados.
3. Quando a busca tiver terminado de passar por todo grafo, se o número de nós contados for igual ao número de nós em G, o grafo é conexo; caso contrario ele é desconexo.

Pelo teorema de Menger, para quaisquer dois vértices u e v em um grafo conexo G, os números κ(u,v) e λ(u,v) podem ser eficientemente determinados usando um algoritimo de Fluxo Máximo–Corte Mínimo. A conectividade e a aresta-conectividade de G pode ser computada como os valores mínimos de κ(u,v) e λ(u,v), respectivamente.

Em teoria da complexidade computacional, SL é a classe de problemas de Redução em espaço logarítmico para o problema de determinar se dois vértices em um grafo estão conectados, que foi provado como sendo igual a classe de problemas L por Omer Reingold em 2004. Consequentemente, conectividade em grafos não-direcionados podem ser resolvidos com espaço $O(\log n)$.

O problema de computar a probabilidade de que um grafo aleatorio de Bernoulli é conexo é chamado de confiabilidade da rede e o problema de computar se dois vértices estão conectados é chamado de problema de confiabilidade-ST.

Exemplos

• A vértice- e aresta-conectividade de uma grafo desconexo são ambas 0.
• 1-conectividade é sinonimo de conectividade.
• O Grafo completo de n vértices tem aresta-conectividade igual a n − 1. Qualquer outro grafo simples com n vértices possui uma aresta-conectividade estritamente menor.
• Em uma árvore, a aresta-conectividade local entre qualquer par de vértices é 1.

Limites da conectividade

• A vértice-conectividade de um grafo é menor ou igual a sua aresta-conectividade. Ou seja, κ(G) ≤ λ(G). Ambos são menores ou iguais ao grau minimo do grafo, pois deletando todos os vizinhos do vértice de grau minimo irá desconectar o vértice do resto do grafo.

• Para o Grafo vértice-transitivo de grau d, nos temos: 2(d+1)/3 ≤ κ(G) ≤ λ(G) = d.

• Para o Grafo vértice-transitivo de grau d ≤ 4, ou para qualquer (não-direcionado) minimal Grafo de Cayley de grau d, ou para qualquer Grafo simétrico de grau d, ambos os tipos de conectividade são iguais: κ(G) = λ(G) = d.

Outras propriedades

• Conectividade é preservada por Homomorfismo de grafos.

• Se G é conexo então seu grafo linha L(G) também é conexo.

• Um grafo G é 2-aresta-conexo Se e somente se ele tem uma orientação que é fortemente conexa.

• O teorema de Balinski afirma que o grafo politopal (1-esqueleto) de um Polítopo conexo de $k$-dimensões é um grafo $k$-vértice-conexo. Como uma conversão parcial, Steinitz mostrou que qualquer Grafo planar 3-vértice-conexo é um grafo politopal (Teorema de Steinitz).

• De acordo com o teorema de G. A. Dirac, se um grafo é k-conexo para k ≥ 2,então para cada conjunto de k vértices no grafo existe um ciclo que passa por todos os vértices desse conjunto.

Veja também

• Conectividade algébrica
• Redes livres de escala
• Redes de pequeno mundo, Teoria dos seis graus de separação