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 $G=(V,E)$ um grafo arbitrário. Se um subgrafo $G^{\prime }=(V,E\setminus X)$ é conexo para todo $X\subseteq E$ onde $|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 $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 $O(n^2)$ interações no máximo grau do problema, que pode ser resolvido com tempo de $O(n^3)$. Por isso, a complexidade do algoritmo descrito é de $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 $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 $O(n^3)$ tempo.

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 $k\ge 2$.

Veja também

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