Revisão das 17h25min de 17 de maio de 2010 editar Ricardo Ferreira de Oliveira (discussão \| contribs) Administradores 26 610 edições ← nova página: {{Em tradução}} [[Ficheiro:Undirected chain articulation points.svg\|right\|thumb\|125px\|Um grafo não-dirigido com ''n''=5 vertices e ''n''-2=3 vértices de corte; os...		Revisão das 23h17min de 17 de maio de 2010 editar desfazer Ricardo Ferreira de Oliveira (discussão \| contribs) Administradores 26 610 edições Ver a alteração posterior →
Linha 6: Em [[matemática]] e [[ciência da computação]], um '''vértice de corte''' ou '''ponto de articulação''' é um [[Vértice (teoria dos grafos)\|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 (teoria dos grafos)\|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. While well-defined even for directed graphs, cut vertices are primarily used in undirected graphs. In general, a connected, undirected graph with ''n'' vertices can have no more than ''n''-2 cut vertices. Naturally, a graph may have no cut vertices at all. ▲<!-- ~~A [[bridge (graph theory)\|bridge]] is an edge analogous to a cut vertex; that is, the removal of a bridge increases the number of connected components of the graph.~~ == Finding Cut vertices ==

Vértice de corte (teoria dos grafos): diferenças entre revisões