Ponte (teoria dos grafos)

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Um grafo com 6 pontes (ressaltadas em vermelho)
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 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[editar | editar código-fonte]

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 vezes[1] .

Algoritmo de pesquisa de pontes[editar | editar código-fonte]

Um algoritmo de compexidade O(|V|+|E|) para encontrar pontes em um grafo conexo foi descoberto por Tarjan em 1974[2] .

Algoritmo em C++[editar | editar código-fonte]

#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 v e w é denotada por v--w. Uma aresta em-árvore com v como pai é denotada por v\to w.

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

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

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

H(v) = \max(\{v\} \cup \{H(w) \mid v \to w\} \cup \{w \mid v--w\})

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

Algoritmo:

  1. Encontre uma árvore de extensão mínima de G
  2. Crie uma árvore enraizada T a partir da árvore de extensão mínima
  3. Atravesse a árvore T em pós-ordem e numere os nodos. Nodos pai na árvore agora tem números mais altos do que os nodos filho.
  4. Para cada nodo de 1 a v_1 (o nodo raiz da árvore) faça:
    1. Calcule o número de descendentes ND(v) para este nodo.
    2. Calcule L(v) e H(v)
    3. para cada w tal que v \to w: se H(w) \leq w e L(w) > w - ND(w) então (v, w) é uma ponte.

Arco de corte em árvores[editar | editar código-fonte]

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 [3]

Ver também[editar | editar código-fonte]

Bibliografia[editar | editar código-fonte]

Referências

  1. http://www.cems.uvm.edu/%7Earchdeac/problems/cyclecov.htm
  2. "A note on finding the bridges of a graph", Robert Endre Tarjan, Information Processing Letters, April 1974 pp160-161.
  3. 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).