En teoría de grafos, una arista de corte, puente[1] o istmo[2] es una arista que al ser eliminada en un grafo incrementa el número de componentes conexas de este.[1] Equivalentemente, una arista es un puente si y sólo si no está contenida en ningún ciclo.
Un grafo con 6 aristas de corte (marcadas en rojo).
El concepto de arista de corte se puede generalizar a un conjunto de aristas. Así, un corte de aristas-l o corte de líneas-l es un conjunto de l aristas que si se quitan, desconectan el grafo. Por lo tanto, una arista de corte es un corte de aristas-1.[1]
Análogamente, un vértice de corte o punto de corte, es un vértice que al eliminarse incrementa el número de componentes conexos del grafo. La conectividad de un grafo se puede calcular en términos del número de aristas o vértices de corte que posee. Esta conectividad es una medida de su cohesión o robustez.[1]
Un importante problema abierto que involucra puentes es la conjetura del ciclo de doble cobertura,[3] propuesta por Seymour y Szekeres (1978 y 1979, independientemente), que establece que todo grafo sin puentes admite un conjunto de ciclos que contiene cada arista exactamente dos veces.
Recuero, A. (1994). «Aplicaciones de la teoría de grafos: búsqueda de caminos en una red y análisis de su conectividad». Informes de la construcción (CSIC) 46 (433). doi:10.3989/ic.1994.v46.i433.1115.
The Cycle Double Cover Conjecture
Bibliografía
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:Q2532492
Marcha 11, 2022
arista, corte, teoría, grafos, arista, corte, puente, istmo, arista, eliminada, grafo, incrementa, número, componentes, conexas, este, equivalentemente, arista, puente, sólo, está, contenida, ningún, ciclo, grafo, aristas, corte, marcadas, rojo, concepto, aris. En teoria de grafos una arista de corte puente 1 o istmo 2 es una arista que al ser eliminada en un grafo incrementa el numero de componentes conexas de este 1 Equivalentemente una arista es un puente si y solo si no esta contenida en ningun ciclo Un grafo con 6 aristas de corte marcadas en rojo El concepto de arista de corte se puede generalizar a un conjunto de aristas Asi un corte de aristas l o corte de lineas l es un conjunto de l aristas que si se quitan desconectan el grafo Por lo tanto una arista de corte es un corte de aristas 1 1 Analogamente un vertice de corte o punto de corte es un vertice que al eliminarse incrementa el numero de componentes conexos del grafo La conectividad de un grafo se puede calcular en terminos del numero de aristas o vertices de corte que posee Esta conectividad es una medida de su cohesion o robustez 1 Un importante problema abierto que involucra puentes es la conjetura del ciclo de doble cobertura 3 propuesta por Seymour y Szekeres 1978 y 1979 independientemente que establece que todo grafo sin puentes admite un conjunto de ciclos que contiene cada arista exactamente dos veces Indice 1 Aplicaciones 2 Vease tambien 3 Referencias 4 BibliografiaAplicaciones EditarEn analisis de redes sociales un puente o arista de corte es considerada una conexion o lazo interpersonal crucial entre dos actores 1 Vease tambien EditarVertice de corte Agujero estructuralReferencias Editar a b c d e Wasserman y Faust 2013 Grafos y matrices por Dawn Iacobucci pp 121 188 Recuero A 1994 Aplicaciones de la teoria de grafos busqueda de caminos en una red y analisis de su conectividad Informes de la construccion CSIC 46 433 doi 10 3989 ic 1994 v46 i433 1115 The Cycle Double Cover ConjectureBibliografia 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 Q2532492 Obtenido de https es wikipedia org w index php title Arista de corte amp oldid 135308418, wikipedia, wiki, leyendo, leer, libro, biblioteca,
