154 209
edicions
Canvis
Anar a la navegació
Anar a la busca
Llínea 11:
Llínea 11: − + − + Llínea 21:
Llínea 21: − + + + + − {{Traduït de|es|Vértice de corte}}
sense resum d'edició
== 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
::restaurar i
::restaurar i
Existix un algoritme en [[temps d'eixecució]] d'orde ''O''(''n''+''m'') que utilisa la [[busca en profunditat]].
Existix un algoritme en [[temps d'eixecució]] d'orde ''O''(''n''+''m'') que utilisa la [[busca en profunditat]].
== Vore també ==
== Vore també ==
* [[Graf conex]]
* [[Graf conex]]
* [[Aresta de tall]]
* [[Aresta de tall]]
{{Traduït de|es|Vértice de corte}}
[[Categoria:Teoria de grafo]]
[[Categoria:Teoria de grafo]]