Grafo Conexo

Un grafo es conexo si cualquier vértice V le pertenece al conjunto de vértices y es alcanzable por algún otro.

Otra definición es que es un grafo no dirigido de tal modo que para cualquier par de nodos existe al menos un camino que los une.

Un grafo no dirigido es conexo si existe un camino entre cualquier par de nodos que forman el grafo. Ejemplo:

Grafo conexo Grafo no conexo con dos componentes conexas

Un grafo es doblemente conexo si para cada par de vértices está conectado por al menos dos caminos disjuntos, es decir, se dice que es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.

Tema opcional: Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices, es decir, si para todo par de vértices (a, b) debe tener una arista e que los une.

Existe también llamado Grafo fuertemente conexo que es un grafo dirigido tal que para cualquier par de nodos existe un camino que los une.