Grafo k-aresta-conexo

Na teoria dos grafos, um grafo é k-aresta-conexo se ele permanece conexo mesmo que (menos que) k arestas sejam retiradas.

A aresta-conectividade de um grafo é o maior k para que um grafo é k-aresta-conexo.

Definição Formal

Seja ${\displaystyle G=(V,E)}$ um grafo arbitrário. Se um subgrafo ${\displaystyle G'=(V,E\setminus X)}$ é conexo para todo ${\displaystyle X\subseteq E}$ onde ${\displaystyle |X|<k}$, então G é k-aresta-conexo.

Grau de relação do mínimo vértice

O mínimo grau de vértice dá um limite trivial de ponta para aresta-conexa. Isto é, se um grafo ${\displaystyle G=(V,E)}$ é k-aresta-conexo então é necessário que k ≤ δ(G)), onde δ(G) é o grau mínimo de qualquer vértice v ∈ V. Obviamente, deletando todas arestas incidentes ao vértice, v, iria então desconexar v do grafo.

Aspectos Computacionais

Existe um algoritmo de tempo polinomial que determina o maior k para que um grafo G é k-arestas-conexo. Um simples algoritmo poderia, para cada par (u,v), determina o grau máximo de u para v com capacidade de todas as arestas em G igualando a 1 para ambas direções. O grafo é k-arestas-conexo se somente se o grau máximo de u para v é no mínimo k para qualquer par (u,v), então k é no mínimo u-v-grau entre todos (u,v).

Se n é o número de vértices do grafo, este simples algoritmo iria ter um tempo de ${\displaystyle O(n^{2})}$ interações no máximo grau do problema, que pode ser resolvido com tempo de ${\displaystyle O(n^{3})}$. Por isso, a complexidade do algoritmo descrito é de ${\displaystyle O(n^{5})}$ no total.

Um algoritmo improvisado vai resolver o máximo grau do problema para cada par (u,v) onde u é arbitrariamente fixado enquanto v varia todos os vértices. Essa redução tem complexidade de ${\displaystyle O(n^{4})}$, se o corte da capacidade menos que k existir, esse é o limite para separar u de outros vértices. Pode ser usado para improvisar mais pelo algoritmo de Gabow que corre no pior caso em ${\displaystyle O(n^{3})}$ tempo.^[1]

Um problema relacionado: Achar o mínimo subgrafo k-arestas-conexo de G (ou seja: selecionar poucas possíveis arestas em G que sua seleção é k-arestas-conexo) é NP-difícil para ${\displaystyle k\geq 2}$.^[2]

Veja também

• Grafo k-vertice-conexo
• Conectividade (teoria dos grafos)
• Teorema de Menger
• Teorema de Robbins