Vértice de corte (teoria dos grafos)

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

Um algoritmo trivial ${\displaystyle 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 de execução muito melhor, ${\displaystyle O(n+m)}$[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

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

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