Em teoria dos grafos, uma ponte (também conhecida como aresta-de-corte ou arco de corte ou um istmo) é uma aresta cuja deleção em um grafo aumenta o número de componentes conectados deste. Equivalentemente, uma aresta é uma ponte, se e somente se ela não está contida em qualquer ciclo.
Um grafo é dito ser sem ponte se ele não contém pontes. É fácil ver que isso é equivalente a 2-arestas-conectividade de cada componente não trivial.
Conjectura do ciclo de dupla cobertura Um importante problema aberto envolvendo pontes é a conjectura do ciclo de dupla cobertura, devido à Seymour e Szekeres (1978 e 1979, independentemente), que afirma que todo grafo sem ponte admite um conjunto de ciclos que contém cada aresta exatamente duas vezeshttp://www.cems.uvm.edu/%7Earchdeac/problems/cyclecov.htm .
Algoritmo de pesquisa de pontes Um algoritmo de complexidade para encontrar pontes em um grafo conexo foi descoberto por Tarjan em 1974"A note on finding the bridges of a graph", Robert Endre Tarjan, Information Processing Letters, April 1974 pp160-161..
Algoritmo em C++ #include <algorithm> #include <set> #include <vector> #include <cstring> #define MAX 400
using namespace std; int n, time_s, visit[MAX]; vector<int> ADJ[MAX];
int dfs(int u, int pai, vector<pair<int,int> >& ans){ int menor = visit[u] = time_s++; int filhos = 0; for(int i = 0; i<ADJ[u].size(); i++){ if(visit[ADJ[u][i]]==0){ filhos++; int m = dfs(ADJ[u][i], u, ans); menor = min(menor,m); if(visit[u]<m){ ans.push_back(make_pair(u, ADJ[u][i]));
}else if(ADJ[u][i]!=pai){ menor = min(menor, visit[ADJ[u][i]]);
return menor; }
vector<pair<int,int> > get_articulacoes(){ vector<pair<int,int> > ans; time_s = 1; memset(visit, 0, n*sizeof(int)); dfs(0,-1,ans); return ans; }
Definições: Uma aresta não-árvore entre e é denotada por . Uma aresta em-árvore com como pai é denotada por .
onde é o nodo pai de .
detecta conexões para nós mais à esquerda ou mais para baixo na árvore.
detecta conexões para nós mais à direita ou mais para cima na árvore.
Algoritmo: Encontre uma árvore de extensão mínima de Crie uma árvore enraizada a partir da árvore de extensão mínima Atravesse a árvore em pós-ordem e numere os nodos. Nodos pai na árvore agora tem números mais altos do que os nodos filho. Para cada nodo de 1 a (o nodo raiz da árvore) faça: Calcule o número de descendentes para este nodo. Calcule e para cada tal que : se e então é uma ponte.
Arco de corte em árvores Uma aresta ou arco e = uv de uma árvore G é um arco de corte de G se e somente se o grau dos vértices u e v são maiores do que 1. Arcos de corte são também definidos para grafos orientados Rao, S.B.; Ramachandra Rao, A. The number of cut vertices and cut arcs in a strong directed graph. (em inglês) Acta Math. Acad. Sci. Hung. 22, 411-421 (1972).
Ver também Vértice de corte
Bibliografia Béla Bollobás, Modern graph theory, GTM 184, Springer Verlag, 1998.
Categoria:Teoria dos grafos Categoria:Conectividade de grafos