Граф G = (V, E) — математичний об'єкт, що складається з множини вершин V (nodes) і множини ребер E (edges). Ребра з'єднують пари вершин і можуть бути орієнтованими (dігрaф) або ні.
Приклад: граф K₄ (повний граф з 4 вершинами)
1
/|\
/ | \
2--+--3
\ | /
\|/
4
V = {1,2,3,4}, E = {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}
|V| = 4, |E| = 6 = C(4,2)
Класифікація графів
Тип
Означення
Приклад/застосування
Незважений
Ребра без числових ваг
Соціальні мережі (є/немає зв'язку)
Зважений
Кожне ребро має вагу w(e)
Мережі доріг, витрати маршрутів
Орієнтований (ориграф)
Ребра мають напрямок (u→v)
Веб-сторінки, залежності задач
Дворядний
V = A ∪ B, всі ребра між A і B
Розклади, задача присвоєння
Дерево
Зв'язний граф без циклів
Ієрархічні структури, BST
Планарний
Можна намалювати без перетину ребер
Друковані плати, карти
Теорема Ейлера і сім мостів Кенігсберга
У 1736 р. Ейлер вирішив задачу про сім мостів Кенігсберга: чи можна пройти всіма мостами рівно по одному разу? Відповідь — ні, і це стало першою теоремою теорії графів.
Ейлерів шлях (Eulerian path):
Проходить кожне ребро рівно по одному разу.
Теорема Ейлера: Ейлерів шлях існує ⟺
рівно 0 або 2 вершини мають непарний степінь.
Ейлерів цикл існує ⟺ всі вершини мають парний степінь.
Кенігсберг: 4 землі з'єднані 7 мостами.
Ступені вершин: 3, 5, 3, 3 — всі непарні
(4 непарних вершини > 2) → Ейлерового шляху немає!
Обходи графа: BFS і DFS
Два фундаментальні алгоритми обходу: пошук у ширину (BFS) і пошук у глибину (DFS). Обидва мають складність O(|V| + |E|).
BFS (Breadth-First Search):
Використовує чергу (queue)
Знаходить найкоротші шляхи (незважений граф)
Алгоритм:
1. queue = [s]; visited = {s}
2. while queue не порожня:
u = queue.popleft()
для кожного сусіда v u:
if v ∉ visited: visited.add(v); queue.append(v)
DFS (Depth-First Search):
Використовує стек (або рекурсію)
Знаходить цикли, топологічне сортування
Алгоритм Дейкстри: найкоротший шлях
Алгоритм Дейкстри (1959) знаходить найкоротший шлях від початкової вершини до всіх інших у зваженому графі з невід'ємними вагами. Складність: O((|V|+|E|) log|V|) з купою.
Вхід: зважений граф G=(V,E,w), джерело s
Вихід: масив dist[], де dist[v] = мінімальна відстань s→v
Алгоритм:
1. dist[s]=0; dist[v]=∞ для всіх v≠s
2. priority_queue Q = {(0, s)}
3. while Q не порожня:
(d, u) = Q.pop_min()
для кожного ребра (u,v) з вагою w:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
Q.push((dist[v], v))
Коректність: жадібний підхід + невід'ємні ваги
Google Maps, OpenStreetMap, навігатори використовують варіант алгоритму Дейкстри з A*-евристикою для маршрутизації.
Остовне дерево: алгоритми Крускала і Прима
Мінімальне остовне дерево (MST) — підграф-дерево, що з'єднує всі вершини з мінімальною сумарною вагою ребер.
MST: дерево T ⊆ E: з'єднує всі |V| вершин,
мінімізує Σ_{e∈T} w(e)
Алгоритм Крускала (жадібний):
1. Відсортуй всі ребра за вагою
2. Додавай ребро, якщо воно не створює цикл
(DSU — структура «система непересічних множин»)
Складність: O(|E| log|E|)
Алгоритм Прима:
Нарощуємо дерево від початкової вершини,
додаючи найдешевше ребро до незвіданого вузла.
Складність: O(|E| log|V|) з двійковою купою
Мережеві потоки: теорема Форда–Фалкерсона
Задача максимального потоку: знайти максимальну кількість «рідини», яку можна пустити від джерела s до стоку t, дотримуючись пропускних здатностей ребер.
Мережа: ориграф G=(V,E) з пропускн. здатн. c(u,v)
Потік: f(u,v) ≤ c(u,v) для кожного ребра
Збереження: Σf(вхід)=Σf(вихід) для v≠s,t
Теорема Форда-Фалкерсона (макспотік = мінрозріз):
max_flow(s,t) = min_cut(s,t)
Де мінімальний розріз — найменша сума пропускних
здатностей ребер, що відокремлює s від t
Планарні графи і теорема про 4 фарби
Планарний граф — той, який можна намалювати на площині без перетину ребер. Формула Ейлера зв'язує вершини, ребра і грані.
Формула Ейлера для планарних графів:
V − E + F = 2
де F — кількість граней (включаючи зовнішню)
Наслідок: E ≤ 3V − 6 (планарний граф)
Тобто K₅ і K₃,₃ — не планарні (теорема Куратовського)
Теорема про 4 фарби (Аппель і Хакен, 1976):
Будь-яку карту можна розфарбувати 4 фарбами так,
що суміжні регіони мають різні кольори.
(Перша теорема, доведена за допомогою комп'ютера!)
Застосування теорії графів
Галузь
Задача
Алгоритм
Навігація
Найкоротший маршрут
Дейкстра, A*
Соціальні мережі
Пошук спільнот
Алгоритм Лувена
Компілятори
Порядок компіляції
Топологічне сортування
Мережі
Максимальна пропускна здатність
Форд–Фалкерсон
Хімія
Ізоморфізм молекул
Ізоморфізм графів
ML
Нейронні мережі, GNN
Згортки на графах
Про цю статтю
Ця стаття є частиною бази знань calculator.party — освітнього ресурсу, що поєднує теорію з практичними інструментами. Матеріал орієнтований на студентів, учнів і фахівців, що прагнуть глибокого розуміння теми. Тут зібрані ключові концепції, формули та реальні приклади застосування.
Інформатика та алгоритміка лежать в основі сучасного світу: від пошукових алгоритмів до нейронних мереж та квантових обчислень.
Навіщо читати цю статтю
Після прочитання ви зможете впевнено пояснити тему, вирішувати практичні задачі та застосовувати знання у навчанні й роботі. Стаття охоплює теоретичне підґрунтя і числові приклади, що полегшують запам'ятовування матеріалу.
Часті запитання (FAQ)
Що таке Теорія графів: від мостів Кенігсберга до алгоритмів Google і чому це важливо знати?
Теорія графів: від мостів Кенігсберга до алгоритмів Google — ключова тема в комп'ютерних наук. Розуміння її основ дає змогу вирішувати практичні задачі, успішно складати іспити та застосовувати знання в реальних ситуаціях. Стаття розкриває концепцію доступними словами з конкретними прикладами.
Які ключові формули та методи використовуються в теорія графів: від мостів кенігсберга до алгоритмів google?
Основні формули та методи для теорія графів: від мостів кенігсберга до алгоритмів google охоплюють як аналітичні підходи, так і числові алгоритми. У статті наведені всі ключові вирази з поясненням кожного позначення та вказівкою одиниць вимірювання.
Де в реальному житті застосовується теорія графів: від мостів кенігсберга до алгоритмів google?
Сфери застосування теорія графів: від мостів кенігсберга до алгоритмів google надзвичайно широкі: програмуванні (бекенд, алгоритми), штучному інтелекті, кібербезпеці та обробці великих даних. Знання цієї теми відкриває кар'єрні можливості в інженерії, науці, фінансах та IT-галузі.
Як розрахувати теорія графів: від мостів кенігсберга до алгоритмів google онлайн?
На calculator.party є безкоштовні онлайн-калькулятори з тематики 'Теорія графів: від мостів Кенігсберга до алгоритмів Google'. Достатньо ввести вхідні дані — і ви миттєво отримаєте точний результат з покроковим поясненням. Це ідеально для перевірки ручних розрахунків.
Яка різниця між теорія графів: від мостів кенігсберга до алгоритмів google та суміжними темами?
Стаття чітко описує межі тематики 'Теорія графів: від мостів Кенігсберга до алгоритмів Google', порівнюючи її з близькими поняттями. Чітке розуміння відмінностей допомагає уникнути типових помилок та плутанини при розв'язанні задач.