КДМ ЛК 7.6 (1)

1. Розділ 5. Теорія графів

2. 5.10. Дерева

⚫ орієнтовані і бінарні дерева
⚫ дерева пошуку
⚫ дерева прийняття рішень

3.

➢ Зв'язний граф Т без циклів називається деревом.
➢ Орієнтація може не враховуватися, і тоді говорять
про ребра дерева уi. Якщо орієнтація враховується,
то говорять про дуги дерева, а саме дерево
називається орієнтованим, наприклад, дерево
логічних можливостей, генеалогічне дерево.

4.

Для графа G з n вершинами і m ребрами
рівносильні такі властивості:
1. G зв'язний і не має циклів.
2. G зв'язний, і число його вершин на одиницю
перевершує число ребер: n = m + 1.
3. G не містить циклів і n = m + 1.
4. G не містить циклів, але додавання ребра між
будь-якими двома несуміжними вершинами
призводить до появи циклу.
5. G зв'язний, але втрачає цю властивість при
видаленні будь-якого ребра.
6. Будь-які дві вершини xi xk графа G з'єднує
єдиний ланцюг.

5.

➢ Граф G = (X, Y) називається позначеним, якщо його
вершинам
привласнені
фіксовані
позначки,
наприклад, номери 1, 2, ..., n.
➢ Два позначених графа однакові (не різняться),
якщо їхні вершини позначені однією системою
позначок та існує ізоморфізм одного графа на
інший, при якому зберігаються позначки всіх
вершин.
Формула А.Келі Число n позначених дерев з n
вершинами дорівнює nn-2
➢ Важливий клас графів утворюють дерева з однією
позначеною вершиною, яка називається коренем.
Само дерево з однією позначеною («виділеною»)
вершиною називається кореневим деревом.

6. Орієнтовані і бінарні дерева

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

7. Кореневе дерево

r =1
рівень 0
2
4
3
5 6
8
рівень 1
7
9
рівень 2
10
рівень 3

8.

➢ Нащадок v вершини u — це вершина v, в яку веде
шлях з вершини u; при цьому u називається предком
для v.
➢ Якщо довжина цього шляху дорівнює 1, тобто з u до v
веде дуга, то u — «батько» для v, a v — «син» для u.
➢ Вершина, що не має нащадків, називається листом.
➢ Висота дерева — це число дуг найдовшого шляху,
тобто висота кореня.
➢ Рівень вершини v — це довжина шляху з кореня у v.
➢ Упорядкованим деревом називається дерево, в якого
множина синів кожної вершини упорядкована.
➢ Дерево висотою h називається збалансованим, якщо
всі його листки розташовані на рівнях h або h+1.

9.

➢ Бінарним
(двійковим) деревом Т називається
упорядковане дерево, з кожної вершини якого може
виходити не більше двох дуг.
➢ Лівим
піддеревом
вершини
u
називається
максимальне піддерево Tl(ul) T, коренем якого є
лівий син ul вершини u. Відповідно праве піддерево
Tr(ur) вершини u визначається як максимальне
піддерево з коренем ur — правим сином вершини u.
r =1
2
4
3
5
8
6
7
9
10

10.

Найпростіший варіант комп'ютерного задання
двійкового дерева Т – за допомогою двох масивів:
ЛІВИЙ СИН і ПРАВИЙ СИН. Якщо вершини Т
занумеровані числами від 1 до n, то в масиві
ЛІВИЙ СИН [і]=k коли вершина 'k' є лівим сином
вершини 'і', та [і]=0 коли вершина 'і' не має лівого
сина.
і
r =1
2
4
8
Л 2 4 6 0 8 0 9 0 0 0
3
5 6
П 3 5 7 0 0 0 10 0 0 0
7
9
1 2 3 4 5 6 7 8 9 10
10
Найбільш
зручний
для
комп'ютерної обробки варіант
задання двійкового дерева Т – за
допомогою списку.

11.

Велика кількість задач як для графів, так і для дерев,
вимагають перегляду всіх вершин і ребер графа G у певному
порядку. Найбільш поширений так званий алгоритм «пошуку
у глибину» (або DFS-метод від англ. depth first search). У ході
роботи алгоритму використовують структуру даних, яку
називають стеком, що працює за принципом „останнім
прийшов — першим вийшов". Додавання й вилучення
елементів у стеку відбувається з одного кінця, який називають
верхівкою стеку.
r =1
2
6
3
4
5
7
8
9
10

12.

Алгоритм пошуку вглиб у простому зв'язному
графі
1)
2)
3)
4)
Почати з довільної вершини x. Виконати DFS(x):= 1.
Включити цю вершину в стек.
Розглянути вершину у верхівці стеку: нехай це вершина х.
Якщо всі ребра, інцидентні вершині х, позначено, то перейти
до кроку 4, інакше — до кроку 3.
Нехай (х,у) — непозначене ребро. Якщо DFS(y) уже
визначено, то позначити ребро (х,у) штриховою лінією та
перейти до кроку 2. Якщо DFS(y) не визначено, то позначити
ребро (х,у) потовщеною суцільною лінією, визначити DFS(y)
як черговий DFS-номер, включити цю вершину в стек і
перейти до кроку 2.
Виключити вершину х зі стеку. Якщо стек порожній, то
зупинитись, інакше — перейти до кроку 2.
Щоб вибір номерів був однозначним, доцільно домовитись,
що вершини, суміжні з тією, яка вже отримала DFS-номер,
аналізують за зростанням їх порядкових номерів (або в
алфавітному порядку).

13.

Вершина
4a
5f
3d
2c
6e
1b
7g
8h
b
с
d
а
f
e
g
h
-
DFSномер
1
2
3
4
5
6
7
8
-
Вміст
стеку
b
bc
bcd
bcda
bcd
bc
bcf
bcfe
bcfeg
bcfe
bcf
bc
bch
bc
b

14.

Часто використовується перегляд графа «пошуком у ширину»
(або BFS-метод від англ. breadth first search), при якому у
кожній черговій вершині переглядаються всі інцидентні їй
ребра без виключення і всі їх кінцеві вершини (тобто
«оточення» вершини X). У ході реалізації алгоритму
використовують структуру даних, яку називають чергою, що
використовує принцип „першим прийшов — першим
вийшов". Елемент включається у хвіст черги, а виключається
з її голови.
r =1
2
3
4
5
8
6
7
9
10

15.

Алгоритм пошуку вшир у простому зв'язному
графі
1)
2)
3)
4)
Почати з довільної вершини x. Виконати BFS(x):= 1.
Включити вершину x у чергу.
Розглянути вершину, яка перебуває на початку черги; нехай
це буде вершина х. Якщо для всіх вершин, суміжних із
вершиною х, уже визначено BFS-номери, то перейти до
кроку 4, інакше — до кроку 3.
Нехай (х, у) — ребро, у якому номер BFS(у) не визначено.
Позначити це ребро потовщеною суцільною лінією,
визначити BFS(у) як черговий BFS-номер, включити
вершину у у чергу й перейти до кроку 2.
Виключити вершину х із черги. Якщо черга порожня, то
зупинитись, інакше — перейти до кроку 2.
Щоб результат виконання алгоритму був однозначним,
вершини, які суміжні з вершиною х, аналізують за
зростанням їх порядкових номерів.

16.

Вершина
7a
4f
3d
2c
8e
1b
5g
6h
b
с
d
f
g
h
a
e
-
DFSномер
1
2
3
4
5
6
7
8
-
Вміст
черги
b
bc
bcd
cd
cdf
cdfg
cdfgh
dfgh
dfgha
fgha
fghae
ghae
hae
ae
e

17. Бінарне дерево пошуку

Бінарне дерево забезпечує дуже зручний метод
організації даних, у разі використання якого
можна легко знайти будь-які конкретні дані чи
виявити,
що
їх
немає.
Очевидно,
що
найнеефективніший
спосіб
пошуку
—
послідовний перегляд усіх даних. Справді, якщо
потрібних даних немає, то для виявлення цього
потрібно переглянути весь список. Бінарне дерево
пошуку дає змогу уникнути цього. Єдина вимога
— уведення для даних якогось лінійного порядку.
Ним може бути, наприклад, алфавітний або
числовий порядок. Лінійно впорядкувати можна
теги, покажчики, файли чи інші ключі, які
визначають дані.

18.

Приклад лінійно впорядкованого дерева - проекції
номерів вершин на пряму дають правильну
послідовність чисел.
r =5
2
7
1
4
3
1
23
6
9
8
456
78
10
9
10

19.

У бінарному дереві пошуку кожній вершині
присвоєно значення, яке називають ключем.
➢ Ключ
— це елемент якоїсь лінійно впорядкованої
множини: будь-які два її елементи можна порівняти.
Під час побудови бінарного дерева пошуку
використовують його рекурсивну властивість, яку
можна описати так. Кожна вершина розбиває дерево
на два піддерева. Ліве піддерево містить лише ключі,
менші від ключа цієї вершини, а праве — ключі,
більші від ключа вершини. Ця властивість
повторюється для кожної вершини.

20.

Алгоритм додавання об'єкта до дерева
1)
2)
3)
4)
5)
Почнемо з дерева, що містить лише одну вершину.
Означимо її як корінь. Перший об'єкт списку
присвоюємо кореню: це ключ кореня. Щоб додати
новий об'єкт, виконуємо таку процедуру:
Почати з кореня.
Якщо об'єкт менший, ніж ключ у вершині, то
перейти до лівого сина.
Якщо об'єкт більший, ніж ключ у вершині, то
перейти до правого сина.
Повторювати кроки 2 та 3, доки не досягнемо
вершини, яку не визначено (тобто її немає).
Якщо досягнуто невизначену вершину, то визначити
(тобто додати) вершину з новим об'єктом як
ключем.

21.

Приклад побудови дерева для такого списку:
{m,a,c,h,i,n,e,b,o,x}.
m
a
n
o
c
b
h
e
x
i

22.

Алгоритм пошуку об'єкта в дереві
1)
2)
3)
4)
5)
6)
Застосовують той самий підхід, що для побудови
дерева.
Почати з кореня.
Якщо об'єкт менший, ніж ключ у вершині, то
перейти до лівого сина.
Якщо об'єкт більший, ніж ключ у вершині, то
перейти до правого сина.
Якщо об'єкт дорівнює ключу у вершині, то об'єкт
знайдено; виконати потрібні дії й вийти.
Повторювати кроки 2, 3 та 4, доки не досягнемо
вершини, яку не визначено.
Якщо досягнуто невизначену вершину, то даний
об'єкт не зберігається в дереві; виконати потрібні
дії й вийти.

23.

Приклад пошуку у дереві для такого списку: {x,d}.
d< m <x
d> a
n <x
o <x
c <d
b
h >d
d> e
i
d?
x

24.

Алгоритм видалення об'єкта з дерева
1)
2)
3)
Можливі три випадки:
вузол, що видаляється, не має нащадків, тобто є
листком дерева;
вузол, що видаляється, має одного нащадка;
вузол, що видаляється, має двох нащадків.
Перший випадок найпростіший – вузол просто
видаляється.
У другому випадку на місце вузла, що
видаляється, ставиться його нащадок.
Найскладнішим є випадок, коли вузол, що
видаляється, має двох нащадків.

25.

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

26.

Приклад видалення вузла, що не має нащадків.
m
a
n
o
c
b
h
e
x
i

27.

Приклад видалення вузла, що має одного нащадка.
m
a
n
ox
c
b
h
e
x
i

28.

Приклад видалення вузла, що має двох нащадків.
m
a
n
o
c
b
h
e
x
i

29.

Приклад видалення вузла, що має двох нащадків.
i
a
n
o
c
b
h
e
x

30.

Найбільша кількість порівнянь, потрібних для
додавання або пошуку об'єкта, дорівнює висоті
дерева. Якщо дерево збалансоване, то його висота
[log(n+1)]. Отже, у цьому разі для додавання чи
локалізації об'єкта потрібно не більше ніж [log(n+1)]
порівнянь.
Бінарне
дерево
пошуку
може
розбалансуватись унаслідок додавання нових
об'єктів, тому потрібен алгоритм ребалансування
(тобто
відновлення
збалансованості).
Проте
процедура додавання об'єкта, яка відновлює
збалансоване дерево, навряд чи завжди доцільна, бо
відновлення
збалансованості
дерева
після
випадкового додавання — досить складна операція.
Тому розглядають також збалансованість із дещо
послабленими вимогами.

31.

➢ АВЛ-дерево — бінарне дерево, у якому висоти двох
піддерев кожної з його вершин відрізняються не
більше ніж на одиницю.
Таке
означення
збалансованості
широко
використовують на практиці; його ввели 1962 р.
Г.М.Адельсон-Вельський і Є.М.Ландіс.

32. Ребалансування АВЛ-дерева

Висота АВЛ-дерева незалежно від кількості
вершин
ніколи
не
перевищує
висоту
збалансованого дерева більше, ніж на 45 %.
➢ Відносно АВЛ-дерева балансування вершини - це
операція, яка у випадку різниці висоти лівого та
правого піддерев =2, змінює зв’язки предокнащадок у піддереві даної вершини так, що
різниця стає <= 1, або нічого не змінює. Вказаний
результат отримують обертами піддерева даної
вершини. Використовують чотири типи обертів.

33.

Малий правий оберт – використовується, коли
h(b) – h(L) = 2 та
h(C) h(R).
Великий правий оберт – використовується, коли
h(b) - h(L) = 2 та
h(c) > h(R).

34.

Малий лівий оберт – використовується, коли
h(b) – h(R) = 2 та
h(C) h(L).
Великий лівий оберт – використовується, коли
h(b) - h(R) = 2 та
h(c) > h(L).

35. Дерева прийняття рішень

Кореневі дерева можна застосовувати для
розв'язування задач прийняття рішень. Для цього
використовують дерева прийняття рішень, або
дерева рішень. Кожному листку такого дерева
поставлено у відповідність рішення зі скінченної
множини відомих рішень, а кожній внутрішній
вершині v — перевірку умови P(v). Прийняття
рішень за допомогою такого дерева полягає в
побудові простого шляху від кореневої вершини до
листка. Під час побудови шляху виконують
перевірку умов у внутрішніх вершинах дерева.
Значення умови P(v) у вершині v задає ребро, яке
буде додано в шлях після вершини v. Кінцева
вершина
побудованого
шляху
відповідає
прийнятому рішенню.

36.

Приклад. Серед восьми монет одна фальшива, вона
має меншу вагу. Знайдемо цю монету зважуваннями
на балансових терезах за допомогою якнайменшої
кількості зважувань. Занумеруємо монети числами
1,2,...,8. Порівнюємо вагу груп монет 1,2,3 та 4,5,6.
Якщо одна із цих груп виявиться легшою, то це
означає, що фальшива монета є в цій групі, і її можна
виявити другим зважуванням. У разі балансу терез
фальшива одна з монет 7 або 8, що також можна
виявити другим зважуванням. Очевидно, що
кількість зважувань дорівнює висоті дерева, тобто
двом.

37.

Відповідне дерево рішень:
1
3
2 7
8 4
6
5

38.

У багатьох практичних задачах потрібно приймати
рішення стосовно досліджуваних об'єктів, відносячи
їх до певних класів, тобто надаючи цим об'єктам
класифікаційних ознак. Якщо ці ознаки наперед
відомі, такі задачі називають задачами класифікації.
Для об'єктів, щодо яких рішення вже прийнято,
узагалі кажучи, невідомі правила отримання ними
класифікаційних ознак. Тому задача прийняття
рішень відносно нових об'єктів полягає в пошуку
правил, за якими надано такі ознаки.
Для побудови дерев рішень застосовують алгоритм
ID3, запропонований 1983 р. Куїнланом (J. Quinlan).
Цей алгоритм будує дерево рішень і на основі
прикладів генерує правила.

39. Алгоритм Куїнлана

1.
Якщо вершині дерева прийняття рішень поставлено
у відповідність множину прикладів R і всі ці
приклади мають однакове значення атрибута
прийняття рішення d, то цю вершину визначають як
листок дерева і позначають цим значенням d.
2.
Якщо для певної вершини умови кроку 1 не
виконано, то розгляюають множину умовних
атрибутів А. Якщо А≠Ø, то вибирають довільний
атрибут а А; нехай множина його значень Еа={е1,
е2,…, еk}.

40.

Цю вершину позначають атрибутом а, сам атрибут а
вилучають із множини А й виконують наступні дії:
– У вершині а утворюють ребра е1, е2,…, еk ( їх
кількість становить |Еа|, і кожне ребро
позначають елементом множини Еа.
– Множину прикладів R вершини а розбивають на
підмножини з однаковим значенням атрибута а
(усього таких підмножин k, значення атрибута а в
першій підмножині дорівнює е1, у другій – е2, …,
у k-й - еk).
– Кінцю ребра еj ставлять у відповідність
підмножину прикладів, у яких значення атрибута
а дорівнює еj.
Якщо на кроці 2 виявиться, що А= Ø, то щодо
вершини, яка має стати листком, приймають
рішення залежно від специфіки задачі.

41.

Приклад
Побудуємо дерево рішень для наведеної в таблиці інформації
щодо проведення змагань із тенісу залежно від погоди.
Ден
Погода Температура Вологість Вітер Гра
ь
D1
Сонце
Спека
Висока Слабкий Ні
D2
Сонце
Спека
Висока Сильний Ні
D3 Хмари
Спека
Висока Слабкий Так
D4
Дощ
Помірно
Висока Слабкий Так
D5
Дощ
Холод
Норма
Слабкий Так
D6
Дощ
Холод
Норма
Сильний Ні
D7 Хмари
Холод
Норма
Сильний Так
D8
Сонце
Помірно
Висока Слабкий Ні
D9
Сонце
Холод
Норма
Слабкий Так
D10
Дощ
Помірно
Норма
Слабкий Так
D11 Сонце
Помірно
Норма
Сильний Так
D12 Хмари
Помірно
Висока Сильний Так
D13 Хмари
Спека
Норма
Слабкий Так

42.

Гра – це атрибут прийняття рішень. Множина всіх умовних
атрибутів А={погода, температура, вологість, вітер}
відповідає кореневій вершині. Виберемо атрибут погода й
позначимо ним кореневу вершину. Множина значень цього
атрибута складається з трьох елементів: сонце, хмари, дощ.
Кореневій вершині поставимо у відповідність три ребра,
кожному із яких припишемо значення атрибута погода.
Множину прикладів розібємо на 3 множини А й отримаємо
множину А={температура, вологість, вітер}, яка відповідає
кожній із вершин 2, 3, 4 дерева.

43.

Розглянемо вершину 2. Їй відповідає підмножина прикладів
{D9,D11}, які мають значення атрибута прийняття рішень
так, і підмножина прикладів {D1, D2, D8}, які мають
значення атрибута ні. Виберемо наступний атрибут із
множини А; нехай це температура. Позначимо ним вершину
2, побудуємо три ребра зі значеннями цього атрибута й
розіб’ємо множину прикладів у вершині 2 на три
підмножини, у кожній із яких значення температури
однакові.
У вершині 5 приклади D1, D2 мають однакові значення (ні)
атрибута гра. Тому цю вершину позначимо ні, і вона стане
листком. Аналогічно, вершину 7 позначимо так, і вона
також стане листком. Вилучимо атрибут температура з
множини А. Одержимо множину А={вологість, вітер}.
Вершину 6 позначимо атрибутом вологість.

44.

45.

Розглянемо два листки, які відповідають значенням так і ні
відповідно для прикладів D11 і D8. Вилучимо атрибут
вологість із множини А і отримаємо А={вітер}. Тепер
розглянемо вершину 3. Усі приклади, приписані цій вершині,
мають значення так атрибута гра, тому ця вершина являє
собою листок; позначимо її так. У вершині 4 приклади
мають різні значення атрибута гра, тому припишемо їй
атрибут вітер, який має два значення: слабкий і сильний. Ці
значення припишемо ребрам, інцидентним вершинні 4.
Множину прикладів розібємо на дві підмножини: {D4, D5,
D10} зі значенням так і {D6} зі значенням ні.

46.

47.

Вибираючи іншу послідовність атрибутів і обходу вершин,
можна одержати інше дерево рішень.

48.

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

49. 5.11. Остови (каркаси) графа

⚫ остовне дерево графа
⚫ найкоротші відстані та шляхи

50. Остовне дерево графа

➢ Остовом або каркасом графа G=(X,Y) називається
підграф Н=(X,YH) без циклів, що містить всі
вершини X і максимально велике число ребер.
Якщо граф зв'язний, то остов є дерево, якщо G
містить p компонент зв'язності, то остов
складається з р дерев.
Два остови у G вважаються різними, якщо вони
відрізняються хоча б одним ребром. Для того щоб
G мав більше одного остова, необхідно і достатньо
існування хоча б одного циклу в G.

51. Алгоритм побудови остовного дерева

1)
2)
3)
Задача побудови якого-небудь (одного!) остовного дерева у
графі G=(X,Y) належить до числа найважливіших для
практики. Основна ідея побудови полягає у послідовному
відборі ребер, що не утворюють цикли з попередніми.
Вважаємо i=1. Вибираємо у G=(X,Y) довільну вершину vi X,
що утворює підграф Тi, який є деревом.
Якщо i=n, то задачу розв'язано, і Тi – шукане остовне дерево
графа G. В іншому випадку переходимо до кроку 3.
Нехай уже побудовано дерево Тi, що є підграфом G і містить
деякі вершини v1,...,vi, де 1 i n-1. Будуємо граф Тi+1,
додаючи до Тi нову вершину vi+1 X\{v1,...,vi}, суміжну в Тi з
деякою вершиною vj, та нове ребро, інцидентне вершинам vj
і vi+1. Очевидно граф Тi+1 також є деревом. Вважаємо i=i+1 і
переходимо до кроку 2.

52.

Приклад побудови остова.
a
f
d
c
e
b
g
h

53.

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

54. Остів мінімальної ваги

➢ Зваженим
графом називається граф G=(X,Y),
кожному ребру якого приписана вага — додатне
число сi=с(yi)>0 (іноді сi 0). Вагою графа з G
називається сума ваг його ребер.
Задача відшукання остова найменшої ваги у графі
G часто зустрічається у застосуваннях: при
проектуванні комп'ютерних і кабельних мереж,
ліній електропостачання, трубопроводів, доріг
тощо. Роль вершин графа G відіграють відповідно
комп'ютери, комп'ютерні центри, абоненти і
передавачі (у кабельних мережах), джерела і
споживачі електроенергії, води, газу і т. д. Роль
ребер yi і ваг сi зваженого графа G відіграють
припустимі шляхи прокладки кабелів, труб, доріг
та їх вартості.

55. Алгоритм Дж. Краскала знаходження остова мінімальної ваги

Ідея алгоритму полягає в тому, що на кожному кроці
алгоритму обирається найкоротше ребро, що не утворює
цикл з обраними раніше ребрами.
1 крок. В вихідному графі G = (X, Y) будується підграф Т1=(X,Y1)
з одним pебром u1 = у1 мінімальної ваги .
Крок k. Якщо граф Тk-1 = (X, Yk-1) без циклів вже побудований,
обираємо ребро uk Y\Yk-1 так, щоб воно не утворювало
циклу з ребрами Yk-1 і мало найменшу вагу серед всіх таких
ребер. Будуємо граф Тk, приєднуючи до графа Тk-1 ребро uk;
Тk=(X,Yk), Yk=Yk-1 {uk}, k=2,3,..., n-1.
Зауваження. Іноді треба побудувати остів максимальної
ваги у графі G. Алгоритм Краскала повністю розв'язує цю
задачу, якщо у ньому всюди мінімальну вагу замінити на
максимальну.

56.

Приклад. Знаходження остову мінімальної ваги.
b
7
7
2
3
4
a
c
d
g
3
2
e
3
2
f

57. Найкоротші відстані та шляхи

Задачі відшукання найкоротших відстаней між
вершинами графа із заданими вагами ребер часто
зустрічаються на практиці і мають очевидний
економічний зміст. Це ж можна сказати і про
задачі пошуку оптимальних шляхів у орієнтованих
графах.
Нехай G=(X,Y) — зважений орієнтований зв'язний
граф з додатними довжинами (вагами) дуг с(у) 0,
треба знайти найкоротший шлях (з мінімальною
сумою ваг дуг) з вершини s до вершини t графа.
Ефективний алгоритм було запропоновано
Е.Дейкстрою у 1959р.

58.

Ідея алгоритму Дейкстри така. Якщо вже знайдено довжини
(ваги) l(xi) найкоротших шляхів з вершини s і вказано
(«пофарбовано») ті вершини х1=s, х2, .., хk, до яких ведуть ці
шляхи, то «черговий» за довжиною шлях із s до (k+1)-ї вершини
хk+1 у кінці цього шляху можна знайти за таким правилом.
Позначимо через Xk={xi}ki=1 множину пофарбованих вершин.
Для кожної непофарбованої вершини w переглянути довжини
с(xi,w) дуг (xi,w), xi Xk, w Wk = X\Xk і знайти
min{с(xi, w)} = c(v0, w0), v0 Xk, w0 Wk.
Коли вершини xi, w не суміжні, то с(xi,w)= . Якщо с(xi,w)= для
всіх xi Xk і всіх w Wk, то алгоритм зупиняється: всі вершини w
множини Wk і, зокрема, вершина t не досяжні із s. Якщо існує
хоча б одна дуга з множини вершин Xk у множину Wk, тоді
мінімум min{с(xi,w)} скінченний і вершину w0 буде знайдено.
Шуканий («черговий» за довжиною) шлях веде з вершини s до
вершини w0, довжина цього шляху дорівнює l(v0)+c(v0,w0).
Можемо пофарбувати вершину w0, тобто привласнити їй
позначення хk+1=w0, покласти l(хk+1)=l(v0)+c(v0,w0) і сформувати
більш широку множину пофарбованих вершин
k +1
X k +1 = xi i=1
Процес закінчується, якщо хk+1=t.

59.

Формально в алгоритмі пофарбованій вершині x Xk
привласнюється постійна позначка l(х) — довжина
найкоротшого шляху із s до х. Якщо вершина w Wk ще не має
постійної позначки, тобто не пофарбована, їй привласнюється
тимчасова позначка l(w), що дорівнює довжині найкоротшого
(s,w)-шляху, що проходить тільки по вершинам з постійними
позначками (пофарбованим). Тимчасова позначка вершини w,
взагалі кажучи, змінюється від кроку до кроку і перестає
змінюватися, коли вершина w фарбується (одержує постійну
позначку).
Практично на k-му кроці алгоритму будується кореневе дерево
Тk( Тk-1) від кореня s до вершин множини Xk з постійними
позначками. На останньому кроці k0 вершина t стає кінцевою
вершиною дерева .
Зауваження. Алгоритм Дейкстри може знаходити найкоротші
відстані між парами вершин у неорієнтованому зв'язному
зваженому графі G з додатними вагами ребер с(у). Для його
застосування слід перейти до орієнтованого симетричного
графа, замінивши кожне ребро парою протилежно спрямованих
дуг однакової ваги.

60. Алгоритм Дейкстри побудови найкоротших шляхів із вершини s

Крок 1. Привласнення початкових значень.
Покласти l(s)=0 і вважати цю позначку постійною (тобто
пофарбувати вершину s). Покласти l(w)= для всіх вершин
w s і вважати ці позначки тимчасовими. Покласти р=s
(р — ім'я останньої вершини, що одержала постійну
позначку).
Крок 2. Оновлення позначок.
Для кожної непофарбованої вершини w, у яку веде дуга
(р,w) з вершини р, позначка l(w) змінюється за правилом
l(w) = min{l(w), l(p)+с(р,w))}.

61.

Крок 3. Перетворення позначки у постійну.
На множині всіх непофарбованих вершин (з тимчасовими
позначками) Wp знайти вершину w0 з мінімальною
позначкою: l ( w0 ) = min{ l ( w)}
w W p
Зробити позначку вершини w0 постійною і покласти р=w0.
Крок 4. (Якщо треба знайти найкоротший шлях від s до t).
4.1. Якщо р=t, то l(p)— довжина найкоротшого (s,t) шляху.
Зупинка.
4.2. Якщо р t, то перейти до кроку 2.
Крок 5. (Якщо треба знайти найкоротші шляхи від s до всіх
вершин графа G).
Алгоритм виконується так довго, щоб всі вершини одержали
постійні позначки і множина непофарбованих вершин
вичерпалася: Wp = 0.
Зупинка.

62.

Приклад. Знаходження найкоротшого шляху між
вершиною a і рештою вершин у зваженому графі.
b(7)
b( )
7
7
2
3
4
a(0)
c(7)
c( )
d(4)
d( )
3
(8)
gg ( )
2
e(3)
e( )
3
2
(6)
ff ( )

63. Алгоритм Форда - Беллмана побудови найкоротших шляхів із вершини

Алгоритм Дейкстри не знаходить найкоротшого шляху,
якщо є дуги з від'ємними вагами.
Ще до появи у 1959р. алгоритму Дейкстри було
запропоновано процедури знаходження найкоротших
шляхів за дугами з будь-якими знаками ваг: 1956р.—
Форд, 1957р.— Мур, 1958р. — Беллман. В головному ці
процедури схожі; відповідна обчислювальна процедура
називається зараз алгоритмом Форда-Беллмана побудови
найкоротших шляхів у випадку довільних ваг.
Алгоритм Форда-Беллмана можна застосувати до графа з
невід'ємними вагами дуг, однак у цьому випадку він менш
ефективний за швидкістю порівняно з алгоритмом
Дейкстри.

64.

Зміни алгоритму Дейкстри полягають у такому:
1. На кроці 2 «Оновлення позначок» перерахунок величин l(w)
робиться для всіх вершин — як з тимчасовими, так і з
постійними позначками (непофарбованими і пофарбованими).
При цьому довжини l(w) можуть зменшуватися як для
непофарбованих вершин, так і для пофарбованих.
Поняття «постійна позначка» вершини хр стає некоректним, і
зручніше говорити, що вершина хр пофарбована (на кроці 3),
але, можливо, тимчасово.
2. Якщо для деякої пофарбованої вершини хр після застосування
кроку 2 відбувається зменшення «відстані» l(хр), тоді з вершини
хр і пофарбованої дуги, що веде до неї, знімається фарбування.
3. Алгоритм закінчується тоді, коли всі вершини графа
пофарбовані і ще одне виконання кроку 2 не змінює жодне з
чисел l(x), x X, або число фарбувань будь-якої одної вершини
не досягне величини n - кількості всіх вершин. У останньому
випадку граф має контур від'ємної довжини і алгоритм ФордаБеллмана не коректний.

65.

Приклад. Знаходження найкоротшого шляху між
вершиною a і рештою вершин у зваженому графі.
b(3)
b( )
b(5)
b(4)
-2
c(5)
c( )
6
5
2
a(0)
3
-3
2
ggg(11)
(5)
( )
3
d(2)
d( )
4
(2)
ff ( )
(6)

66. Алгоритм Флойда і Данцига побудови найкоротших шляхів між всіма вершинами

Задача пошуку найкоротших шляхів між всіма
парами вершин графа може бути розв'язана
шляхом послідовного привласнення позначки
«початкова вершина s» кожній вершині графа G і
наступного застосування алгоритму Дейкстри.
Однак існують більш ефективні методи, ніж
багаторазове
(саме
n-кратне)
повторення
алгоритму Дейкстри — саме алгоритми Флойда
(1962р.) і Данцига (1967p.). Обидва алгоритми
застосовні як у випадку невід'ємних ваг дуг, так і у
випадку ваг довільних знаків. Однак у будь-якому
випадку необхідно, щоб граф G не мав контурів
від'ємної довжини.

67.

Попередньо пронумеруємо вершини графа G натуральними
числами 1, 2, ..., n і введемо позначення lmi,j для довжини
найкоротшого з усіх таких шляхів від вершини і до вершини j
(інакше — всіх таких (і,j) — шляхів), які як проміжні вершини
можуть містити тільки перші m вершин, тобто вершини з
множини Vm = {1, 2, ..., m). При цьому lmi,j = , якщо не існує
жодного (і,j)-шляху з проміжними вершинами тільки і Vm.
Для m=0 вважається, що Vm={0} — порожня множина і l0i,j —
довжина найкоротшої (і,j)-дуги (тобто (і,j)-шляхи без
проміжних вершин) при і j. Для і=j припускається l0i,j =0.
Алгоритм Флойда ставить своєю ціллю послідовно для
m=0,1,2,...,n обчислювати n2 чисел (довжин) lmi,j і закінчувати
обчислення
одержанням
lni,j
(і,j=1,2,...,n)
шуканих
найкоротших довжин шляхів між всіма парами (і,j) вершин у
графі G. Якщо для фіксованого m об'єднати всі довжини lmi,j у
матрицю, то задача полягає у послідовному обчисленні
матриць L0, L1, ..., Lm-1, Lm, ..., Ln.

68.

При цьому виявляється можливим обчислити матрицю Lm,
використовуючи тільки лише безпосередньо попередню
матрицю Lm-1. Дійсно, нехай відомі всі найкоротші довжини
lm-1i,j (і,j=1,...,n). Розіб'ємо множину всіх (і,j) — шляхів через
вершини Vm на два класи: що обов'язково проходять через
вершину m і що не проходять через m (тобто які проходять
тільки через вершини з Vm-1). Найкоротший шлях у другому
класі має довжину lm-1i,j. Найкоротший шлях через вершину m у
першому класі складається з двох частин: (і,j) — шляхи
довжини lm-1i,m і (m,j) — шляхи довжини lm-1m,j. Тому
найкоротший (і,j) — шлях через вершину m (з проміжними
вершинами тільки з Vm) має довжину lm-1i,m + lm-1m,j . Отже,
lim, j = min{ lim, j−1 , lim,m−1 + lmm,−j1}
Зрозуміло, що граф G не має контурів від'ємної довжини,
інакше рекурентне правило не буде справедливим.

69.

Крок 1. Перенумерувати вершини графа G числами 1,2,...,n.
Сформувати матрицю довжин L0={l0i,j}, поклавши число l0i,j
при і j, що дорівнює мінімальній довжині дуги з вершини і до
вершини j або l0i,j= , якщо таких дуг немає. Якщо і=j, то l0i,j=0.
Крок 2. Послідовно для m = 1, 2, ..., n, виходячи з елементів lm-1i,j
матриці Lm-1, обчислити елементи матриці Lm={lmi,j} за
рекурентним правилом, фіксувати «найкоротший» (і,j)-шлях,
що має довжину lmi,j.
При m = n алгоритм закінчує роботу. Числа lni,j є довжини
шуканих найкоротших (і,j)-шляхів у графі G; і,j=1,2,...,n.
Зауваження. При одержані матриці Lm (пo Lm-1) значення
елементів головної діагоналі lmi,i, елементів m-того рядку lmm,j, і
m-го стовпця lmi,m можна не обчислювати, а покласти відразу
l
m
m, j
=l
m−1
m, j
m
i ,m
l
m−1
i ,m
=l
Зауваження. Якщо на де-якому кроці виявиться, що lmi,i<0, то в
графі існує цикл з від’ємною довжиною.

70.

Приклад. Знаходження найкоротших шляхів між
всіма вершинами у зваженому графі.
1
-2
2
3
-3
4
2
5
4
-3
5
3
0
L0=
4
-2
0
5
3
2
0
5
-3
-3
0
0 -2 3
0 2
L1=
0
-3
-3
4
0
2
5

71.

0
L0=
4
-2
0
5
3
2
0
5
-3
-3
0
0
L3=
4
-2
0
2
0
2
0
4
-3
-1
-3
0
0
L1=
4
-2
0
2
3
2
0
5
-3
-3
0
0
3
L4= 1
4
-2
0
-1
2
0
2
0
4
-3
-1
-3
0
1
0
L2=
4
-2
0
2
0
2
0
4
-3
-3
0
-2
2
3
-3
4
2
5
4
-3
5
3