Визначення мінімального шляху на графі з ребрами довільної довжини

Размещено на http://www.allbest.ru/

Лабораторна робота № 3

Визначення мінімального шляху на графі з ребрами довільної довжини

граф інцидентність ребро вершина

Мета роботи - навчитися визначати оптимальний шлях (мінімальної довжини) у заданого графа, а також виконувати синтез графа (визначення ваги всіх ребер та індексів всіх вершин), що має задану структуру та заданий оптимальний шлях.

Короткі теоретичні відомості

Є багато підходів до визначення поняття “граф”. Наведемо одне з таких визначень. Нехай V - довільна множина, E - деяка сукупність пар вигляду (v_i, v_j), де v_i, v_j V (тобто сукупність пар елементів, що входять до множини V), причому в сукупності E можуть зустрічатися однакові пари. Тоді упорядкована пара G=(V, E), що складається з множини V та сукупності E, називається графом із множиною вершин V та множиною ребер E. Іншими словами, граф - це дві множини, що взаємно відповідають одна інший, - множина вершин та множина ребер (множина бінарних відношень вершин), кожне (ребро) з яких відповідає парі елементів (допускаються однакові елементи) з множини вершин.

Графи зручно зображати графічно (малюнком), що спричинило появу їхньої назви. При цьому елементи множини вершин V зображають крапками на площині, а ребра (v_i, v_j) - відрізками (прямолінійними або криволінійними), які з'єднують крапки v_i та v_j. Граф називається скінченним, якщо множини його вершин та ребер є скінченими (надалі розглядаються лише такі графи). Множину вершин графа G позначають V(G), а множину ребер - E(G). Кількість вершин графа n(G)=|V(G)| (кількість елементів V(G)). Кількість ребер графа m(G)=|E(G)| (кількість елементів E(G)). Кількість вершин графа називають його порядком.

Якщо елемент e (ребро) сукупності E є парою елементів (вершин) v та w: e=(v, w), то кажуть:

– вершини v та w суміжні;

– вершини v та w є кінцями ребра e;

– вершини v та w - інцидентні ребру e;

– ребро e - інцидентне вершинам v та w.

Іншими словами, якщо вершини є кінцями ребра, то вони інцидентні цьому ребру, а ребро - інцидентне їм. Два ребра називають суміжними, якщо обидва вони є інцидентними одній вершині (тобто мають спільну вершину). Кількість ребер, інцидентних деякій вершині v, називається локальним степенем або просто степенем вершини v.

Графічне представлення деяких прикладів графів наведено на рис. 1.

Рис. 1

Якщо множина ребер E порожня (рис.1, а), граф називається нуль-графом. Якщо множина вершин V є порожньою, то порожньою є також множина ребер E. Такий граф називається порожнім. Лінії, що зображають ребра графа, можуть перетинатися, але точки перетину не є вершинами (рис.1, б). Різні ребра можуть бути інцидентні одній і тій самій парі вершин (рис.1, в), такі ребра називаються кратними (випадок наявності однакових пар (v_i, v_j)). Граф, що містить кратні ребра, називається мультиграфом. Ребро може з'єднувати вершину саму з собою (рис.1, г), таке ребро називається петлею. Це випадок наявності пар (v_i, v_i). Граф із петлями та кратними ребрами називається псевдографом.

Якщо пара e=(v, w)E вважається впорядкованою, тобто суттєвим є порядок розташування кінців ребра (іншими словами, важливим є, яка вершина ребра є початком, а яка - кінцем), то таке ребро називається орієнтованим. В такому випадку (w, v)?(v, w). Граф, що містить лише орієнтовані ребра, називається орієнтованим.

Якщо немає різниці, яку вершину ребра вважати початком, а яку - кінцем, тобто (w, v)=(v, w), ребро є неорієнтованим. Граф, що містить тільки неорієнтовані ребра - неорієнтований. Іноді граф може містити як орієнтовані, так і неорієнтовані ребра (змішаний граф). Ребра орієнтованого графа прийнято називати дугами і позначати направленими відрізками (рис.1, д-з). Напрямки орієнтованих ребер позначаються стрілками. Орієнтований граф може мати кратні ребра (рис.1, е), петлі (рис.1, ж), а також петлі, що з'єднують одні й ті самі вершини, але у зворотних напрямках (рис.1, з). Кожному неорієнтованому графу можна поставити у відповідність орієнтований граф з тією самою множиною вершин та множиною ребер, в якій кожне ребро замінено двома орієнтованими ребрами, що є інцидентними тим самим вершинам та мають зворотні напрямки. Про дугу (w, v) кажуть, що вона виходить з вершини w та приходить в вершину v. Вершини w та v називають відповідно початком та кінцем дуги (w, v).

Задати граф означає задати множини його вершин та ребер, а також відношення інцидентності. Крім графічного, є інші способи задання графа. Якщо граф скінчений, для опису його вершин та ребер достатньо їх занумерувати. Нехай v₁, v₂, … v_n - вершини графа, e₁, e₂, … e_m - його ребра. Відношення інцидентності можна визначити матрицею, що має m рядків та n стовпчиків і складається з елементів е_ij. Стовбці відповідають вершинам графа, а рядки - його ребрам. Якщо ребро e_i є інцидентним вершині v_j, тоді елемент е_ij = 1, інакше е_ij = 0. Така матриця називається матрицею інцидентності звичайного графа і є одним зі способів його визначення. Для графа на рис. 2 - матриця інцидентності наведена в табл.1.

Рис. 2

Для орієнтованого графа прийнято, що елемент е_ij = -1, якщо вершина v_j є початком ребра e_i; е_ij = 1, якщо вершина v_j є кінцем ребра e_i; е_ij = б(-1, 0, 1), якщо e_i - петля інцидентної вершини v_j; інакше е_ij = 0.

Граф можна задати матрицею суміжності - квадратною матрицею д_ij, стовпцям і рядкам якої відповідають вершини графа. Для неорієнтованого графа д_ij дорівнює кількості ребер, інцидентних i-тій та j-тій вершинам (кількості ребер, що їх з'єднують), для орієнтованого графа цей елемент відповідає кількості ребер з початком в i-тій вершині та кінцем в j-тій вершині. Таким чином матриця суміжності неорієнтованого графа є симетричною (д_ij = д_ji), а орієнтованого - необов'язково. Якщо ж вона є все-таки симетричною, то для кожної дуги орієнтованого графа існує дуга, що з'єднує ті ж вершини, але в зворотному напрямку.

Матриця суміжності для графа на рис.2 наведена в таблиці 2.

Таблиця 1. Матриця інцидентності

Таблиця 2. Матриця суміжності

Маршрутом (шляхом) у графі називається така скінченна або нескінченна послідовність вершин і ребер, що чергуються: (… v₁, e₁, v_2, e₂, …, v_n-1, e_n-1, v_n, …), що кожні два сусідні ребра e_i-1 та e_i мають спільну інцидентну вершину v_i. В скінченних маршрутах існує перше та останнє ребра, а також перша (початок маршруту) та остання (кінець маршруту) вершини.

Граф називається зваженим, якщо на множині ребер визначено вагову функцію (кожному ребру поставлена у відповідність вага). Для будь-якого шляху М зваженого графу позначимо через l(M) суму ваг ребер, що входять у М. Величину l(M) будемо називати вагою (або довжиною) шляху М у зваженому графі. Шлях у зваженому графі з вершини w в вершину v, де w v, називається мінімальним, якщо він має найменшу вагу серед усіх шляхів з вершини w в вершину v.

Існує багато практичних задач, що зводяться до пошуку мінімального шляху на графах (задачі мінімізації транспортних, енергетичних, інформаційних тощо потоків, пошуку оптимальних послідовностей виконуваних дій, наприклад оптимальної послідовності запуску партій виробів тощо).

Розглянемо алгоритм знаходження оптимального за мінімумом довжини (найкоротшого) шляху в неорієнтованому графі з ребрами довільної довжини (ваги). Нехай задано граф, у якого відомо ваги всіх ребер та вершини якого пронумеровано за порядком. Також задано початкову та кінцеву вершини шляху (яка точка є початком, а яка є кінцем, значення не має). Позначимо початок шляху - А, кінець - В. Нехай вага ребра, що з'єднує i-ту та j-ту вершини, буде позначатися L_ij. Алгоритм передбачає присвоєння кожній вершині певного індексу (аналог потенціалу в електричних схемах) та має два етапи - етап визначення індексів всіх вершин та етап прокладання шляху по ребрам, вага яких рівна різниці індексів інцидентних вершин (вершин, які з'єднуються даним ребром). Отже,

1. Визначення індексів вершин (позначатимемо л_i індекс вершини v_i).

1.1. Приймаємо індекс вершини кінця шляху (В), рівний 0: л_(B) = 0.

1.2. Починаємо цикл по всім вершинам, починаючи з вершини В. Для кожної вершини, індекс якої відомий, виконуємо визначення індексів всіх суміжних вершин. Якщо індекси всіх суміжних вершин для даної буде визначено, то така вершина буде вважатися “пройденою” і біля неї поставимо галочку.

1.2.1. Починаємо цикл індексації по всім вершинам, сусіднім з даною. Для кожної сусідньої вершини виконуємо:

1.2.1.1. Визначення можливого індексу чергової вершини:

л_j = л_i + L_ij

(л_i - індекс вершини, відносно якої визначаємо);

1.2.1.2. Якщо індекс даної вершини, яку розраховуємо, ще не був визначений або є більший, ніж нове розраховане значення л_j, приймаємо його рівним новому значенню л_j, інакше - не змінюємо.

1.2.2. Повторюємо пп.1.2.1.1-1.2.1.2 для всіх вершин, сусідніх з даною. Після цього дану вершину вважаємо “пройденою” і біля неї поставимо галочку. Якщо при розрахунку індексів сусідніх вершин змінився індекс вершини, яка буда “пройденою”, вона перестає бути “пройденою” і галочка біля неї знімається.

1.2.3. Повторюємо п.1.2.1-1.2.2 доки всі вершини (крім А) не будуть “пройдені” (біля них будуть стояти галочки). Довжина шляху рівна індексу вершини А.

2. Визначення шляху.

2.1. Починаючи з вершини, що є початком шляху (А), визначаємо чергове ребро, по якому іде шлях. Це буде ребро, що з'єднує дану вершину v_j з вершиною v_i, різниця індексів яких в точності рівна вазі ребра:

л_j - л_i = L_ij

(л_j - останньої знайденої вершини, л_i - індекс вершини, що перевіряється на предмет того, щоб вона стала наступною в мінімальному шляху). Завжди знайдеться принаймні одне таке ребро, що з'єднує дану вершину з вершиною, відносно якої був порахований індекс даної.

2.2. Повторюємо п.2.1., поки не прийдемо в вершину В. Якщо на якомусь кроці пункту 2.1 задовольняє декілька ребер, маємо альтернативні шляхи і виконуємо далі п.2.1 для кожного із шляхів.

Цікавою представляється задача синтезу графа - побудови такого графа, в якому оптимальний шлях має бути таким, як заздалегідь визначено (наприклад, якщо треба спроектувати транспортну або інформаційну мережу так, щоб в ній певний потік проходив саме так, як визначено). Розглянемо алгоритм побудови (синтезу) графа (визначення ваги всіх ребер та індексів всіх вершин), що має задану структуру, заданий оптимальний шлях та якомога меншу сумарну вагу всіх ребер. Структура графу (набір вершин та ребер, що їх з'єднує), береться як у графа в задачі визначення оптимального шляху. Заданий шлях отримується дзеркальним відображенням знайденого шляху відносно горизонтальної прямої. Довжина шляху береться більшою (меншою) довжини знайденого шляху на константу, вказану викладачем. Алгоритм полягає в наступному:

1. Малюємо дзеркальний граф, на якому позначаємо заданий шлях. Розподіляємо загальну довжину заданого шляху по ребрам, що його складають (приблизно рівномірно).

2. Приймаємо індекс кінця шляху (В), рівний 0: л_(B) = 0.

3. Визначаємо індекси вершин, по яким проходить оптимальний шлях:

л_j = л_i + L_ij (поки не дійдемо до вершини А).

4. Визначаємо ваги інших ребер та індекси вершин (що не належать оптимальному шляху):

4.1.Для ребра, що має визначені індекси обох кінців:

4.1.1. Якщо вершина, якій відповідає більший індекс, належить оптимальному шляху - вага ребра рівна різниці індексів вершин плюс 1. Інакше - вага ребра рівна різниці індексів вершин (але не менша 1):

L_ij = л_j - л_i+1,

якщо л_j > л_i то л_j (AB)_min, інакше:

L_ij = max((л_j - л_i), 1).

4.2. Для вершини, індекс якої невідомий, визначаємо сусідню з мінімальним індексом. Індекс даної вершини буде на 1 більше індексу сусідньої вершини з мінімальним індексом.

4.3. Виконуємо 4.1-4.2 поки всі індекси вершин та ваги ребер не будуть визначені.

Виконання роботи

1. Виконано вручну пошук шляху мінімальної довжини між двома заданими викладачем вершинами А та В на графі, заданому за варіантом(Рис.3) .

Рис.3. Малюнок графу, на якому виконано пошук оптимального маршруту вручну

2. Виконано перевірку правильності вирішення задачі пошуку мінімального шляху на ЕОМ (Рис.4).

3. Виконано вручну синтез графа із оптимальним маршрутом, отриманим як дзеркальне відображення маршруту, знайденого в п.1 та п.2. Довжину маршруту прийняти більшою на 7 довжини знайденого шляху на константу, що вказується викладачем(Рис.5).

4. Виконано перевірку правильності синтезу графа на ЕОМ (Рис.6).

Рис.4. Знімок графу з програми, що засвідчує правильність вирішення задачі пошуку мінімального шляху на заданому графі.

Рис.5. Малюнок графа, на якому показано вирішення задачі синтезу графа вручну.

Рис.6.Знімок графу з програми, що засвідчує правильність вирішення задачі синтезу графа

Висновок

У ході лабораторної роботи було ознайомлено з визначенням оптимального шляху (мінімальної довжини) у заданого графа, а також з виконанням синтезу графа. Під час виконання даної лабораторної роботи було виконано пошук оптимального маршруту вручну, знайдено мінімальний шлях на заданому графі. Виконавши пошук мінімального шляху на ЕОМ, правильність вирішення задачі вручну підтвердилась. Було виконано вручну синтез графа із оптимальним маршрутом, отриманим як дзеркальне відображення вибраного маршруту, що був одержаний. При перевірці синтезу графа на ЕОМ, правильність виконаного вручну синтезу графа підтвердилась.

Размещено на Allbest.ru