Vértice de corte
En teoría de grafos, un vértice de corte, nodo de corte,[1] punto de corte[2] o punto de articulación[1] es un vértice de un grafo tal que al eliminarlo de este se produce un incremento en el número de componentes conexos.[2] 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. En un árbol, cada vértice con 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.[2]
Análogamente, una arista de corte o puente, es una arista que al eliminarla incrementa el número de componentes conexos del grafo. El grado de conectividad de un grafo se puede calcular en términos del número de vértices o aristas de corte que posee. Esta conectividad es una medida de su cohesión o robustez.[2]
Buscando vértices de corte
editarUn algoritmo trivial de complejidad O(nm) es el siguiente:
- a = número de componentes en G (encontrar usando DFS/BFS)
- para cada i en V con aristas incidentes
- eliminar i de V
- b = número de componentes en G con i eliminado
- si b > a
- i es un vértice de corte
- restaurar i
Existe un algoritmo con tiempo de ejecución de orden O(n+m) que utiliza la búsqueda en profundidad.
Aplicaciones
editarLos 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 componentes entre las cuales no se podrían transmitir mensajes.[2]
Véase también
editarReferencias
editar- ↑ a b Gutiérrez, J. A.; Herrera, M.; Pérez-García, R.; Izquierdo, J. (2011). «Aplicación de técnicas de teoría de grafos en el análisis de la vulnerabilidad de redes abastecimiento de agua». 10 Seminario Iberoamericano de Planificación, Proyecto y Operación de Sistemas de Abastecimiento de Agua, SEREA (Morelia, Michoacán, México). Consultado el 26 de abril de 2021.
- ↑ a b c d e Wasserman y Faust, 2013, «Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.
Bibliografía
editar- Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053.
Datos: Q2300244
