Conectividade (teoria dos grafos) - Connectivity (graph theory)

Este gráfico se desconecta quando o nó mais à direita na área cinza à esquerda é removido
Este gráfico se desconecta quando a borda tracejada é removida.

Em matemática e ciência da computação , a conectividade é um dos conceitos básicos da teoria dos grafos : ela pede o número mínimo de elementos (nós ou arestas) que precisam ser removidos para separar os nós restantes em dois ou mais subgrafos isolados . Está intimamente relacionado à teoria dos problemas de fluxo de rede . A conectividade de um gráfico é uma medida importante de sua resiliência como rede.

Vértices e gráficos conectados

Com o vértice 0, este gráfico é desconectado. O resto do gráfico está conectado.

Em um gráfico undirected G , de dois vértices de u e v são chamados ligado se G contém um caminho de u para v . Caso contrário, eles são chamados de desconectados . Se os dois vértices são adicionalmente conectados por um caminho de comprimento 1 , ou seja, por uma única aresta, os vértices são chamados de adjacentes .

Diz-se que um gráfico está conectado se cada par de vértices do gráfico estiver conectado. Isso significa que existe um caminho entre cada par de vértices. Um gráfico não direcionado que não está conectado é denominado desconectado . Um grafo não direcionado G é, portanto, desconectado se houver dois vértices em G de forma que nenhum caminho em G tenha esses vértices como pontos finais. Um gráfico com apenas um vértice está conectado. Um gráfico sem arestas com dois ou mais vértices está desconectado.

Um gráfico direcionado é denominado fracamente conectado se a substituição de todas as suas arestas direcionadas por arestas não direcionadas produzir um gráfico conectado (não direcionado). Ele é conectado unilateralmente ou unilateral (também chamado de semicconectado ) se contiver um caminho direcionado de u para v ou um caminho direcionado de v para u para cada par de vértices u, v . É fortemente conectado , ou simplesmente forte, se contiver um caminho direcionado de u para v e um caminho direcionado de v para u para cada par de vértices u, v .

Componentes e cortes

Um componente conectado é um subgráfico conectado máximo de um gráfico não direcionado. Cada vértice pertence a exatamente um componente conectado, assim como cada aresta. Um gráfico é conectado se e somente se tiver exatamente um componente conectado.

Os componentes fortes são os subgráficos máximos fortemente conectados de um gráfico direcionado.

Um corte de vértice ou conjunto de separação de um grafo conectado G é um conjunto de vértices cuja remoção torna G desconectado. A conectividade do vértice κ ( G ) (onde G não é um gráfico completo ) é o tamanho de um corte mínimo do vértice. Um gráfico é chamado de k -vertex conectado ou k -conectado se sua conectividade de vértice for k ou maior.

Mais precisamente, qualquer gráfico G (completo ou não) é chamado de k -vertex-conectado se contiver pelo menos k +1 vértices, mas não contiver um conjunto de k - 1 vértices cuja remoção desconecta o gráfico; e κ ( G ) é definido como o maior k tal que G é conectado em k . Em particular, um gráfico completo com n vértices, denotado K n , não tem nenhum corte de vértice, mas κ ( K n ) = n - 1 .

Um corte de vértice de dois vértices de u e v é um conjunto de vértices cuja remoção a partir do gráfico desconecta u e v . A conectividade local κ ( u , v ) é o tamanho de um corte de vértice mais pequeno que separa u e v . A conectividade local é simétrica para gráficos não direcionados; ou seja, κ ( u , v ) = κ ( v , u ) . Além disso, exceto para gráficos completos, κ ( G ) é igual ao mínimo de κ ( u , v ) sobre todos os pares não adjacentes de vértices u, v .

A 2- conectividade também é chamada de biconectividade e a 3- conectividade também é chamada de tricconectividade . Um gráfico G que está conectado, mas não 2- conectado, às vezes é chamado de separável .

Conceitos análogos podem ser definidos para arestas. No caso simples em que cortar uma única aresta específica desconectaria o gráfico, essa aresta é chamada de ponte . Mais geralmente, um corte de borda de G é um conjunto de arestas cuja remoção torna o gráfico desconectado. A conectividade de aresta λ ( G ) é o tamanho de um corte de aresta menor, e a conectividade de aresta local λ ( u , v ) de dois vértices u, v é o tamanho de um corte de aresta menor desconectando u de v . Novamente, a conectividade de borda local é simétrica. Um gráfico é chamado de k -edge conectado se sua conectividade de borda for k ou maior.

Diz-se que um gráfico está conectado ao máximo se sua conectividade for igual a seu grau mínimo. Diz-se que um gráfico está conectado ao máximo pela borda se sua conectividade pela borda for igual ao seu grau mínimo.

Super e hiperconectividade

Diz-se que um gráfico é superconectado ou super-κ se cada corte mínimo de vértice isola um vértice. Um gráfico é considerado hiperconectado ou hiper-κ se a deleção de cada corte mínimo do vértice cria exatamente dois componentes, um dos quais é um vértice isolado. Um gráfico é semi-hiperconectado ou semi-hiper-κ se qualquer corte mínimo de vértice separar o gráfico em exatamente dois componentes.

Mais precisamente: um grafo conectado por G é dito superconectado ou super-κ se todos os cortes de vértices mínimos consistirem em vértices adjacentes a um vértice (grau mínimo). Um grafo G conectado é dito superconectado ou super λ se todos os cortes mínimos de aresta consistirem nas arestas incidentes em algum vértice (grau mínimo).

Um cutset X do L é chamado um cutset não-trivial, se X não contém a vizinhança N (u) de qualquer vértice u ∉ X . Então, a superconectividade κ1 de G é:

κ1 (G) = min {| X | : X é um cutset não trivial}.

Um corte de borda não trivial e a superconectividade de borda λ1 (G) são definidos analogamente.

Teorema de Menger

Um dos fatos mais importantes sobre a conectividade em grafos é o teorema de Menger , que caracteriza a conectividade e a conectividade de aresta 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 , em seguida, uma coleção de caminhos entre u e v é chamado independente se não houver dois deles compartilham um vértice (excepto u e v -se). Da mesma forma, a coleção é independente da borda se não houver dois caminhos nela que compartilhem uma borda. O número de caminhos mutuamente independentes entre u e v é escrito como κ ' ( u , v ) , e o número de caminhos mutuamente independente de ponta entre u e v é escrito como λ' ( u , v ) .

O teorema de Menger afirma que para vértices distintos u , v , λ ( u , v ) é igual a λ ′ ( u , v ) , e se u também não é adjacente a v, então κ ( u , v ) é igual a κ ′ ( u , v ) . Este fato é na verdade um caso especial do teorema de corte mínimo de fluxo máximo .

Aspectos computacionais

O problema de determinar se dois vértices em um gráfico estão conectados pode ser resolvido de forma eficiente usando um algoritmo de pesquisa , como a pesquisa em largura . De forma mais geral, é fácil determinar computacionalmente se um gráfico está conectado (por exemplo, usando uma estrutura de dados de conjunto separado ) ou contar o número de componentes conectados. Um algoritmo simples pode ser escrito em pseudocódigo da seguinte maneira:

  1. Comece em qualquer nó arbitrário do gráfico, G
  2. Continue a partir desse nó usando a pesquisa em profundidade ou em largura, contando todos os nós alcançados.
  3. Uma vez que o gráfico foi totalmente percorrido, se o número de nós contados for igual ao número de nós de G , o gráfico é conectado; caso contrário, ele é desconectado.

Pelo teorema de Menger, para quaisquer dois vértices u e v em um gráfico conectado L , os números k ( u , v ) e λ ( u , v ) pode ser determinado de forma eficiente utilizando o min-corte de fluxo máximo algoritmo. A conectividade e a conectividade de borda de G podem então ser calculadas como os valores mínimos de κ ( u , v ) e λ ( u , v ) , respectivamente.

Na teoria da complexidade computacional, SL é a classe de problemas de espaço logarítmico redutível ao problema de determinar se dois vértices em um grafo estão conectados, o que foi provado ser igual a L por Omer Reingold em 2004. Conseqüentemente, a conectividade de grafo não direcionada pode ser resolvido no espaço O (log n ) .

O problema de calcular a probabilidade de que um grafo aleatório de Bernoulli esteja conectado é chamado de confiabilidade de rede e o problema de calcular se dois vértices dados estão conectados, o problema de confiabilidade de ST. Ambos são #P -difícil.

Número de gráficos conectados

O número de gráficos marcados conectados distintos com n nós é tabulado na Enciclopédia On-Line de Sequências Inteiras como sequência A001187 . Os primeiros poucos termos não triviais são

n gráficos
2 1
3 4
4 38
5 728
6 26704
7 1866256
8 251548592

Exemplos

  • As conectividades de vértice e aresta de um gráfico desconectado são ambas 0 .
  • 1 -conectividade é equivalente a conectividade para gráficos de pelo menos 2 vértices.
  • O gráfico completo em n vértices tem conectividade de borda igual a n - 1 . Todos os outros gráficos simples em n vértices têm conectividade de borda estritamente menor.
  • Em uma árvore , a conectividade de borda local entre cada par de vértices é 1 .

Limites de conectividade

  • A conectividade de vértice de um gráfico é menor ou igual à sua conectividade de borda. Ou seja, κ ( G ) ≤ λ ( G ) . Ambos são menores ou iguais ao grau mínimo do gráfico, pois deletar todos os vizinhos de um vértice de grau mínimo desconectará aquele vértice do resto do gráfico.
  • Para um gráfico transitivo de vértice de grau d , temos: 2 ( d + 1) / 3 ≤ κ ( G ) ≤ λ ( G ) = d .
  • Para um gráfico transitivo de vértice de grau d ≤ 4 , ou para qualquer gráfico de Cayley mínimo (não direcionado) de grau d , ou para qualquer gráfico simétrico de grau d , ambos os tipos de conectividade são iguais: κ ( G ) = λ ( G ) = d .

Outras propriedades

Veja também

Referências