Edició de «Vèrtiç de tall»
Anar a la navegació
Anar a la busca
Advertencia: No has iniciat sessió. La teua direcció IP serà visible públicament si realises qualsevol edició. Si inicies sessió o crees un conte, les teues edicions s'atribuiran al teu nom d'usuari, junt en atres beneficis.
Pot desfer-se la modificació. Per favor, revisa la comparació més avall per a assegurar-te que es lo que vols fer; llavors deixa els canvis per a la finalisació de la desfeta de l'edició.
Revisió actual | El teu text | ||
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 |