Page 21 - 4336

e ) - кратнні, то ннеобхіднно додатково ввказуватии, яку із двохх
n
інциидентниих вершиин вважаати почаатком (кіінцем) ммаршрутуу.

Маршршрут доввжини kk - послідовністть, що ммістить kk ребер..

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

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

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

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

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

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

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

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

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

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

Прикллад 1.5. Визнаачити мможливіі маршшрути тта їхнюю

доввжину з ввершинии v у v в графі, зображееному наа рис. 1.99 а.
0
8

а б
Риссунок 1.99 – Прикклади мааршрутівв

Розв'язок.

З вершшини v вв v ведууть, напрриклад, ннаступніі маршруути:
8
0
1) v vv v - доввжини 2;
0 3 8
2) v vv v v v - довжини 4;
0 1 2 3 8
3) v vv v v v -- довжинни 4;
0 3 4
7 8
21