Деякі визначення

Маршрути, ланцюги і цикли

Нехай G - неорієнтований граф.

Визначення. Маршрутом в G називається скінченна або нескінченна послідовність ребер S = {…, e ₀, e ₁, …, e_n, …} в якій кожні два сусідні ребра e_{i - 1} і e_i мають спільну вершину, тобто

e ₀ = (v ₀, v ₁)

e ₁ = (v ₁, v ₂)

e ₂ = (v ₂, v ₃)

...

e_n = (v_n, v_{n + 1}).

Визначення. Якщо в S немає ребер, які стоять перед e ₀, то v ₀ називається початковою вершиною S; якщо немає ребер після e_{n - 1}, то v_n - кінцевою вершиною. Якщо вершина v_i належить і e_{i - 1} і e_i, то вона називається внутрішньою.

Визначення. Якщо маршрут S має початкову і кінцеву вершини, то він називається скінченним; якщо S має початок і не має кінцевої вершини (або навпаки), то він називається односторонньо-нескінченним; якщо немає ні початкової вершини ні кінцевої – то двосторонньо-нескінченними. Якщо S має початкову вершину v ₀ і кінцеву v_n, то позначається

S = S (v ₀, v_n)

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

Визначення. Якщо v ₀ = v_n, то маршрут називається циклічним.

Визначення. Якщо v_i і v_j - дві вершини маршруту S, то

S (v_i, v_j) = (e_i, …, e_{i + 1}, …, e_{j - 1})

називається підмаршрутом.

На рис.5 маршрут S = (e ₁, e ₂, e ₃, e ₄, e ₅) є скінченним, має довжину 5, початкову вершину v ₁ і кінцеву v ₅. Маршрут S = (e ₂, e ₃, e ₄) є підмаршрутом даного маршруту.

Рис.5

Визначення. Ланцюг – це маршрут, кожне ребро якого зустрічається рівно один раз. Циклічний ланцюг називається циклом.

Визначення. Нециклічний ланцюг називається простим, якщо в ньому жодна вершина не повторюється. Цикл з початком (і кінцем) в v ₀ називається простим, якщо в ньому жодна вершина, крім v ₀ не повторюється.

Зрозуміло, що частина ланцюга або циклу теж є ланцюгом або циклом.

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

Дата добавления: 2014-11-29