Vértice de corte (teoria dos grafos)

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Um grafo não-dirigido com n=5 vertices e n-2=3 vértices de corte; os vértices de corte (em vermelho) são aqueles que não estão em ambos as pontas
Um grafo não-dirigido sem vértices de corte

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[editar | editar código-fonte]

Um algoritmo trivial O(nm) é 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 muito melhor execução O(n+m)[2] é conhecido usando uma Busca em profundidade.

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

#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[editar | editar código-fonte]

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

  1. Gersting, Judith L.. Fundamentos Matemáticos para a Ciência da Computação. 3ª ed. Rio de Janeiro: LTC, 1993. 307 pp. ISBN 85-216-1041-6
  2. Slides apresentando o algoritmo O(n+m)

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

Ligações externas[editar | editar código-fonte]

  • 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).