Diferencia entre revisiones de «Vértice de corte»

Contenido eliminado Contenido añadido
añado enlace
Línea 1:
[[Imagen:UndirectedChain.jpg|right|thumb|120px|Un grafo no dirigido con ''n''=5 vértices y ''n''-2=3 vértices de corte; los vértices de corte son aquellos que no son puntos finales.]]
[[Image:Undirected.svg|thumb|125px|Grafo no dirigido sin vértices de corte]]
En [[teoría de grafos]], un '''vértice de corte''' o '''punto de articulación''' es un [[Vértice (teoría de grafos)|vértice]] de un [[grafo]] tal que al removerlo de éste se produce un incremento en el número de [[Componente fuertemente conexo|componentes conexos]]. Si el grafo estaba conectado antes de retirar el vértice, entonces pasará a desconectarse. Cualquier [[grafo conexo]] con un vértice de corte tiene una conectividad de 1.
 
A pesar de que estén bien definidos para grafos dirigidos, los vértices de corte se usan principalmente en los grafos no dirigidos. En general, un grafo conexo, no dirigido y con ''n'' vértices, puede tener no más que ''n''-2 vértices de corte. Naturalmente, un grafo puede no tener ningún vértice de corte.