Ścieżki i cykle

Ścieżką o długości $k$ w grafie $G=(V,A)$ nazywamy ciąg wierzchołków
i łuków

$$P=(v_1,e_1,v_2,e_2,...,v_i,e_i,v_{i+1},...,e_{k},v_{k+1})$$ (8.1)

takich, że $v_i \in V$ dla $i=1,...,k+1$, $e_i$ jest łukiem o końcach $v_i, v_{i+1}$ dla $i=1,...,k$, oraz $v_i \neq v_j$ dla $i \neq j$.

Rys. 8.2

O łuku $e_i=(v_i,v_{i+1})$ mówimy, że jest zgodny ze ścieżką $P$, zaś jeśli $e_i=(v_{i+1},v_i)$ mówimy, że $e_i$ jest niezgodny z $P$.
Na rysunku 8.2 łuki $e_1$ i $e_3$ są zgodne, zaś łuk $e_2$ niezgodny ze ścieżką $P=(v_1,e_1,v_2,e_2,v_3,e_3,v_4)$, o łukach $e_1=(v_1,v_2), e_2=(v_3,v_2), e_3=(v_3,v_4)$.
Jeśli, dodatkowo, założymy, że $v_1=v_n$ (przy zachowaniu $v_i \neq v_j$ dla wszystkich pozostałych przypadków), to ścieżkę () nazywamy cyklem.