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 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.
 
El concepto de vértice de corte se puede generalizar a un conjunto de vértices. Así, un '''conjunto de corte''' es un conjunto de vértices necesario para mantener la conexión de un grafo. Un '''corte de nodos-''k''''' es un conjunto de corte de ''k'' vértices. Por lo tanto, un vértice de corte es un corte de nodos-1.<ref name=WF13.c4/>
Una [[arista de corte]] o puente, es una [[arista (teoría de grafos)|arista]] análoga a un vértice de corte; es decir, una que al eliminarla incrementa el número de componentes conexos del grafo.
 
EnAnálogamente, ununa [[árbol (teoríaarista de grafos)|árbolcorte]] o puente, cadaes vértice conuna [[gradoarista (teoría de grafos)|gradoarista]] mayor que 1al eseliminarla incrementa unel vérticenúmero de cortecomponentes conexos del grafo.
 
== Buscando vértices de corte ==
Línea 22:
 
Existe un algoritmo con [[tiempo de ejecución]] de orden ''O''(''n''+''m'') que utiliza la [[búsqueda en profundidad]].
 
== Aplicaciones ==
Los vértices de corte son estudiados en [[análisis de redes sociales]]. En redes de comunicación, son importantes ya que si se quitaran de la red, entonces quedarían [[Componente (teoría de grafos)|componentes]] entre las cuales no se podrían transmitir mensajes.<ref name=WF13.c4/>
 
== Véase también ==
* [[Grafo conexo]]
* [[Arista de corte]]
 
== Referencias ==
{{listaref}}
 
== Bibliografía ==