Teoria de grafos - Conectividade

Se é possível atravessar um gráfico de um vértice para outro é determinado por como um gráfico é conectado. Conectividade é um conceito básico da Teoria dos Grafos. Conectividade define se um gráfico está conectado ou desconectado. Possui subtópicos baseados em aresta e vértice, conhecidos como conectividade de aresta e conectividade de vértice. Vamos discuti-los em detalhes.

Conectividade

Diz-se que um gráfico é connected if there is a path between every pair of vertex. De cada vértice a qualquer outro vértice, deve haver algum caminho a ser percorrido. Isso é chamado de conectividade de um gráfico. Um gráfico com vários vértices e arestas desconectados é considerado desconectado.

Example 1

No gráfico a seguir, é possível viajar de um vértice para qualquer outro vértice. Por exemplo, pode-se atravessar do vértice 'a' ao vértice 'e' usando o caminho 'ab-e'.

Example 2

No exemplo a seguir, atravessar do vértice 'a' para o vértice 'f' não é possível porque não há nenhum caminho entre eles direta ou indiretamente. Portanto, é um gráfico desconectado.

Cut Vertex

Seja 'G' um gráfico conectado. Um vértice V ∈ G é chamado de vértice de corte de 'G', se 'G-V' (Excluir 'V' de 'G') resulta em um gráfico desconectado. Remover um vértice de corte de um gráfico divide-o em dois ou mais gráficos.

Note - Remover um vértice cortado pode tornar um gráfico desconectado.

Um gráfico conectado 'G' pode ter no máximo (n – 2) vértices de corte.

Example

No gráfico a seguir, os vértices 'e' e 'c' são os vértices cortados.

Ao remover 'e' ou 'c', o gráfico se tornará um gráfico desconectado.

Sem 'g', não há caminho entre o vértice 'c' e o vértice 'h' e muitos outros. Portanto, é um gráfico desconectado com vértice de corte como 'e'. Da mesma forma, 'c' também é um vértice de corte para o gráfico acima.

Borda cortada (ponte)

Seja 'G' um gráfico conectado. Uma aresta 'e' ∈ G é chamada de aresta de corte se 'G-e' resultar em um gráfico desconectado.

Se a remoção de uma borda em um gráfico resultar em dois ou mais gráficos, essa borda é chamada de Corte de Borda.

Example

No gráfico a seguir, a borda de corte é [(c, e)].

Ao remover a aresta (c, e) do gráfico, ele se torna um gráfico desconectado.

No gráfico acima, remover a aresta (c, e) divide o gráfico em dois, que nada mais é do que um gráfico desconectado. Portanto, a aresta (c, e) é uma aresta de corte do gráfico.

Note - Seja 'G' um gráfico conectado com 'n' vértices, então

uma aresta de corte e ∈ G se e somente se a aresta 'e' não fizer parte de qualquer ciclo em G.
o número máximo de arestas de corte possível é 'n-1'.
sempre que houver arestas de corte, vértices de corte também existem porque pelo menos um vértice de uma aresta de corte é um vértice de corte.
se existe um vértice de corte, então uma aresta de corte pode ou não existir.

Corte o conjunto de um gráfico

Seja 'G' = (V, E) um gráfico conectado. Um subconjunto E 'de E é chamado de conjunto de corte de G se a exclusão de todas as arestas de E' de G faz G desconectar.

Se a exclusão de um certo número de arestas de um gráfico o desconecta, então essas arestas excluídas são chamadas de conjunto de corte do gráfico.

Example

Dê uma olhada no gráfico a seguir. Seu conjunto de corte é E1 = {e1, e3, e5, e8}.

Depois de remover o conjunto de corte E1 do gráfico, ele aparecerá da seguinte forma -

Da mesma forma, existem outros conjuntos de corte que podem desconectar o gráfico -

E3 = {e9} - Menor conjunto de corte do gráfico.
E4 = {e3, e4, e5}

Edge Connectivity

Seja 'G' um gráfico conectado. O número mínimo de arestas cuja remoção torna 'G' desconectado é chamado de conectividade de aresta de G.

Notation - λ (G)

Em outras palavras, o number of edges in a smallest cut set of G é chamada de conectividade de borda de G.

Se 'G' tem uma borda de corte, então λ (G) é 1. (conectividade de borda de G.)

Example

Dê uma olhada no gráfico a seguir. Ao remover duas arestas mínimas, o gráfico conectado se desconecta. Portanto, sua conectividade de borda (λ (G)) é 2.

Aqui estão as quatro maneiras de desconectar o gráfico removendo duas arestas -

Vertex Connectivity

Seja 'G' um gráfico conectado. O número mínimo de vértices cuja remoção torna 'G' desconectado ou reduz 'G' a um grafo trivial é chamado de conectividade de vértice.

Notation - K (G)

Example

No gráfico acima, remover os vértices 'e' e 'i' faz com que o gráfico se desconecte.