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

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

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

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

e₀ = (v₀, v₁)

e₁ = (v₁, v₂)

e₂ = (v₂, v₃)

. . .

e_n = (v_n, v_n_{+ 1}).

Визначення. Якщо в S немає ребер, які стоять перед e₀, то v₀ називається початковою вершиною S; якщо немає ребер після e_n_-₁, то v_n - кінцевою вершиною. Якщо вершина v_i належить і e_i_- ₁ і 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₀ не повторюється.

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

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

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Частини, суграфи і підграфи графу.	\|	Зв’язаність

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.003 сек.