Акушерство Анатомия Анестезиология Вакцинопрофилактика Валеология Ветеринария Гигиена Заболевания Иммунология Кардиология Неврология Нефрология Онкология Оториноларингология Офтальмология Паразитология Педиатрия Первая помощь Психиатрия Пульмонология Реанимация Ревматология Стоматология Терапия Токсикология Травматология Урология Фармакология Фармацевтика Физиотерапия Фтизиатрия Хирургия Эндокринология Эпидемиология

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

Означення 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 дуг; якщо таких шляхыв нема, то .