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

Маршрут (англ. 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

Джерела

Дискретний аналіз: Навч.-метод. посібник для самост. вивч. дисц. / О. Д. Шарапов, Д. Є. Семьонов, В. Д. Дербенцев. — К.: КНЕУ, 2002. — 126 с. ISBN 966—574–380–5
Дискретна математика: підручник для студ. вищих тех. навч. закладів / Ю. М. Бардачов, Н. А. Соколова, В. Є. Ходаков; За ред. В. Є. Ходакова. — К. : Вища школа, 2002. — 288 с. ISBN 966-642-090-2
Нікольський Ю. В., Пасічник В. В., Щербина Ю. М. Дискретна математика. — К.: Видавнича група BHV, 2007. — 368 с.: іл. ISBN 966-552-201-9