Grafo connesso

Un grafo connesso con 4 nodi e 4 archi

In teoria dei grafi, un grafo G = (V, E) è detto connesso se, per ogni coppia di vertici (u, v) ∈ V, esiste un cammino che collega u a v. Un sottografo connesso massimale di un grafo non orientato è detto componente connessa di tale grafo. Di conseguenza, un grafo è connesso se esso è composto di una sola componente connessa.

Se in un grafo esiste una coppia di vertici (u, v) ∈ V che non ammette un cammino che li colleghi, tale grafo si dice disconnesso.

Voci correlate

• Grafo
• Componente connessa (teoria dei grafi)

Collegamenti esterni

• (EN) Denis Howe, connected graph, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL