Vèrtiç de tall

Revisió de 17:04 30 ago 2016 per 188.244.80.133 (Discussió) (Pàgina nova, en el contingut: «Archiu:UndirectedChain.jpg|thumb|120px|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ó...»)
(difs.) ← Revisió anterior | Revisió actual (difs.) | Revisió següent → (difs.)
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.
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é