Grafo connesso

grafo avente un'unica componente connessa

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.

Un grafo connesso con 4 nodi e 4 archi

NoteModifica

  1. ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. MIT Press, 2009 (terza edizione).

Voci correlateModifica

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica