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ó |
||
| (No es mostren 5 edicions intermiges d'2 usuaris) | |||
| 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 | ||
| Llínea 21: | Llínea 21: | ||
::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]] | ||