Page 31 - 4386

3 МАРШРУТИ НА ГРАФАХ

3.1 Маршрути в неорієнтованому графі

Маршрутом (шляхом) у графі G називається така

послідовність ребер M(e , e ,…, e ), у якій кожні два сусідніх
1
n
2
ребра e та e мають спільну вершину. У маршруті те саме ребро
i
i-1
може зустрічатися кілька разів. Іншими словами, маршрут – це
сукупність ребер, які об'єднані разом вершинами так, що можна

рухатися по них уздовж графа.

Початок маршруту – це вершина v , інцидентна ребру e і
0
1
не інцидентна ребру e . Кінець маршруту – це вершина v
2
n
інцидентна ребру e і не інцидентна e . Якщо ребра e , e (e ,
n-1
n
2
n-1
1
e ) - кратні, то необхідно додатково вказувати, яку із двох
n
інцидентних вершин вважати початком (кінцем) маршруту.
Маршрут довжини k - послідовність, що містить k ребер.

Іншими словами, довжиною маршруту називається кількість

ребер у ньому; при цьому кожне ребро враховується стільки

разів, скільки воно зустрічається в маршруті.

Надалі, маршруту з вершини v у вершину v будемо
0
n
позначати як v v v …v v .
n-1 n
0 1 2
Для систематичності міркувань введемо поняття

тривіальний або нуль-маршрут – маршрут, що складається з

єдиної вершини та має довжину 0. Інші маршрути вважаються

нетривіальними.

Маршрут, усі ребра якого різні, називається ланцюгом.

Ланцюг, що не перетинає себе, тобто не має вершин, що

повторюються, називається простим.

30