Canvis
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ó...»
[[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ón punts finals.]]
[[Archiu:Undirected.svg|thumb|125px|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ç (teoria de graf)|vèrtiç]] d'un [[graf]] tal que en eliminar-ho d'este es produïx un increment en el número de [[Component fortament conex|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 (teoria de grafo)|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 (teoria d'@grafo)|arbre]], cada vèrtiç en [[grau (teoria de grafo)|grau]] major que 1 és un vèrtiç de cort.
== Buscant vèrtiços de cort ==
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]])
: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é ==
* [[Graf conex]]
* [[Aresta de tall]]
{{Traduït de|es|Vértice de corte}}
[[Categoria:Teoria de grafo]]
[[Archiu:Undirected.svg|thumb|125px|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ç (teoria de graf)|vèrtiç]] d'un [[graf]] tal que en eliminar-ho d'este es produïx un increment en el número de [[Component fortament conex|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 (teoria de grafo)|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 (teoria d'@grafo)|arbre]], cada vèrtiç en [[grau (teoria de grafo)|grau]] major que 1 és un vèrtiç de cort.
== Buscant vèrtiços de cort ==
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]])
: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é ==
* [[Graf conex]]
* [[Aresta de tall]]
{{Traduït de|es|Vértice de corte}}
[[Categoria:Teoria de grafo]]