Un grafo es doblemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no tiene vértices de corte, esto es, vértices tales que al quitarlos el grafo resultante se vuelve disconexo.
En ciencias de la computación, es posible determinar si un grafo es conexo usando un algoritmo de búsqueda en anchura (BFS) o búsqueda en profundidad (DFS). En términos matemáticos, la propiedad de un grafo de ser (fuertemente) conexo permite establecer con base en él una relación de equivalencia para sus vértices, la cual lleva a una partición de estos en componentes (fuertemente) conexas, es decir, porciones del grafo, que son (fuertemente) conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos.
En un grafo dirigido, se distingue entre los siguientes tipos de conectividad:[1]
grafo débilmente conexo: todos los pares de vértices están débilmente conectados, es decir, unidos por un «semicamino» (camino que no considera la dirección de las aristas);
grafo unilateralmente conexo: todos los pares de vértices están unilateralmente conectados, es decir, unidos por un camino que va desde uno hasta el otro;
grafo fuertemente conexo: todos los pares de vértices están fuertemente conectados, es decir, unidos por al menos dos caminos, uno que va desde uno hasta el otro, y viceversa;
grafo recursivamente conexo: todos los pares de vértices están recursivamente conectados, es decir, están fuertemente conectados y el camino desde uno hasta el otro usa los mismos vértices y aristas que los del camino inverso.
Si se cumple alguno de estos tipos de conexiones, entonces se cumplen todos los tipos anteriores.[1]
Carrasco Pacheco, José Luis; Contreras Ordaz, Marco Antonio (2017). Modelado dinámico por inspección para convertidores de potencia CD a CD commutados: Un enfoque basado en grafos. Universidad Tecnológica de la Mixteca. Consultado el 25 de abril de 2021.
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:Q230655
Noviembre 04, 2021
grafo, conexo, teoría, grafos, grafo, conexo, conectado, grafo, todos, vértices, están, conectados, camino, grafo, dirigido, semicamino, grafo, dirigido, grafo, conexo, denomina, grafo, disconexo, inconexo, subgrafos, conexos, máximos, grafo, dirigido, llaman,. En teoria de grafos un grafo conexo o conectado 1 es un grafo en que todos sus vertices estan conectados por un camino si el grafo es no dirigido 2 o por un semicamino si el grafo es dirigido Un grafo que no es conexo se denomina grafo disconexo o inconexo Los subgrafos conexos maximos de un grafo no dirigido se llaman componentes o componentes conexos 1 Para el caso de los grafos dirigidos si no se considera el sentido de las aristas se habla de componente debilmente conexo mientras que si se considera el sentido se habla de componente fuertemente conexo Grafo conexo Grafo disconexo con tres componentes Un grafo es doblemente conexo si cada par de vertices esta conectado por al menos dos caminos disjuntos es decir es conexo y no tiene vertices de corte esto es vertices tales que al quitarlos el grafo resultante se vuelve disconexo En ciencias de la computacion es posible determinar si un grafo es conexo usando un algoritmo de busqueda en anchura BFS o busqueda en profundidad DFS En terminos matematicos la propiedad de un grafo de ser fuertemente conexo permite establecer con base en el una relacion de equivalencia para sus vertices la cual lleva a una particion de estos en componentes fuertemente conexas es decir porciones del grafo que son fuertemente conexas cuando se consideran como grafos aislados Esta propiedad es importante para muchas demostraciones en teoria de grafos Indice 1 Conectividad en grafos dirigidos 2 Vease tambien 3 Referencias 4 BibliografiaConectividad en grafos dirigidos EditarArticulo principal Conectividad teoria de grafos En un grafo dirigido se distingue entre los siguientes tipos de conectividad 1 grafo debilmente conexo todos los pares de vertices estan debilmente conectados es decir unidos por un semicamino camino que no considera la direccion de las aristas grafo unilateralmente conexo todos los pares de vertices estan unilateralmente conectados es decir unidos por un camino que va desde uno hasta el otro grafo fuertemente conexo todos los pares de vertices estan fuertemente conectados es decir unidos por al menos dos caminos uno que va desde uno hasta el otro y viceversa grafo recursivamente conexo todos los pares de vertices estan recursivamente conectados es decir estan fuertemente conectados y el camino desde uno hasta el otro usa los mismos vertices y aristas que los del camino inverso Si se cumple alguno de estos tipos de conexiones entonces se cumplen todos los tipos anteriores 1 Vease tambien EditarComponente teoria de grafos Camino teoria de grafos Conectividad teoria de grafos Referencias Editar a b c d Wasserman y Faust 2013 Grafos y matrices por Dawn Iacobucci pp 121 188 Carrasco Pacheco Jose Luis Contreras Ordaz Marco Antonio 2017 Modelado dinamico por inspeccion para convertidores de potencia CD a CD commutados Un enfoque basado en grafos Universidad Tecnologica de la Mixteca Consultado el 25 de abril de 2021 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 Q230655 Obtenido de https es wikipedia org w index php title Grafo conexo amp oldid 135307887, wikipedia, wiki, leyendo, leer, libro, biblioteca,
