3. 11. Маршрути, ланцюги, та цикли.

Означення 1. Нехай G- неорієнтований граф. Маршрутом M у графі G називається така скінченна або не скінченна послідовність вершин і ребер, які чергуються.

{... vs , es , vs+1 , es+1 ,…, vn-1 ,en-1 , vn , e n ,…}.

і кожні два сусідні ребра es- 1 і es є інцидентними до вершини vs .

очевидно, маршрут M можна задати послідовністю вершин (…,vs-1, vs, vs+1,…) або послідовністю ребер (…,еs-1, еs, еs+1,…) .

Одне і те ж сааме ребро в маршруті може зустрічатись декілька разів. Якщо розглядати тільки скінченні маршрути, то існують перше е1 і останнє еn ребра. Вершина v0 інцидентна ребру e1 , називається початком маршруту. Якщо e1 та e2 — крайні, то потрібна спеціальна вказівка, яку із двох інцидент ним до них вершин вважати початком. Аналогічно означається кінець маршруту.

Означення 2. Вершини, інцидентні ребрам маршруту, крім початкової і кінцевої, називають внутрішніми або проміжними.

Означення 3. Нехай маршрут М(e1, e2,..., en) має початок v0 і кінець vn . Тоді його називають сполучним. Число ребер такого маршруту є його довжиною. Якщо v0 =vn , то маршрут М називають замкненим (циклічним). Відрізок (eі, eі+1,..., ej) скінченого або нескінченого маршруту М називають його ділянкою.

Означення 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, ... ,vn), n 2. Введемо величину , де , . Для фіксованих і та k величина за умови, що М містить не більше ніж k дуг; якщо таких шляхыв нема, то .