Основи теорії графів (алгоритми ) Марчук Людмила Василівна учитель інформатики Черкаської загальноосвітньої школи І-ІІІ ступенів 30

Нехай маємо звязаний неорієнтований граф в якому вершини зєднуються ребрами, для кожного з яких задається вага

4

G 5

6

7

8

9

10

«Пошук в глибину і в ширину. Ейлерів та Гамільтонів граф»

Здійснюється обхід в максимально можливу глибину до переходу на наступну вершину

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

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

Гамільтонів граф Граф, що містить гамільтонів шлях, тобто такий, який проходить кожну вершину графа 1 і тільки 1 раз.

Алгоритм Флойда - Уоршелла

Алгоритм Флойда - Уоршелла - алгоритм для знаходження найкоротших відстаней між усіма вершинами зваженого графа без циклів з негативними вагами з використанням методу динамічного програмування

Розроблений в 1962 році Робертом Флойдом Стівеном Уоршеллом. і

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

1. Найкоротший шлях між не проходить через вершину, тоді Існує більш короткий шлях між 2. проходить через, тоді він спочатку йде від до, а потім від до У цьому випадку, очевидно, Таким чином, для знаходження значення функції досить вибрати мінімум з двох позначених значень

Тоді рекурентна формула для має вигляд: - довжина ребра Алгоритм Флойда- Уоршелла послідовно обчислює всі значення для від 1 до. Отримані значення є довжинами найкоротших шляхів між вершинами

Приклад графа і таблиця відстаней для нього

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

Зберігатимемо поточну мінімальну відстань до всіх вершин V і на кожному кроці алгоритму намагатимемося зменшити цю відстань. Спочатку встановимо відстані до всіх вершин рівними нескінченості, а до вершини а нулю

В математичних термінах Нехай u вершина, від якої шукаються відстані, V множина вершин графа, di відстань від вершини u до вершини i,, w(i, j) вага «ребра» (i, j). Алгоритм: 1. Множина вершин U, до яких відстань відома, = {u}. 2. Якщо U=V, алгоритм завершено. 3. Потенційні відстані Di до вершин з U\V встановлюються нескінченними. 4. Для всіх ребер (i, j), де i U та j V\U, якщо Dj>di+w(i, j), то Dj присвоюється di+w(i, j). 5. Шукається i V\U, при якому Di мінімальне. 6. Якщо Di дорівнює нескінченності, алгоритм завершено. В іншому випадку di := Di, U := U {i} і виконується перехід до кроку

Література Басакер Р., Сааті Т. Кінцеві графи та мережі. М.: Наука, c. Бєлов В. В., Воробйов Є. М., Шаталов В. Є. Теорія графів - М.: Вища. школа, С Берж К. Теорія графів та її застосування. М.: ІЛ, c. Емелічев В. А., Мельников О. І., Сарванов В. І., Тишкевич Р. І. Лекції з теорії графів. М.: Наука, с. (Ізд.2, испр. М.: УРСС, с.) Зиков А. А. Основи теорії графів - М.: "Вузівська книга", С ISBN (М.: Наука, c.)ISBN