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.
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.
Grafo no dirigido sin vértices de corte.
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]
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]
↑ 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.
Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN978-84-7476-631-8. OCLC 871814053.
Datos:Q2300244
Agosto 05, 2021
vértice, corte, teoría, grafos, vértice, corte, nodo, corte, punto, corte, punto, articulación, vértice, grafo, eliminarlo, este, produce, incremento, número, componentes, conexos, grafo, estaba, conectado, antes, retirar, vértice, entonces, pasará, desconecta. En teoria de grafos un vertice de corte nodo de corte 1 punto de corte 2 o punto de articulacion 1 es un vertice de un grafo tal que al eliminarlo de este se produce un incremento en el numero de componentes conexos 2 Si el grafo estaba conectado antes de retirar el vertice entonces pasara a desconectarse Cualquier grafo conexo con un vertice de corte tiene una conectividad de 1 Un grafo no dirigido con n 5 vertices y n 2 3 vertices de corte los vertices de corte son aquellos que no son puntos finales Grafo no dirigido sin vertices de corte A pesar de que esten bien definidos para grafos dirigidos los vertices de corte se usan principalmente en los grafos no dirigidos En general un grafo conexo no dirigido y con n vertices puede tener no mas que n 2 vertices de corte Naturalmente un grafo puede no tener ningun vertice de corte En un arbol cada vertice con grado mayor que 1 es un vertice de corte El concepto de vertice de corte se puede generalizar a un conjunto de vertices Asi un conjunto de corte es un conjunto de vertices necesario para mantener la conexion de un grafo Un corte de nodos k es un conjunto de corte de k vertices Por lo tanto un vertice de corte es un corte de nodos 1 2 Analogamente una arista de corte o puente es una arista que al eliminarla incrementa el numero de componentes conexos del grafo El grado de conectividad de un grafo se puede calcular en terminos del numero de vertices o aristas de corte que posee Esta conectividad es una medida de su cohesion o robustez 2 Indice 1 Buscando vertices de corte 2 Aplicaciones 3 Vease tambien 4 Referencias 5 BibliografiaBuscando vertices de corte EditarUn algoritmo trivial de complejidad O nm es el siguiente a numero de componentes en G encontrar usando DFS BFS para cada i en V con aristas incidenteseliminar i de V b numero de componentes en G con i eliminado si b gt ai es un vertice de corte dd restaurar i dd Existe un algoritmo con tiempo de ejecucion de orden O n m que utiliza la busqueda en profundidad Aplicaciones EditarLos vertices de corte son estudiados en analisis de redes sociales En redes de comunicacion son importantes ya que si se quitaran de la red entonces quedarian componentes entre las cuales no se podrian transmitir mensajes 2 Vease tambien EditarGrafo conexo Arista de corteReferencias Editar a b Gutierrez J A Herrera M Perez Garcia R Izquierdo J 2011 Aplicacion de tecnicas de teoria de grafos en el analisis de la vulnerabilidad de redes abastecimiento de agua 10 Seminario Iberoamericano de Planificacion Proyecto y Operacion de Sistemas de Abastecimiento de Agua SEREA Morelia Michoacan Mexico 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 Bibliografia EditarWasserman Stanley Faust Katherine 2013 1994 Analisis de redes sociales Metodos y aplicaciones Madrid Centro de Investigaciones Sociologicas ISBN 978 84 7476 631 8 OCLC 871814053 Datos Q2300244Obtenido de https es wikipedia org w index php title Vertice de corte amp oldid 135308411, wikipedia, wiki, leyendo, leer, libro, biblioteca,
