Маршрут (теорія графів)

Маршрут (англ. walk) в графі — скінченна або нескінченна послідовність ребер S = {…, e, e₁, …, e_n,…} в якій кожні два сусідні ребра e_{i -1} і e_i мають спільну вершину тобто

e₀ = (v₀, v₁) (ребро e₀ інцидентне вершинам v₀, v₁ )

e₁ = (v₁, v₂)

e₂ = (v₂, v₃)

.   .   .

e_n = (v_n, v_n+1). 

Маршрут називають скінченним якщо він має початкову і кінцеву вершину. Якщо маршрут має початкову вершину, але не має кінцевої (або навпаки), то його називають односторонньо-нескінченним. Якщо маршрут не має початкової і кінцевої вершин то його називають двосторонньо-нескінченними. 

Довжина маршруту дорівнює кількості ребер у ньому (причому кожне ребро вказується стільки разів, скільки воно зустрічається в даному маршруті).

Якщо S має початкову вершину v₀ і кінцеву вершину v_n, то записують 

S = S(v₀, v_n) (тобто S — маршрут довжини n, який з'єднує вершини v₀ і v_n).

Маршрут M називається ланцюгом, якщо кожне ребро зустрічається в ньому не більше одного разу, і простим ланцюгом, якщо будь-яка вершина, крім, можливо, початкової, зустрічається в ньому не більш як один раз.

Маршрут називають циклічним або замкнутим якщо v₀ = v_n