Лекції з дискретної математики. Глава 4 Частина 1

n1.doc (1 стор.)
Оригінал



Глава 4. Зважений граф І орграфа




3

Визначення

.1. Функція ваги




Зваженим графом (Орграф) називається граф (орграф) зі зваженими вершинами і / або ребрами (дугами).

Під вершинно-зваженому графі (Орграф) вводиться додаткова функція E  R, R-речові числа, яка асоціюється з кожною вершиною графа (орграфа). Цю функцію можна розглядати як функцію, задану «вартість» вершини.

3.1.1. Графічне зображення


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



Зауваження






Далі будуть розглядатися реберно-зважені графи (орграф), які коротко будуть називатися зваженими графами (орграф).

3.1.2. Матричне уявлення


Зважена матриця суміжності






Для зваженого графа (орграфа) зважена матриця суміжності [A] розміру n  n, n = | V | задається наступним чином:


[A] =

w (v i, v j), якщо є ребро (дуга) з вершини v i в вершину v j;

0 в інших випадках,

де w (v i, v j) R - вага («вартість») ребра (дуги).

Для простих графів зважена матриця суміжності симетрична щодо головної діагоналі.

Приклад









Ріс.3.1.2. Зважена матриця суміжності графа і її графічне представлення

3.1.3. Таблиця інціденцій зваженого

г

Визначення

рафа і орграфа




Рядок таблиці інціденцій містить вершину V i з перерахуванням всіх інцидентних їй ребер (дуг) і їх вагами.

Приклад








3.2. Мінімальна каркасне

дерево графа


Визначення






Мінімальним каркасним деревом графа є каркасне дерево у зваженому графі, що має мінімальний загальна вага ребер.

Приклад






3.2.1. Алгоритм Краскала (Kruskal)


Визначення







Алгоритм Краскала створює ліс дерев. Спочатку ліс містить n простих дерев. На кожному кроці додається саме мінімальне по вазі ребро так, щоб воно єднало два дерева разом.

Якщо вибране ребро формує цикл, то воно відкидається.




Ініціалізація алгоритму:

  1. Створити ліс, що містить n тривіальних дерев по одній вершині в кожному дереві (немає ребер);

  2. Організувати пріоритетну чергу ребер графа, організовану в порядку зростання ваг ребер.

Виконання алгоритму:

  1. До тих пір, поки в дереві не з'явиться (n-1)-ребер,

виконати:

    1. Вибрати з черги ребро з найменшою вагою;

    2. Якщо ребро формує цикл, то відкинути його, інакше додати це ребро в ліс.

Псевдокод






Зауваження







  1. Кожен крок алгоритму Краскала буде з'єднувати два дерева разом, тому в кінці алгоритму вийде тільки одне дерево.

  2. Складність алгоритму O (mlogn), n = | V |, m = | E |.


Приклад








Ініціалізація:

1. Будується ліс з 5-ти тривіальних дерев




2. Пріоритетна чергу:

2 {a, e}, 4 {a, c}, 4 {b, d}, 5 {d, c}, 6 {a, b}, 6 {b, e}, 7 {d, e}, 8 {a, d}, 8 {c, e}, 9 {c, d}




Крок 3. Вибір з черги ребра 4 {b, d}. Циклів немає.

Крок 4. вибір з черги ребра 5 {b, c}. Циклів немає.






Крок 5. Вибір з черги ребра 6 {a, b}. З'являється цикл (a, b, c). Ребро 6 {a, b} відкидається.

Крок 6. Вибір з черги ребра 6 {b, e}. З'являється цикл (a, b, c, e). Ребро 6 (b, e) відкидається.

Крок 7. Вибір з черги ребра 7 {d, e}. З'являється цикл (a, b, c, d, e). Ребро 7 {d, e} відкидається.

Крок 8. Вибір з черги ребра 8 {a, d}. З'являється цикл (a, c, b, d). Ребро 8 {a, d} відкидається.

Крок 9. Вибір з черги ребра 8 {c, e}. З'являється цикл (a, c, e). Ребро 8 {c, e} відкидається.

Крок 10. Вибір з черги ребра 9 {c, d}. З'являється цикл (b, c, d). Ребро 9 {c, d} відкидається.

Алгоритм - стоп. Мінімальна каркасне дерево (см.шаг 4) має вагу 15.



Зауваження







Якщо розмірність зваженого графа зростає, то виникає очевидна трудність визначення циклу, що виникає при додаванні з черги ребра.

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



Ш аг 1. Із пріоритетною черзі вибираємо ребро {g, h}, яке створює перше нетривіальне дерево. Червоний колір вибраний описувачем цього дерева. Число ребер дерева дорівнює 1.

Крок 2. Ребро {c, i} з пріоритетною черзі створює друге нетривіальне дерево. Синій колір вибраний описувачем цього дерева. Число ребер каркасного дерева дорівнює 2.




Крок 3. Ребро {f, g} увійшло в перше нетривіальне дерево, тому вершина g - червона, а f - біла. Червоний колір залишився описувачем цього дерева. Число ребер каркасного дерева - 3.




Крок 4. Ребро {a, b} створює третю нетривіальне дерево. Зелений колір стає описувачем цього дерева. Число ребер каркасного дерева дорівнює 4.



Крок 5. Додаємо ребро {c, f}. Вершина c - синя, вершина f - червона. Ребро {c, f} яет перше і друге дерева. Червоний колір вибраний як описувача цього об'єднаного дерева. Число ребер каркасного дерева дорівнює 5.



Крок 6. Ребро {g, i} має однакові червоні описувачі вершин, отже, воно створює цикл. Відкидаємо його.



Крок 7. Ребро {c, d}: вершина з має червоний колір, вершина d - біла. Додаємо її до дерева. Описувачі дерева - червоні. Число ребер каркасного дерева дорівнює 6.


Крок 8. Вершини h і i ребра {h, i} - червоні. Ребро створює цикл, відкидаємо його.




Крок 9. Ребро {a, h} - вершина a - зелена, вершина h - червона. Додаємо ребро {c, d} до дерева. Червоний колір залишається описувачем цього дерева. Число ребер каркасного дерева дорівнює 7.




Крок 10. Вершини b і c ребра {b, c} - червоні. Додавання цього ребра призведе до створення циклу. Відкидаємо його.



Крок 11. Ребро {d, e}: вершина d - червона, а вершина e - біла. Додаємо це ребро до дерева. Вершини дерева - червоні. Число ребер каркасного дерева дорівнює 8, алгоритм стоп.



Вага мінімального каркасного дерева = 38

Зауваження






Навіть якщо продовжити виконання алгоритму Краскала все залишився в пріоритетною черзі ребра будуть створювати цикли.

3.2.2. Алгоритм Прима (Prim)


Визначення






Алгоритм Прима характеризується наступним:





Ініціалізація алгоритму:

  1. Вибрати будь-яку вершину графа (корінь дерева).

Виконання алгоритму:

  1. До тих пір, поки в дереві не з'явиться n-1 ребер, виконати:

    1. Створити чергу знаходяться поза дерева і інцидентних вершині. Чергу організувати в порядку зростання ваг ребер.

    2. Вибрати з черги ребро з найменшою вагою.

    3. Якщо ребро формує цикл, то відкидаємо його, інакше додати це в дерево.

Псевдокод



Складність алгоритму - O (mlogn), n = | V |, m = | E |.


Приклад






Ініціалізація:

Початкова вершина (корінь дерева) - вершина а.

У дереві n-1 = 5-1 = 4 ребра



Зауваження







Як і для алгоритму Краскала, в алгоритмі Прима для визначення циклів можна скористатися описувач вершин, при цьому знадобляться визначники двох типів - для вершин дерева (червоний колір) і для всіх інших вершин (білий колір).

При додаванні ребра до споруджуваного дереву перевіряються кольору вершин:


Приклад












3.2.3. Мінімальна каркасне дерево для точок на евклідовій площині



Визначення







Евклідовому мінімальним каркасним деревом (Euclidean minimum spanning tree - EMST) є мінімальне каркасне дерево безлічі точок на площині (або в більш загальному випадку під багатовимірному просторі), де ваги ребер між кожною парою точок буде відстанню між цими двома точками.

Перший алгоритм розв'язання задачі






  1. Будується повнозв'язну граф, зв'язуючий задані n точок.

  2. Розраховуються відстані між усіма вершинами графа за формулою

((X i-x j) 2 + (y i - y j) 2) 1/2. Ці відстані приймаються в якості ваг ребер графа.

  1. Алгоритмом Крускала або Прима будується мінімальне каркасне дерево отриманого зваженого графа.

Приклад






Координати точок (x, y):

  1. (5,80);

  2. (34,93);

  3. (25,65);

  4. (50,65);

  5. (5,51);

  6. (33,41);

  7. (66,51);

  8. (15,10);

  9. (50,20);

  10. (75,30);

  11. (95,39);

  12. (84,9).






Мінімальна каркасне дерево,

загальна довжина 280,75


Визначення






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

Тріангуляцію можна уявити собі як планарний граф, внутрішні області (області, обмежені ребрами) якого є трикутниками.

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

Другий алгоритм рішення







  1. По заданому безлічі точок на площині (кожна точка є вершиною графа) побудувати триангуляцию Делоне.

  2. В якості ваг ребер взяти їх довжину.

  3. Використовувати алгоритм Прима або Краскала для знаходження мінімального каркасного дерева.


Зауваження






  1. Борис Миколайович Делоне запропонував цей метод тріангуляції в 1934 році в роботах з обчислювальної геометрії.

  2. Існують ефективні алгоритми побудови тріангуляції Делоне.



3.3. Мінімальні каркасні дерева

з

Визначення
обмеженнями



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

У літературі можна знайти понад 30 варіантів двухкрітеріальних мінімальних каркасних проблем, а також кілька багатокритеріальних проблем.

3.3.1. Мінімальна каркасне дерево

із заданим ступенем


Визначення


Якщо зажадати, щоб ступінь мінімального каркасного дерева не перевищувала заданого числа, тобто deg (Т) = k, k 2, то виникає проблема знаходження мінімального каркасного дерева із заданим ступенем. Далі для стислості ця проблема буде називатися k - MST проблемою (k-Minimum Spanning Tree problem).

2-MSP проблема є проблемою знаходження Гамільтона шляху мінімальної довжини.

Клас складності






k-MST проблема відноситься до NP-важкою при будь-якому k.

Алгоритми для k-MST проблеми на евклідовій площині






При завданні графа G на евклідовій площині вага його ребер є відстань між суміжними вершинами. Для даного випадку було доведено, що існує мінімальне каркасне дерево зі ступенем не більше 5. Однак при k = 3 проблема NP-важка, при k = 4 докази немає.

Для вирішення k-MST проблеми на евклідовій площині існують евристичні алгоритми полиномиального часу (зокрема, модифікований алгоритм Прима (k-Prim algorithm)).

Вельми успішно застосовуються різні версії генетичних і еволюційних алгоритмів.


3.3.2. Мінімальна каркасне дерево з максимальним числом листя


Визначення






Для заданого зваженого ненаправленного графа G = (V, E) знайти мінімальне каркасне дерево Т з максимальним числом листя.

Клас складності






П
Алгоритми
роблема відноситься до NP-важкою.



Відомі досить хороші апроксимаційні алгоритми, кращий з має складність майже лінійну в розмірах графа. Апроксимаційні відношення алгоритмів - 2,5 - 3,0.

3.3.3. Каркасне дерево з найкоротшою

про

Визначення
бщей довжиною шляху



Заданий зважений ненаправлений граф G = (V, E) і позитивне ціле число B. Чи каркасне дерево T = (V, F), F E, таке, що сума всіх шляхів між всіма можливими парами вершин u і v в цьому дереві не перевищувала величину B?

Клас складності






П
Алгоритми
роблема відноситься до NP-важкою.



Є евристичні алгоритми, що дозволяють отримати апроксимаційні відносини 2,15 / 8 і 3/2 за час О (n 2 + f (G)), O (n 3) і O (n 4) відповідно, де f (G) - час обчислення найкоротших шляхів між всіма парами вершин графа G, а n - число вершин графа G.

3.3.4. Каркасне дерево з обмеженням діаметра


Визначення


Для заданого зваженого зв'язного графа знайти мінімальне каркасне дерево із заданою нижньою межею діаметра D 2.

Клас складності






Проблема відноситься до NP-важкою для 4 D n-1, де n - число вершин графа.

Алгоритми






Точні алгоритми дозволяють отримати за розумне на практиці час рішення для повного графа розміром менше 100 вершин. Є жадібні евристичні алгоритми, засновані на алгоритмі Прима, а також еволюційні алгоритми вирішення проблеми.

3

Визначення
.3.5. Каркасне дерево оптимальної зв'язку




Заданий зв'язний ненаправлений граф G = (V, E). На ребрах графа задані:

  1. Запити зв'язку або передачі. Задаються матрицею запитів R = [r ij], де r ij - кількість навантаження, необхідне передати між вершинами v i і v j.

  2. Відстані між вершинами v i і v j. Задаються матрицею відстані w [v i, v j].

Знайти мінімальне каркасне дерево Т = (V, F), F E, з мінімальною вагою

W (T) = f (w ij, r ij).

У багатьох випадках розглядаються функції f виду f = w ij * r ij, де * - операція множення.

Клас складності






Проблема є NP-важкою.

Алгоритми




За останні 10-15 років для вирішення проблеми було запропоновано велику кількість еволюційних і генетичних алгоритмів.

3.3.6. Проблема багатоцільового мінімального каркасного дерева


Визначення






Для заданого зв'язного ненаправленного графа G = (V, E) з n вершинами для кожного ребра задається K> 1 невід'ємних цілих числа. Ці числа визначають K атрибутів на ребрах графа w ij = (w ij 1, w ij 2,..., w ij K). Тоді проблема знаходження багатоцільового каркасного дерева формулюється наступним чином:

на каркасному дереві Т графа G мінімізувати W = (W 1, W 2,..., W K), де W k = w i, j k, k 1 ... K.

Дана мінімізація може і не дати мінімум за всіма компонентами W. У цьому випадку потрібно знайти безліч каркасних дерев S * S (це безліч називається оптимальним безліччю Парето (Pareto)).

3

Визначення
.3.7. Проблема багатоцільового мінімального каркасного дерева із заданим ступенем



Якщо до проблеми знаходження багатоцільового мінімального каркасного дерева обмеження по величині ступеня дерева, то в результаті вийде проблема багатоцільового мінімального каркасного дерева із заданим ступенем.

Клас складності






Дана проблема NP-важка.

3

Визначення
.3.8. Узагальнене мінімальне каркасне дерево



Кластерами розбиття вершин графа на кілька груп за певною ознакою. Прикладом такого розбиття можуть служити кліки графа.

Проблема узагальненого мінімального каркасного дерева (The Generalized Minimum Spanning Tree Problem - GMSTP) формулюється таким чином.

Заданий ненаправлений зв'язний граф G = (V, E) і V є об'єднанням K кластерів V k, k = 1,2, K, кластерів вершин графа. Ненегативна матриця вартості C = [c ij] асоціюється з ребрами E.

GMSTP вимагає побудови мінімального за вартістю каркасного дерева, що містить принаймні одну вершину з кожного кластера (проблема L-GMSTP).

Існує інше формулювання проблеми:

Знайти мінімальне по вартості каркасне дерево, що містить точно одну вершину з кожного кластера (проблема E-GMSTP).



Клас складності





В обох формулюваннях проблема є NP-важкою.

Зауваження







Вперше проблема E-GMSTP була досліджена в 1995 році, а проблема L-GMSTP - в 2000-2001 рр..

Алгоритми





Різні точні алгоритми рішення застосовні для графів з кількістю вершин від 100 до 200.

Є ряд евристичних і генетичних алгоритмів алгоритмів, що дозволили вирішити проблему з числом вершин графа близько 500.

    1. Д

      Визначення

      ерев Штейнера (Steiner)



Нехай G = (V, E) буде графом, у якому кожне ребро має позитивний дійсний вагу. У графі G задається безліч N термінальних вершин, V  N. Решта вершини (V \ N) називаються нетермінальний вершинами або вершинами Штейнера.

Дерево Т, побудоване на графі G, є мінімальним деревом Штейнера або просто деревом Штейнера, якщо це дерево містить всі термінальні вершини N (зауважимо, що в дереві Штейнера можуть міститися нетермінальні вершини або вершини Штейнера).

Приклад









Термінальні вершини:

N = {1,3,6}


Ріс.3.4.1. Дерево Штейнера (виділено жирним)

з точками Штейнера {2,4,5}

Клас складності







Проблема знаходження мінімального дерева Штейнера відноситься до NP-важкою.

Точні алгоритми






Відомі точні алгоритми вирішення проблеми дерева Штейнера, однак вони мають експоненційну складність.

Евристичні алгоритми






До проблеми пошуку дерев Штейнера зводяться багато важливі практичні задачі. Тому література з евристичним алгоритмам з даної проблеми обширна.

У вирішенні проблеми Штейнера є два крайніх випадку, коли вони вирішуються в поліноміальний час:

- N = V, коли проблема зводиться до пошуку мінімального каркасного дерева;

- N = 2, коли проблема зводиться до пошуку мінімального шляху між двома вершинами.

Евристичний алгоритм злиття найкоротших шляхів

(The Merged Shortest Paths Heuristic - SPATH)







Заданий граф G = (V, E), | V | = n, | E | = m, невід'ємні цілочисельні ваги ребер і термінальні вершини F V.

Опис алгоритму:

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

Якщо найкоротший шлях вибирається за допомогою алгоритму Дейкстри, то складність алгоритму дорівнює O (zn 2), де n - число вершин графа, z - число термінальних вершин.



Дерево Штейнера з евклідової метрикою





Величезний практичний інтерес представляє рішення проблеми дерева Штейнера на площині. Для будь-яких двох пар вершин графа u = (u x, u y) і v = (v x, v y), заданих координатами на площині, відстань задається в L p - метриці (1  p  ):

| | Uv | | p = (| u x - v x | p + | u y - u y | p) 1 / p.

Для двох спеціальних випадків:





Алгоритм побудови дерева Штейнера з евклідової метрикою





На площині задано N точок, з F - термінальні.

Алгоритм приблизного побудови дерева Штейнера:

  1. Побудувати повнозв'язну граф G '= (N, E') на вершинах N. Відстанню між двома вершинами цього графа буде найкоротша відстань між цими вершинами. Взяти ці відстані в якості ваг.

  2. Знайти мінімальне каркасне дерево Т 'повнозв'язну графа G'.

  3. Підставити мінімальне каркасне дерево T 'в вихідний граф G. Замінити кожне ребро дерева T 'мінімальним шляхом вихідного графа G. В результаті вийде новий граф T'' (не завжди T'' буде деревом).

  4. Знайти каркасне дерево графа T'', яке буде приблизними деревом Штейнера.

Апроксимаційні відношення цього алгоритму дорівнює 2.

Приклад









G = (V, E)

N = {A, B, C, D}

G '= (N, E')




Ріс.3.4.4. Побудова дерева Штейнера (виділено жирним)

Зауваження






Е

Приклад

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









Вихідна задача

Дерево Штейнера

(Довжина = 9)

Дерево Штейнера з додатковими вершинами Штейнера

(Довжина = 7)


Ріс.3.4.5. Рішення задачі Штейнера в прямокутних координатах

    1. Дерева Штейнера з обмеженнями

      1. Д

        Визначення
        ерев Штейнера з обмеженням ступенів



Заданий простий зв'язковий ненаправлений G = (V, E) cn вершинами, невід'ємними вагами ребер c ij, підмножиною термінальних вершин Z V і обмеженнями ступенів вершин k i 2.

Проблемою Штейнера з обмеженнями на ступені вершин (The Degree-constrained Steiner Problem - DCSP) є знаходження на графі дерева Т такого, що ступінь кожної вершини дерева deg (i) k i, а сума ваг ребер цього дерева мінімальна серед усіх можливих дерев з обмеженнями на ступені вершин.

Клас складності





Клас складності DCSP - NP-важка.

Алгоритми





Точні алгоритми рішення DCSP (алгоритм перерахування каркасних дерев і динамічний програмний алгоритм) мають складність O (p 2 2 (n - p) + n 3) і O (n3 p + n 2 лютого p + n) відповідно. Отримати рішення в приемлимое час для графа з десятком вершин проблематично.

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

      1. Д

        Визначення
        ерев Штейнера з обмеженням запізнювання



Заданий простий зв'язний ненаправлений граф G = (V, E) і дві вагові функції на ребрах графа: функція вартості з ij і функція запізнювання D ij. Обидві функції є цілими позитивними числами. Крім того, задана вершина-витік s і термінальні вершини S V.

Проблема знаходження дерева Штейнера з обмеженням запізнювання:

Знайти дерево Штейнера за умови, сума запізнювань всіх шляхів цього дерева від вершини s у всі термінальні вершини не перевищує деякої позитивної величини .

Клас складності





Клас складності даної проблеми - NP-важкий.

Алгоритми







Є декілька евристичних алгоритмів вирішення даної проблеми.



      1. Про

        Визначення

        бобщенное дерево Штейнера





Заданий граф G = (V, E), вершини якого розбиті на кластери, а ребра мають невід'ємні цілі ваги c ij.

Проблема узагальненого дерева (The Generalized Steiner Tree Problem - GSTP) формулюється двома способами:

Клас складності





Проблеми L-GSTP і E-GSTP відносяться до NP-важкою.

1 Термін «тріангуляція» по-різному трактується в обчислювальній геометрії, геодезії, теорії графів та інших областях.
Навчальний матеріал
© ukrdoc.com.ua
При копіюванні вкажіть посилання.
звернутися до адміністрації