Визначення діаметра графа

Діаметром Неорієнтований граф називається максимальна довжина найкоротшого шляху між двома вершинами. Класичний спосіб визначення діаметра – виконати пошук завширшки від усіх вершин, тоді діаметр дорівнює максимальному зі знайдених відстаней. Складність такого підходу становить [math]O(mn)[/math] , і в гіршому випадку (наприклад, коли граф є циклом) цю оцінку, мабуть, не можна поліпшити.

Алгоритм iFUB [1] (англ. iterative Fringe Upper Bound) дозволяє зменшити кількість викликів алгоритму пошуку завширшки. Для багатьох реальних графів буде достатньо декількох викликів і загальна складність буде близька до лінійної [math]O(m)[/math] .

1.2 Математичне опис алгоритму

1.3 Обчислювальне ядро ​​алгоритму

1.4 Макроструктура алгоритму

1.5 Схема реалізації послідовного алгоритму

1.6 Послідовна складність алгоритму

Послідовна складність алгоритму iFUB дорівнює [math]O(Bm)[/math] , де [math]B[/math] – кількість викликів алгоритму пошуку завширшки, складність кожного виклику [math]O(m)[/math] . У найгіршому випадку (граф є циклом) [math]B = n[/math] і загальна складність дорівнює [math]O(mn)[/math] , проте для багатьох реальних графів [math]B = O(1)[/ math] та загальна складність складає [math]O(m)[/math] .

1.7 Інформаційний граф

1.8 Ресурс паралелізму алгоритму

1.9 Вхідні та вихідні дані алгоритму

Вхідні дані: неорієнтований граф [math](V, E)[/math] ([math]n[/math] вершин [math]v_i[/math] та [math]m[/math] ребер).

Обсяг вхідних даних: [math] O (m + n) [/ math].

Вихідні дані: Діаметр графа [math](V, E)[/math] .

Обсяг вихідних даних: [math]O(1)[/math] .

1.10 Властивості алгоритму

2 Програмна реалізація алгоритму

2.1 Особливості реалізації послідовного алгоритму

2.2 Можливі способи та особливості паралельної реалізації алгоритму

2.3 Результати прогонів

2.4 Висновки для класів архітектур

3 Література

1. ↑ Crescenzi, Pilu, Roberto Grossi, Michel Habib, Leonardo Lanzi, and Andrea Marino. “On Computing the Diameter of Real-World Undirected Graphs.” Theoretical Computer Science 514 (11 листопада 2013): 84–95. doi:10.1016/j.tcs.2012.09.018.

Граф неорієнтований: основні поняття та визначення

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

1. Основні визначення

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

"граф неорієнтований" складається з вершин, з'єднаних ребрами, що не мають напряму. Це відрізняє його від орієнтованого графа, в якому ребра спрямовані від однієї вершини до іншої.

Важливою характеристикою вершини неорієнтованого графа є її ступінь - Число ребер, інцидентних даній вершині. Для графа виконується формула:

Де | V | - Число вершин, | E | - Число ребер, Σdeg(v) - сума ступенів всіх вершин.

До переваг неорієнтованих графів відносяться:

• Простота визначення та зображення
• Інтуїтивна інтерпретація ребер як зв'язків без спрямування
• Можливість моделювання симетричних відносин
• Простіші алгоритми обходу в порівнянні з орієнтованими графами
• Зручне уявлення у вигляді матриці суміжності

2. Види неорієнтованих графів

Розрізняють такі основні види неорієнтованих графів:

• Прості графи - не містять кратних ребер та петель
• Мультиграф - допускають кратні ребра, але не петлі
• Псевдографи - допускають і кратні ребра, і петлі

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

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

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

3. Подання неорієнтованих графів

Для представлення неорієнтованих графів у пам'яті комп'ютера використовуються два основні способи:

Матриця суміжності неорієнтованого графа - це квадратна | V | x | V | матриця, у комірці (i,j) якої міститься 1, якщо вершини i і j з'єднані ребром, і 0 - якщо не з'єднані.

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

Порівняння двох уявлень щодо використання пам'яті та швидкості виконання основних операцій наведено нижче:

Як видно, у обох уявлень є свої переваги та недоліки.

4. Основні операції над неорієнтованими графами

Розглянемо базові операції, які виконуються над неорієнтованими графами:

• Додавання вершини
• Видалення вершини
• Додавання ребра
• Видалення ребра
• Пошук шляхів між заданими вершинами

При додаванні та видаленні елементів потрібно коректно оновлювати відповідні структури даних, чи то матриця суміжності, чи список суміжності.

Завдання пошуку шляхів між вершинами часто виникає під час роботи з орієнтованим та неорієнтованим графом. Для неорієнтованих графів вона вирішується простіше за відсутності напрямків ребер.

Розглянемо кілька прикладів типових завдань на неорієнтованих графах:

1. Знайти найкоротший шлях між двома вершинами
2. Визначити, чи є граф зв'язковим
3. Знайти максимальну кількість незалежних шляхів між вершинами
4. Виділити компоненти зв'язності незв'язного графа

Для вирішення подібних завдань існують ефективні алгоритми на графах: пошук у глибину та ширину, алгоритм Дейкстри, алгоритм Форда-Беллмана та ін.

5. Застосування неорієнтованих графів

Граф неорієнтований широко використовується в прикладних задачах завдяки простоті формального визначення та наочності графічного уявлення.

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

Ще одне важливе застосування – використання для моделювання соціальних зв'язків, наприклад, відносин знайомства чи дружби між людьми. Вершинами будуть люди, а наявність ребра означає зв'язок між ними.

6. Алгоритми на неорієнтованих графах

Розглянемо деякі базові алгоритми, які працюють із неорієнтованими графами:

• Алгоритм пошуку в глибину (DFS)
• Алгоритм пошуку завширшки (BFS)
• Алгоритм Прима для побудови мінімального остовного дерева
• Алгоритм Фарбала для побудови мінімального остовного дерева

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

7. Неорієнтовані графи та інформатика

Граф неорієнтований є фундаментальною структурою даних в інформатиці та має безліч застосувань при вирішенні алгоритмічних та обчислювальних завдань.

Зокрема, неорієнтовані графи використовують для моделювання різних комп'ютерних мереж - локальних, корпоративних, глобальних. Вершинами є пристрої, а ребрами – лінії зв'язку між ними.

8. Обробка великих графів

Працюючи з великими графами, що містять сотні тисяч і мільйони вершин, виникає проблема ефективного зберігання у пам'яті та виконання операцій.

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