En teoría de grafos, un grafo dirigido es llamado fuertemente conexo si para cada par de vérticesu y v existe un camino de u hacia v y un camino de v hacia u. Los componentes fuertemente conexos (CFC) de un grafo dirigido son sus subgrafos maximales fuertemente conexos. Estos subgrafos forman una partición del grafo.
Un grafo dirigido, y sus componentes fuertemente conexos.
Un subgrafo fuertemente conexo es maximal si contiene todos los vértices del grafo o si al agregarle un vértice cualquiera deja de ser fuertemente conexo.
Aplicar búsqueda en profundidad sobre (el grafo traspuesto) iniciando la búsqueda en los nodos de mayor a menor tiempo de finalización obtenidos en la primera ejecución de búsqueda en profundidad (paso 1)
El resultado será un bosque de árboles. Cada árbol es un componente fuertemente conexo.
Las dos búsquedas en profundidad y la construcción del grafo reverso consumen tiempo lineal, de manera que el tiempo total es también lineal. En 2002, se publicó[4] una prueba simplificada de corrección de este algoritmo.
I. Wegener, A simplified correctness proof for a well-known algorithm computing strongly connected components, Information Processing Letters, 83 (2002) 17-19.
Datos:Q2003238
Agosto 04, 2021
componente, fuertemente, conexo, teoría, grafos, grafo, dirigido, llamado, fuertemente, conexo, para, cada, vértices, existe, camino, hacia, camino, hacia, componentes, fuertemente, conexos, grafo, dirigido, subgrafos, maximales, fuertemente, conexos, estos, s. En teoria de grafos un grafo dirigido es llamado fuertemente conexo si para cada par de vertices u y v existe un camino de u hacia v y un camino de v hacia u Los componentes fuertemente conexos CFC de un grafo dirigido son sus subgrafos maximales fuertemente conexos Estos subgrafos forman una particion del grafo Un grafo dirigido y sus componentes fuertemente conexos Un subgrafo fuertemente conexo es maximal si contiene todos los vertices del grafo o si al agregarle un vertice cualquiera deja de ser fuertemente conexo El calculo de los componentes fuertemente conexos de un grafo es uno de los problemas fundamentales de la Teoria de los grafos El primer algoritmo que trabaja en tiempo lineal para resolver este problema fue propuesto por Robert Tarjan 1 en 1970 a base de una busqueda en profundidad depth first search Otros algoritmos aparecen en los principales textos sobre algoritmica 2 3 La complejidad de este algoritmo es O V E Algoritmo EditarPara encontrar los componentes fuertemente conexos se puede utilizar el algoritmo de Kosaraju el cual funciona de la siguiente forma Sea G V E displaystyle G V E un grafo dirigido Aplicar busqueda en profundidad sobre G Calcular el grafo traspuesto Aplicar busqueda en profundidad sobre G t displaystyle G t el grafo traspuesto iniciando la busqueda en los nodos de mayor a menor tiempo de finalizacion obtenidos en la primera ejecucion de busqueda en profundidad paso 1 El resultado sera un bosque de arboles Cada arbol es un componente fuertemente conexo Las dos busquedas en profundidad y la construccion del grafo reverso consumen tiempo lineal de manera que el tiempo total es tambien lineal En 2002 se publico 4 una prueba simplificada de correccion de este algoritmo Vease tambien EditarComponente teoria de grafos Referencias Editar R E Tarjan Depth First search and linear graph algorithms SIAM J Comp 1 1972 146 60 A V Aho J E Hopcroft J D Ullman Data Structures ans Algorithms Addison Wesley MA 1983 T H Cormen C E Leiserson R L Rivest Introduction to Algorithms MIT Press Cambridge MA 1990 I Wegener A simplified correctness proof for a well known algorithm computing strongly connected components Information Processing Letters 83 2002 17 19 Datos Q2003238Obtenido de https es wikipedia org w index php title Componente fuertemente conexo amp oldid 136164624, wikipedia, wiki, leyendo, leer, libro, biblioteca,
