Графи

1.1 Визначення графа та його компонентів

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

Основні компоненти графа:

Вершини:

• Елементи графа, які представляють об'єкти.
• Позначаються як V (множина вершин).
• Наприклад, V = {A, B, C, D}.

Ребра:

• З'єднання між вершинами, що представляють відносини або зв'язки.
• Позначаються як E (множина ребер).
• Наприклад, E = {(A, B), (B, C), (C, D), (A, D)}.

Основні характеристики графа:

Ступінь вершини:

• Кількість ребер, інцидентних даній вершині.
• У неорієнтованому графі ступінь вершини — це кількість ребер, що з'єднують цю вершину з іншими.
• У орієнтованому графі розрізняють вхідний та вихідний ступені вершини.

Шлях у графі:

• Послідовність ребер, що з'єднують послідовність вершин.
• Наприклад, шлях з A в D: A → B → C → D.

Цикл у графі:

• Шлях, який починається і закінчується в одній і тій же вершині.
• Наприклад, цикл: A → B → C → A.

1.2 Види графів

Графи бувають дуже різні, але з них можна виділити цікаві підтипи:

1. Неорієнтований граф:

Ребра цього графа не мають напрямку, тобто з'єднання між двома вершинами може бути пройдене в обидва боки.

Приклад:

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

2. Орієнтований граф:

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

Приклад:

Граф посилань на веб-сторінках, де вузли — це сторінки, а ребра — посилання між ними.

3. Зважений граф:

Ребра мають ваги (числа), що можуть представляти відстані, вартості або інші міри.

Приклад:

Граф доріг, де вузли — це міста, а ребра — дороги з їх довжиною або вартістю проїзду.

4. Змішаний граф:

Містить як орієнтовані, так і неорієнтовані ребра.

Приклад:

Системи транспортування, де одні дороги двосторонні, а інші — односторонні.

5. Планарний граф:

Граф, який можна намалювати на площині так, щоб його ребра не перетиналися.

Приклад:

Граф доріг у місті (без тунелів).

6. Зв'язний граф:

Граф, у якому існує шлях між будь-якою парою вершин.

Приклад:

Граф, що представляє мережу міст, у якій кожна пара міст з'єднана дорогою.

7. Ациклічний граф:

Граф, що не містить циклів.

Приклад:

Дерево, що представляє структуру файлової системи.

1.3 Приклади застосування графів

1. Соціальні мережі:

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

2. Інтернет та маршрутизація:

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

3. Геноміка:

• Вузли представляють гени або білки, а ребра — взаємодії між ними.
• Використовується для аналізу геномних даних, пошуку патернів тощо.

4. Логістика та транспорт:

• Вузли представляють міста або транспортні вузли, а ребра — дороги або шляхи.
• Використовується для оптимізації маршрутів доставки, мінімізації витрат тощо.

5. Комп'ютерні мережі:

• Вузли представляють пристрої або сервери, а ребра — з'єднання між ними.
• Використовується для проектування та управління мережами.

6. Аналіз даних та машинне навчання:

• Графи використовуються для представлення та аналізу даних, пошуку кластерів, створення рекомендаційних систем і так далі.