Drumuri într-un graf

Numim drum într-un graf o succesiune de muchii adiacente și distincte care conectează două vârfuri din graf (numite capetele drumului). Un drum se numește simplu dacă muchiile care îl compun sunt distincte. Numim ciclu un drum care are drept capete un același vârf.

Dacă P = x₀, ..., x_k-1 este un drum în graful G și x_k-1x₀ este o muchie în acest graf, atunci P + x_k-1x₀ este un ciclu din graful G.

Un ciclu se numește hamiltonian dacă este simplu și trece prin toate nodurile grafului G, exact o dată, și se numeșteeulerian dacă trece prin toate muchiile grafului G, exact o dată. Nu orice graf conține un ciclu hamiltonian (Fig. 2).

Spunem că S este un subgraf al lui G, dacă acesta conține o parte din vârfurile lui G și numai acele muchii care le conectează.