Vèrtiç de tall
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 cortEditar
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éEditar
- 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.