🕸️ Теорія графів
Шпаргалка: Теорія графів
Вершини, ребра, дерева, BFS/DFS, найкоротші шляхи та мінімальні остовні дерева — повна довідка
Основні терміни
Вершина (vertex)
Вузол графа, елемент множини V
Ребро (edge)
Зв'язок між двома вершинами, елемент E
Степінь вершини
deg(v) — кількість ребер, що виходять з v
Неорієнтований граф
Ребро {u,v} = {v,u} (без напрямку)
Орієнтований граф
Ребро (u,v) ≠ (v,u) (з напрямком)
Зважений граф
Кожному ребру відповідає вага w(e)
Шлях (path)
Послідовність вершин без повторів, з'єднаних ребрами
Цикл (cycle)
Шлях, що повертається у початкову вершину
✦ Зв'язний граф (connected graph) — граф, у якому між будь-якою парою вершин існує шлях.
Лема про рукостискання (Handshaking Lemma)
Σ deg(v) = 2·|E|
Сума степенів усіх вершин неорієнтованого графа завжди дорівнює подвоєній кількості ребер — кожне ребро додає 1 до степеня кожної з двох вершин, які воно з'єднує.
✦ Наслідок: кількість вершин з непарним степенем завжди парна.
Дерева
Дерево — зв'язний граф без циклів
n вершин → рівно n − 1 ребро
| Властивість | Значення |
|---|
| Кількість ребер | Завжди n − 1 (n — кількість вершин) |
| Циклів | Немає жодного |
| Зв'язність | Будь-які дві вершини з'єднані рівно одним шляхом |
| Видалення ребра | Розбиває дерево на 2 компоненти |
| Додавання ребра | Утворює рівно один цикл |
✦ Повний граф Kₙ (кожна пара вершин з'єднана) має n(n−1)/2 ребер.
Алгоритми обходу: BFS vs DFS
| Критерій | BFS (пошук у ширину) | DFS (пошук у глибину) |
|---|
| Структура даних | Черга (queue, FIFO) | Стек (stack, LIFO) або рекурсія |
| Порядок обходу | Рівень за рівнем | Заглиблення одним шляхом до кінця |
| Найкоротший шлях | Гарантує найкоротший шлях у незваженому графі | Не гарантує найкоротшого шляху |
| Пам'ять | Може зберігати цілий рівень вершин | Глибина рекурсії ≤ висота графа |
| Типове застосування | Найкоротший шлях, перевірка зв'язності по рівнях | Топологічне сортування, пошук циклів, компоненти зв'язності |
✦ BFS з початкової вершини знаходить найкоротший шлях (за кількістю ребер) у незваженому графі; DFS цього не гарантує.
Найкоротший шлях: Дейкстра та Беллман-Форд
Алгоритм Дейкстри
Найкоротші шляхи від 1 вершини; лише невід'ємні ваги ребер
Алгоритм Беллмана-Форда
Допускає від'ємні ваги; виявляє від'ємні цикли
| Алгоритм | Від'ємні ваги | Виявлення від'ємного циклу |
|---|
| Дейкстра | Не допускаються — результат буде некоректним | Не виявляє |
| Беллман-Форд | Допускаються | Так, якщо після n−1 ітерацій вагу шляху ще можна зменшити |
✦ Якщо всі ваги ребер невід'ємні — обирайте Дейкстру (швидша); якщо можливі від'ємні ваги — Беллман-Форда.
Мінімальне остовне дерево (MST)
Алгоритм Крускала
Сортує всі ребра за вагою, жадібно додає найлегше ребро, що не утворює цикл
Алгоритм Прима
Починає з однієї вершини, на кожному кроці додає найлегше ребро, що з'єднує дерево з новою вершиною
✦ Остовне дерево (spanning tree) охоплює всі n вершин графа рівно n−1 ребром без циклів; MST — те з них, що має мінімальну сумарну вагу.
Планарність та розфарбування графів
Планарний граф
Можна намалювати на площині без перетинів ребер
Хроматичне число
χ(G) — мінімум кольорів, щоб суміжні вершини мали різні кольори
✦ Теорема чотирьох фарб: будь-яку планарну карту можна розфарбувати не більш ніж 4 кольорами так, щоб суміжні області відрізнялися.
Як користуватися шпаргалкою
Ця шпаргалка зосереджує найважливіші терміни, властивості та алгоритми теорії графів у компактному форматі для швидкого пошуку та підготовки до іспитів. Матеріал систематизований від базових означень (вершина, ребро, степінь) до алгоритмів обходу та пошуку найкоротших шляхів.
Ефективне використання
Використовуйте шпаргалку поряд з розв'язуванням задач — не для списування, а як довідник. Спершу спробуйте намалювати граф і застосувати алгоритм самостійно, потім звіртеся з таблицями BFS/DFS чи Дейкстри/Беллмана-Форда, щоб перевірити коректність обраного підходу.
Часті запитання (FAQ)
Що таке теорія графів?
Теорія графів — розділ дискретної математики, що вивчає графи — структури з вершин (вузлів) та ребер (зв'язків між ними). Вона застосовується для моделювання мереж, маршрутів, залежностей та відношень між об'єктами.
У чому різниця між BFS та DFS?
BFS (пошук у ширину) обходить граф рівень за рівнем і використовує чергу (FIFO) — спочатку відвідує всіх сусідів вершини, потім сусідів сусідів. DFS (пошук у глибину) заглиблюється якнайдалі одним шляхом і використовує стек або рекурсію (LIFO), повертаючись назад лише коли шлях вичерпано.
Коли використовувати алгоритм Дейкстри і які в нього обмеження?
Алгоритм Дейкстри знаходить найкоротші шляхи від однієї вершини до всіх інших у зваженому графі, але працює коректно тільки якщо всі ваги ребер невід'ємні. Якщо є від'ємні ваги, потрібен алгоритм Беллмана-Форда.
Що таке остовне дерево графа?
Остовне дерево (spanning tree) — це підграф зв'язного графа, що містить усі його вершини, є деревом (зв'язний, без циклів) і має рівно n−1 ребро, де n — кількість вершин. Мінімальне остовне дерево (MST) має найменшу можливу сумарну вагу ребер; його знаходять алгоритмами Крускала або Прима.
Де на практиці застосовується теорія графів?
Теорія графів лежить в основі соціальних мереж (граф зв'язків між користувачами), GPS-навігації та маршрутизації (пошук найкоротшого шляху), комп'ютерних мереж (топологія та маршрутизація пакетів), рекомендаційних систем та аналізу залежностей у програмному коді.