Vértice de corte (teoria dos grafos)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e2/Undirected_chain_articulation_points.svg/125px-Undirected_chain_articulation_points.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/bf/Undirected.svg/125px-Undirected.svg.png)
Em matemática e ciência da computação, um vértice de corte ou ponto de articulação[1] é um vértice de um grafo tal que a remoção deste vértice provoca um aumento no número de componentes conectados. Se o grafo era conectado antes da remoção do vértice, ele será desconectado depois. Qualquer grafo conectado com um vértice de corte tem uma conectividade de 1.
Embora bem definidos, mesmo para grafos dirigidos (digrafos), os vértices de corte são utilizados principalmente em grafos não dirigidos. Em geral, um grafo conectado, não-dirigido, com n vértices não pode ter mais do que n-2 vértices de corte. Naturalmente, um grafo pode não ter nenhum vértice de corte.
Uma ponte é uma aresta análoga a um vértice de corte, ou seja, a remoção de uma ponte aumenta o número de componentes conectados do grafo.
Encontrando Vértices de corte
Um algoritmo trivial é como se segue:
C = conjunto vazio (no final do algoritmo ele irá conter os vértices de corte) a = número de componentes em G (encontrado usando uma Busca em profundidade/Busca em largura) para cada i em V com arestas incidentes b = número de componentes em G com i removido se b < a i é um vértice de corte C = C + {i} fimse fimpara
Um algoritmo com o tempo de execução muito melhor, [2] é conhecido usando uma Busca em profundidade.
Algoritmo em C++
#include <algorithm> #include <set> #include <vector> #include <cstring> #define MAX 100 using namespace std; int n, time_s, visit[MAX]; vector<int> ADJ[MAX]; int dfs(int u, set<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], ans); menor = min(menor,m); if(visit[u]<=m && (u!=0 || filhos>=2)){ ans.insert(u); } }else{ menor = min(menor, visit[ADJ[u][i]]); } } return menor; } set<int> get_articulacoes(){ set<int> ans; time_s = 1; memset(visit, 0, n*sizeof(int)); dfs(0,ans); return ans; }
Teste seu código em: http://br.spoj.pl/problems/MANUT/
Vértices de corte em árvores
Um vértice v de uma árvore G é um vértice de corte de G somente se o grau do vértice é maior que 1.
Referências
Ver também
- Aresta de corte
Ligações externas
- Wolfram Mathworld [1] "Cut-Vertex"
- Nirmala, K.; Ramachandra Rao, A. O número de vértices de corte em um grafo regular. (em português), Cah. Cent. Étud. Rech. Opér. 17, 295-299 (1975).