Diferència entre les revisions de "Vèrtiç de tall"
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ó...» |
Sense resum d'edició |
||
| 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''('' | 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| | :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 | ||