Grafo conexo
En teoría de grafos, un grafo conexo o conectado[1] es un grafo en que todos sus vértices están 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 máximos 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 débilmente conexo, mientras que sí se considera el sentido, se habla de componente fuertemente conexo.
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.
Conectividad en grafos dirigidos editar
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]
Véase también editar
Referencias editar
- ↑ a b c d Wasserman y Faust, 2013, «Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.
- ↑ 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 editar
- 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.
Datos: Q230655
