En teoría de grafos, un grafo conexo o conectado es un grafo en que todos sus vértices están conectados por un camino (si el grafo es no dirigido) 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. 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.
En un grafo dirigido, se distingue entre los siguientes tipos de conectividad:
Si se cumple alguno de estos tipos de conexiones, entonces se cumplen todos los tipos anteriores.
Escribe un comentario o lo que quieras sobre Grafo conexo (directo, no tienes que registrarte)
Comentarios
(de más nuevos a más antiguos)