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
(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ó...»)
 
Llínea 11: Llínea 11:
 
== Buscant vèrtiços de cort ==
 
== Buscant vèrtiços de cort ==
  
Un [[algoritme]] trivial de [[complexitat computacional|complexitat]] ''O''(''*nm'') és el següent:
+
Un [[algoritme]] trivial de [[complexitat computacional|complexitat]] ''O''(''nm'') és el següent:
  
:a = número de components en G (trobar usant [[Busca en profunditat|*DFS]]/[[Busca en esgambi|*BFS]])
+
:a = número de components en G (trobar usant [[Busca en profunditat|DFS]]/[[Busca en esgambi|BFS]])
 
:per a cada i en V en arestes incidents
 
:per a cada i en V en arestes incidents
 
::eliminar i de V  
 
::eliminar i de V  

Revisió de 17:05 30 ago 2016

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é