Mostrar código-fonte de Ponte (teoria dos grafos)

[[Image:Graph cut edges.svg|thumb|200px|Um grafo com 6 pontes (ressaltadas em vermelho)]]
[[Image:Undirected.svg|thumb|125px|Um grafo conexo não-orientado sem arestas de corte]]

Em [[teoria dos grafos]], uma '''ponte''' (também conhecida como aresta-de-corte ou arco de corte ou um istmo) é uma [[aresta (teoria dos grafos)|aresta]] cuja deleção em um [[grafo]] aumenta o número de [[componente conectado (teoria dos grafos)|componentes conectados]] deste. Equivalentemente, uma aresta é uma ponte, [[se e somente se]] ela não está contida em qualquer [[Ciclo (teoria dos grafos)|ciclo]].

Um grafo é dito ser '''sem ponte''' se ele não contém pontes. É fácil ver que isso é equivalente a [[grafo K-arestas-conectado|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 à [[Paul Seymour (matemático)|Seymour]] e [[George Szekeres|Szekeres]] (1978 e 1979, independentemente), que afirma que todo grafo sem ponte admite um conjunto de ciclos que contém cada aresta exatamente duas vezes<ref>http://www.cems.uvm.edu/%7Earchdeac/problems/cyclecov.htm</ref>.

==Algoritmo de pesquisa de pontes==
Um algoritmo de complexidade <math>O(|V|+|E|)</math> para encontrar pontes em um grafo conexo foi descoberto por [[Tarjan]] em 1974<ref>"A note on finding the bridges of a graph", Robert Endre Tarjan, Information Processing Letters, April 1974 pp160-161.</ref>.

==Algoritmo em C++==
<syntaxhighlight lang="cpp">
#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;
}
</syntaxhighlight>

Definições:
Uma aresta não-árvore entre <math>v</math> e <math>w</math> é denotada por <math>v--w</math>. Uma aresta em-árvore com <math>v</math> como pai é denotada por <math>v\to w</math>.

<math>ND(v) = 1 + \sum_{v \to w} ND(w)</math> onde <math>v</math> é o nodo pai de <math>w</math>.

<math>L(v) = \min(\{v - ND(v) + 1\} \cup \{L(w) \mid v \to w\} \cup \{w \mid v--w\})</math>

<math>L</math> detecta conexões para nós mais à esquerda ou mais para baixo na árvore.

<math>H(v) = \max(\{v\} \cup \{H(w) \mid v \to w\} \cup \{w \mid v--w\})</math>

<math>H</math> detecta conexões para nós mais à direita ou mais para cima na árvore.

Algoritmo:
# Encontre uma árvore de extensão mínima de <math>G</math>
# Crie uma árvore enraizada <math>T</math> a partir da árvore de extensão mínima 
# Atravesse a árvore <math>T</math> 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 <math>v_1</math> (o nodo raiz da árvore) faça:
## Calcule o número de descendentes <math>ND(v)</math> para este nodo.
## Calcule <math>L(v)</math> e <math>H(v)</math>
## para cada <math>w</math> tal que <math>v \to w</math>: se <math>H(w) \leq w</math> e <math>L(w) > w - ND(w)</math> então <math>(v, w)</math> é 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 [[grafo orientado|grafos orientados]] <ref>[[S. B. Rao|Rao, S.B.]]; [[A. R. Rao|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).</ref>

==Ver também==
* [[Vértice de corte (teoria dos grafos)|Vértice de corte]]

==Bibliografia==
* [[Béla Bollobás]], ''Modern graph theory'', [[Graduate Texts in Mathematics|GTM]] '''184''', Springer Verlag, 1998. 

{{Referências}}

[[Categoria:Teoria dos grafos]]
[[Categoria:Conectividade de grafos]]