Grafo conexo

Grafo conexo.

Grafo disconexo con tres componentes.

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.

Conectividad en grafos dirigidos

En un grafo dirigido, se distingue entre los siguientes tipos de conectividad:​

• 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.​

Véase también

• Componente (teoría de grafos)
• Camino (teoría de grafos)
• Conectividad (teoría de grafos)

Bibliografía

• 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