Page 64 - 4496

Означення 4. Маршрут М називається ланцюгом , якщо
кожне ребро в ньому зустрічається не більше ніж один раз і
простим ланцюгом , якщо кожна із вершин (можливо, крім
початової) зустрічається не більше одного разу. Якщо ланцюг
є замкненим, то його називають циклом ; якщо замкнений
простий ланцюг, то це буде простий цикл.
Визначення маршруту можна перенести і на орграф.
Маршрут в останньому називається шляхом. Простий цикл в
орграфі називається контуром.
Мінімальні шляхи у зважених орієнтованих
(неорієнтованих) графах.
Означення 1. Дві вершини v i w графа G називаються
зв’язаними, якщо існує маршрут із кінцями v і w. Граф
називається зв’язаним, якщо будь-яка пара його вершин є
зв’язаною.
Означення 2. Зв’язаністю графа називається мінімальна
кількість вершин, вилучення яких приводить до утворення
незв’язаного графа.
Означення 3. Орієнтований граф D=(V,E) є зваженим,
якщо кожній вершині із його дуг поставлено у відповідність
вагу l.
Для будь-якого зваженого орієнтованого графа
позначимо через l(M) суму ваг дуг, що утворюють шлях М.
При цьому кожна дуга враховується стільки разів, скільки
вона входить в шлях. Величину l(M) будемо називати вагою
шляху М у графі D.
Поставимо задачу. У зваженому графі D знайти такий
шлях М, щоб l(M) набуло мінімального значення.
Якщо у зваженому графі D є замкнені шляхи від’ємної
ваги, то для заданих вершин v і w, де v  w, мінімального
шляху з v до w не може бути.
Позначимо через D=(V,E)- зважений граф; V=( vi, ...
k
,vn), n  2. Введемо величину  i , де i  n , 1 , k  2 , 1 ,... . Для
величина  k  min l (M )
фіксованих і та k i v  за умови,
1 v i
що М містить не більше ніж k дуг; якщо таких шляхыв нема,
k  
то  i .
61