Loading AI tools
conceito da teoria dos grafos Da Wikipédia, a enciclopédia livre
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.
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].
Um algoritmo de complexidade para encontrar pontes em um grafo conexo foi descoberto por Tarjan em 1974[2].
#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:
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]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.