Cos'è un grafico attraversabile nella teoria dei grafi?

Nel contesto della teoria dei grafi, un grafo attraversabile è un grafo in cui è possibile attraversare tutti i vertici e gli spigoli. In altre parole, è un grafo che ci permette di visitare ogni vertice esattamente una volta e ritornare al vertice di partenza.

Un grafo attraversabile è anche conosciuto come grafo connesso, perché è un grafo in cui tutti i vertici sono collegati tra loro .

Ad esempio, consideriamo un semplice grafo con tre vertici A, B e C, dove c'è un bordo tra A e B, un bordo tra B e C e un bordo tra A e C. Questo grafico è attraversabile perché possiamo inizia dal vertice A, segui gli archi fino a B e poi a C, e ritorna ad A.

D'altra parte, un grafo con due componenti disconnesse, come due grafi separati, non è attraversabile perché non è possibile visitare ogni vertice esattamente una volta e ritornare al vertice di partenza.