GRAFO CONECTADO

Grafo conectado

Un grafo se considera conectado si, para cualquier par de vértices, existe un trayecto que los une. En los grafos dirigidos debe tomarse en cuenta la dirección de las aristas para esta definición, formando el par de vértices en cualquier orden.

En la figura de arriba, el grafo no dirigido está conectado gracias a la bidireccionalidad pero el grafo dirigido no lo está, porque no hay ningún trayecto que termine en A, por ejemplo:

• Existe trayecto desde A hasta C: (A, B) y luego (B, C)
• No existe trayecto desde C hasta A: (C, D) y luego (D, B) solamente.

Por lo tanto, no se cumple la existencia de trayecto para cualquier par de vértices.