Diferencia entre revisiones de «Vértice de corte»

1 byte eliminado ,  hace 2 años
m
Correcciones ortográficas con Replacer (herramienta en línea de revisión de errores)
m (Mantenimiento de Control de autoridades)
Etiqueta: Edición móvil avanzada
m (Correcciones ortográficas con Replacer (herramienta en línea de revisión de errores))
[[Archivo:UndirectedChain.jpg|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.]]
[[Archivo: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 eliminarlo de ésteeste 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.
161 025

ediciones