Diferencia entre revisiones de «Vértice de corte»
Contenido eliminado Contenido añadido
Sin resumen de edición |
Sin resumen de edición |
||
Línea 1:
[[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''', '''nodo de corte''',<ref name=Gut11>{{cita publicación |autor1=Gutiérrez, J. A. |autor2=Herrera, M. |autor3=Pérez-García, R. |autor4=Izquierdo, J. |año=2011 |título=Aplicación de técnicas de teoría de grafos en el análisis de la vulnerabilidad de redes abastecimiento de agua |publicación=10 Seminario Iberoamericano de Planificación, Proyecto y Operación de Sistemas de Abastecimiento de Agua, SEREA |ubicación=Morelia, Michoacán, México |url=https://www.researchgate.net/profile/Manuel-Herrera-21/publication/309717504_Aplicacion_de_tecnicas_de_teoria_de_grafos_en_el_analisis_de_la_vulnerabilidad_de_redes_abastecimiento_de_agua/links/581f14d108ae12715af65b47/Aplicacion-de-tecnicas-de-teoria-de-grafos-en-el-analisis-de-la-vulnerabilidad-de-redes-abastecimiento-de-agua.pdf |fechaacceso=26 de abril de 2021}}</ref> '''punto de corte'''<ref name=WF13.c4>{{harvsp|Wasserman|Faust|2013|loc=«Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.}}</ref> o '''punto de articulación'''<ref name=Gut11/> es un [[Vértice (teoría de grafos)|vértice]] de un [[grafo]] tal que al eliminarlo de este se produce un incremento en el número de [[Componente (teoría de grafos)|componentes conexos]].<ref name=WF13.c4/> 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 (teoría de grafos)|conectividad]] de 1.
A pesar de que estén bien definidos para [[grafo dirigido|grafos dirigidos]], los vértices de corte se usan principalmente en los [[grafo no dirigido|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. En un [[árbol (teoría de grafos)|árbol]], cada vértice con [[grado (teoría de grafos)|grado]] mayor que 1 es un vértice de corte.
| |||