Grafo connesso
![Abbozzo](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0e/Puzzle_stub.svg/45px-Puzzle_stub.svg.png)
Questa voce sull'argomento teoria dei grafi è solo un abbozzo.
Contribuisci a migliorarla secondo le convenzioni di Wikipedia.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7e/CPT-Graphs-undirected-unweighted-ex1.svg/150px-CPT-Graphs-undirected-unweighted-ex1.svg.png)
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[1]. 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.
Note
- ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. MIT Press, 2009 (terza edizione).
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)