Графи й дерева: структура, на якій тримаються пошук і нейронні мережі

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

14 хвилин Matěj Žalmánek 2026-10-15

Серія Основи ШІ Частина 8 з 52

1. Мапа штучного інтелекту: що є що і як усе це пов’язано
2. Коротка історія штучного інтелекту: від Тюрінга до мовних моделей
3. Дані, модель, тренування, інференс: основні поняття на одному прикладі
4. Як читати математичний запис: символи, індекси, суми та квантори
5. Множини й відношення: конструктор, з якого складаються означення в ШІ
6. Функції й відображення: чому кожна модель у ШІ — це функція
7. Логіка й доведення: правила, за якими міркують у ШІ
8. Графи й дерева: структура, на якій тримаються пошук і нейронні мережі
9. Лінійна алгебра для машинного навчання: вектори, матриці й чому ШІ передусім множить
10. Похідні, градієнт і правило ланцюжка: як модель дізнається, у якому напрямку вчитися
11. Градієнтний спуск: як навчається модель
12. Що таке ймовірність: від кидка кубика до аксіом Колмогорова
13. Умовна ймовірність і теорема Баєса: як змінити оцінку, коли дізнаєтеся щось нове
14. Випадкова величина і функція розподілу: одна функція, яка каже про розподіл усе
15. Функція щільності та функція маси ймовірності: чому неперервна величина має в точці ймовірність нуль
16. Математичне сподівання, дисперсія і коваріація: де лежить розподіл, наскільки він широкий і що з чим пов’язано
17. Огляд розподілів ймовірностей: Бернуллі, біноміальний, Пуассона, рівномірний, нормальний і експоненційний
18. Закон великих чисел і центральна гранична теорема: чому середні поводяться так передбачувано
19. Статистика й оцінювання параметрів: максимальна правдоподібність, MAP і довірчі інтервали
20. Теорія інформації: ентропія, перехресна ентропія і KL-дивергенція — звідки беруться функції втрат
21. Пошук у просторі станів: BFS, DFS, UCS і A* з анімаціями
22. Ігри та суперник: мінімакс, альфа-бета відсікання і Monte Carlo tree search
23. Задоволення обмежень: бектрекінг, поширення обмежень і AC-3 на судоку та мапі чеських країв
24. Логіка й системи, засновані на знаннях: пряме і зворотне виведення, резолюція та експертні системи
25. Планування: STRIPS, світ кубиків, евристики з релаксації та планування в AI-агентах
26. Локальний пошук та імітація відпалу: комівояжер через обласні центри Чехії
27. Генетичні алгоритми: популяція, схрещування, мутація і добір на рюкзаку для походу
28. Еволюційні стратегії і генетичне програмування: від правила однієї п’ятої до закону Кеплера
29. Оптимізація мурашиною колонією: як феромоновий слід знаходить короткий шлях
30. Оптимізація роєм частинок: інерція, власний досвід і досвід рою
31. Нейроеволюція: еволюція ваг і форми нейронних мереж та алгоритм NEAT
32. Нечіткі множини й функції належності: як записати «трохи тепло»
33. Нечітка логіка та ймовірність: чому «трохи тепло» не означає «імовірно тепло»
34. Нечітка логіка: t-норми, імплікації та правила ЯКЩО–ТО
35. Нечітке керування: Мамдані та Суґено від вентилятора до маятника на візку
36. Нечітка кластеризація: алгоритм fuzzy c-means і точки між кластерами
37. Нейро-нечіткі системи (ANFIS): нечіткі правила, які навчаються з даних
38. Марковські ланцюги: матриця переходів, стаціонарний розподіл і PageRank
39. Приховані марковські моделі: алгоритм Вітербі й нечесне казино
40. Байєсівські мережі: чому трава мокра і що з цього випливає для дощувача
41. Фільтр Калмана: як за неточними вимірюваннями оцінити, де авто і як швидко воно їде
42. Види машинного навчання: з учителем, без учителя, з частковим залученням учителя та інші
43. Промпти, контекст і RAG: як дати моделі правильну інформацію
44. Варіаційні автокодувальники (VAE): нові зображення з неперервного латентного простору
45. Генеративні змагальні мережі (GAN): фальшувальник проти детектива
46. Дифузійні моделі: як із чистого шуму постає зображення
47. Марковські процеси ухвалення рішень: стани, дії, винагороди й рівняння Беллмана
48. Q-навчання і DQN: як навчитися цінності дій — від таблиці до нейронної мережі
49. Policy gradient і PPO: навчання безпосередньо політики
50. Як працює ШІ-агент: мовна модель у циклі з інструментами
51. Програмування з AI-агентами: завдання, тести й перевірка
52. Оцінювання і безпека систем ШІ: як вимірювати і як стежити

Повна програма серії Готово: 52 з 83 тем

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

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

1. Що таке граф

Означення — граф

Граф — це пара G = (V, E), де V — скінченна множина вершин, а E — множина ребер.

У неорієнтованому графі ребро — це двоелементна множина {u, v}; в орієнтованому — упорядкована пара (u, v), стрілка з u до v. Отже, орієнтований граф — це відношення на V.

Зважений граф має ще функцію w : E → ℝ, яка кожному ребру ставить у відповідність вагу (довжину, ціну, час).

2. Степінь вершини

Означення — степінь і лема про рукостискання

Степінь deg(v) вершини v — це кількість ребер, що з неї виходять.

Теорема (лема про рукостискання). У кожному неорієнтованому графі ∑_{v ∈ V} deg(v) = 2 |E|.

Сума степенів дорівнює 2 + 4 + 4 + 4 + 4 + 4 + 2 = 24, а ребер 12 — точно за теоремою. Степінь має практичний зміст: у соціальній мережі це кількість друзів, у вебі — кількість посилань, а вершини з великим степенем зазвичай найважливіші.

3. Як зберегти граф у комп’ютері

Комп’ютер не бачить малюнка, йому потрібні числа. Звичні два подання:

• Матриця суміжності — таблиця |V| × |V|, у клітинці (u, v) стоїть вага ребра або 0. Питання «чи є тут ребро?» розв’язується швидко, але пам’ять зростає як |V|².
• Список суміжності — для кожної вершини список її сусідів. Пам’ять зростає лише як |V| + |E|, а для розріджених графів (соціальна мережа, карта) це величезна різниця.

Матриця симетрична відносно діагоналі — це ознака неорієнтованого графа. У ШІ матрицю суміжності використовують графові нейронні мережі, які навчаються безпосередньо на графах (молекули, соціальні мережі, дорожня мережа).

4. Шляхи, цикли та зв’язність

Означення — шлях, цикл, зв’язність

Шлях з u до v — це послідовність попарно різних вершин u = v₀, v₁, …, v_k = v, у якій кожні дві сусідні з’єднані ребром. Його довжина — це k (кількість ребер), у зваженому графі — сума ваг.

Цикл — це шлях, що повертається до початкової вершини (щонайменше три ребра).

Граф зв’язний, якщо між будь-якими двома вершинами є шлях. Максимальні зв’язні частини графа — це його компоненти зв’язності; «лежати в одній компоненті» є еквівалентністю, тож компоненти утворюють розбиття V.

5. Найкоротші шляхи

Задача «як найшвидше дістатися з A до G» — це пошук найкоротшого шляху, тобто саме те, що робили алгоритми з частини про пошук у просторі станів. Але все залежить від того, що ми вимірюємо.

Якщо нас цікавить кількість ребер, досить пошуку в ширину: спершу сусіди A, потім їхні сусіди… Число над вершиною — це відстань від A в ребрах:

До G ведуть три ребра (наприклад, A–B–E–G). Але коли ми рахуємо довжину доріг, потрібен алгоритм Дейкстри — він завжди продовжує з найближчої ще не закритої вершини. Число над вершиною тепер — найкоротша відстань у кілометрах, а найкоротший шлях до G виділено:

Найкоротший шлях A–B–D–E–G має чотири ребра, тобто більше, ніж триреберний шлях із BFS, але довжину лише 12. Шлях A–B–E–G мав би 4 + 7 + 3 = 14. Менше кроків не означає коротший шлях — саме цю різницю між BFS і UCS ми бачили в лабіринті з болотом.

6. Дерева

Означення — дерево й кореневе дерево

Дерево — це зв’язний граф без циклів. Ліс — це граф без циклів (кожна його компонента — дерево).

Теорема. Для графа з n вершинами рівносильні твердження: (1) це дерево; (2) він зв’язний і має n − 1 ребер; (3) він не має циклів і має n − 1 ребер; (4) між будь-якими двома вершинами веде рівно один шлях.

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

У ШІ дерева всюди. Дерево рішень класифікує серією запитань від кореня до листка. Алгоритми пошуку будують дерево пошуку — дерево BFS і DFS із частини про пошук якраз і є таким. А шахова програма прораховує дерево гри, у якому вершини — позиції, а ребра — ходи.

7. Мінімальне остовне дерево

Означення — остовне дерево й алгоритм Крускала

Остовне дерево зв’язного графа G — це підграф, який містить усі вершини G і є деревом. Мінімальне остовне дерево має найменшу суму ваг ребер.

Алгоритм Крускала: упорядкувати ребра за зростанням ваги й по черзі додавати кожне, яке не утворює циклу. Це жадібний алгоритм, і все ж він завжди знаходить оптимум.

Остовне дерево має 6 ребер для 7 вершин — точно n − 1, як каже теорема про дерева, — і загальну довжину 18. Шість решти доріг алгоритм відкинув, бо вони утворили б цикл.

8. Ациклічні графи й обчислення нейронної мережі

Означення — DAG і топологічне впорядкування

Орієнтований ациклічний граф (DAG) — це орієнтований граф без орієнтованих циклів.

Топологічне впорядкування — це таке розташування вершин, за якого кожне ребро (u, v) веде зліва направо: u стоїть перед v. Теорема. Орієнтований граф має топологічне впорядкування тоді й лише тоді, коли він ациклічний.

Так обчислює кожна нейронна мережа. Ось обчислення одного нейрона ŷ = σ(w · x + b) і його похибки L(ŷ, y) у вигляді обчислювального графа: входи ліворуч, операції як вершини, стрілки показують, що від чого залежить. Числа — це топологічний порядок:

Мережа обчислює вперед у топологічному порядку — спершу добуток, потім суму, сигмоїду й похибку. А коли потім навчається, іде тим самим графом назад: зворотне поширення помилки (backpropagation) проходить вершини в оберненому топологічному порядку і в кожній застосовує ланцюгове правило. Бібліотеки на кшталт PyTorch будують цей граф самі під час кожного обчислення. До речі, і граф залежностей модулів у плані цієї серії — теж DAG.

9. Графи у штучному інтелекті

• Простір станів — це граф: стани є вершинами, дії — ребрами з ціною. Пошук — це пошук шляху в графі.
• Обчислювальні графи нейронних мереж — це DAG; навчання — прохід туди й назад.
• Графи знань зберігають факти як ребра «Прага — є столицею — Чехії», і пошукові системи складають із них відповіді.
• Баєсові мережі — це DAG імовірнісних залежностей; до них ми дійдемо в модулі про ймовірнісні моделі.
• Графові нейронні мережі навчаються безпосередньо на графах: передбачають властивості молекул, дорожній рух або рекомендації.

10. Підсумок

• Граф — це множина вершин і ребер; ребра можуть мати напрям і вагу. Сума степенів удвічі більша за кількість ребер.
• Граф зберігають матрицею суміжності або списком суміжності — для розріджених графів він набагато ощадливіший.
• BFS знаходить шлях із найменшою кількістю ребер, Дейкстра — найкоротший за вагами, і це не обов’язково те саме.
• Дерево — це зв’язний граф без циклів з n − 1 ребрами; мінімальне остовне дерево знаходить жадібний алгоритм Крускала.
• Нейронна мережа — це обчислювальний DAG: уперед обчислюють у топологічному порядку, градієнт — назад.

Маєте іншу думку? Напишіть на support@coden-app.com.