Vértice de corte (teoria dos grafos)

Em matemática e ciência da computação, um vértice de corte ou ponto de articulação é 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.

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

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 $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, $O(n+m)$ é 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.

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