Page 23 - 4336

частто назиивається трикуттником.. Це циикл і ппростий цикл зз

наййменшоюю кількісстю вершшин.

Граф, що не ммає циклі ів, називвається аациклічнним.

1.4.2 ООрієнтоований грграф

Посліддовністьь дуг, у яякій кінеець кожнної поперредньої дуги e
і-1
збіггається з початтком нааступноїї e , називаєтьсся шляххом абоо
і
орієєнтованним марршрутомм. У шляху та самма дугаа можее

зусттрічатисся кількаа разів.

Початтком шлляху є ввершинаа v дугии e , а кінцем шляху єє
1
0
вершина v дуги e .
n
n
Довжииною оррієнтовааного мааршрутуу називаається ккількістьь

дугг, що вхоодять у ццей маршшрут.

Прикллад 1.7. Для гграфа, ззображеного наа рис. 1.10 а,,

прииведемо прикладди орієннтованихх маршррутів з вершинни v доо
0
вершини v :
6 6
1) v vv v v ; v vv v v ; v v v v - ддовжинии 3;
0 2 5 6
00 4 3 6
0 1 3 6
2) v vv v v v v - довжиини 5.
0 2 5 4 3 6

а б
РРисунок 1.10.

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

якоого зустррічаєтьсяя не білььше одноого разу,, а просттим ланццюгом ––

шляях, кожнна вершиина якогоо зустріччається нне більшше одногго разу.

23