Vèrtiç de tall

Archiu:UndirectedChain.jpg

Un graf no dirigit en n=5 vèrtiços i n-2=3 vèrtiços de cort; els vèrtiços de cort són aquells que no són punts finals.

Archiu:Undirected.svg

Graf no dirigit sense vèrtiços de cort.

En teoria de graf, un vèrtiç de tall o punt d'articulació és un vèrtiç d'un graf tal que en eliminar-ho d'este es produïx un increment en el número de components conexos. Si el graf estava conectat abans de retirar el vèrtiç, llavors passarà a desconectar-se. Qualsevol graf conex en un vèrtiç de tall té una conectivitat d'1. A pesar de que estiguen ben definits per a grafs dirigits, els vèrtiços de cort s'usen principalment en els grafs no dirigits. En general, un graf conex, no dirigit i en n vèrtiços, pot tindre no més que n-2 vèrtiços de cort. Naturalment, un graf pot no tindre cap vèrtiç de cort. A pesar de que estiguen ben definits per grafs dirigits, els vèrtiços de cort s'usen principalment en els grafs no dirigits. En general, un graf conex, no dirigit i en n vèrtiços, pot tindre no més que n-2 vèrtiços de cort. Naturalment, un graf pot no tindre cap vèrtiç de cort. Una aresta de tall o pont, és una aresta anàloga a un vèrtiç de cort; és dir, una que en eliminar-la incrementa el número de components conexos del graf.

En un arbre, cada vèrtiç en grau major que 1 és un vèrtiç de cort.

Buscant vèrtiços de cort

Un algoritme trivial de complexitat O(nm) és el següent:

a = número de components en G (trobar usant DFS/BFS)

per a cada i en V en arestes incidents

eliminar i de V

b = número de components en G en i eliminat

si b > a

i és un vèrtiç de cort

restaurar i

Existix un algoritme en temps d'eixecució d'orde O(n+m) que utilisa la busca en profunditat.

Vore també

• Graf conex
• Aresta de tall

• Est artícul fon creat a partir de la traducció de l'artícul es.wikipedia.org/wiki/Vértice de corte de la Wikipedia en espanyol, baix llicència Creative Commons-BY-SA.