Diferència entre les revisions de "Vèrtiç de tall"

De L'Enciclopèdia, la wikipedia en valencià
Anar a la navegació Anar a la busca
m
 
Llínea 27: Llínea 27:
  
 
{{Traduït de|es|Vértice de corte}}
 
{{Traduït de|es|Vértice de corte}}
 +
 +
 
[[Categoria:Teoria de grafo]]
 
[[Categoria:Teoria de grafo]]

Última revisió del 19:17 8 gin 2017

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[editar | editar còdic]

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 | editar còdic]