Vértice de corte , la enciclopedia libre

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]​

Un 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.

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 componentes entre las cuales no se podrían transmitir mensajes.^[2]​

• Grafo conexo
• Arista de corte

• 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.