Дискретная математика: графы, алгоритмы и где это применяется

Граф — абстрактная структура из вершин и рёбер. На первый взгляд — чистая математика. На деле — соцсети, GPS-навигация, компиляторы, маршрутизация в интернете, рекомендательные системы и логистика.

Базовые понятия

Ориентированный vs неориентированный

• Неориентированный: дружба в Facebook (взаимная)
• Ориентированный: подписка в Instagram (А подписан на Б, но не наоборот)

Взвешенный граф

Каждому ребру приписано число — вес (расстояние, стоимость, пропускная способность).

Виды графов

Теорема о сумме степеней

Сумма степеней всех вершин равна удвоенному числу рёбер:

$$\sum_{v \in V} \deg(v) = 2|E|$$

Следствие: в любом графе число вершин с нечётной степенью чётно (лемма о рукопожатиях).

Алгоритмы на графах

1. Поиск в ширину (BFS)

Обходит граф «по уровням» от начальной вершины. Очередь.

Применение: кратчайший путь в невзвешенном графе, поиск друзей в соцсети по уровням (друзья, друзья друзей, ...).

Сложность: $O(V + E)$

Идея: заходим в вершину, кладём всех непосещённых соседей в очередь. Обрабатываем по очереди.

2. Поиск в глубину (DFS)

Уходит «вглубь» до упора, затем возвращается. Стек (рекурсия).

Применение: топологическая сортировка, поиск циклов, проверка связности, поиск компонент.

Сложность: $O(V + E)$

3. Алгоритм Дейкстры

Кратчайший путь во взвешенном графе с неотрицательными весами.

Идея: поддерживаем множество «обработанных» вершин и минимальное расстояние до каждой. На каждом шаге выбираем необработанную вершину с минимальным расстоянием.

Сложность: $O(V^2)$ или $O(E \log V)$ с кучей.

Применение: Яндекс.Навигатор, построение маршрутов.

4. Алгоритм A*

Улучшение Дейкстры с эвристикой — оценкой оставшегося расстояния.

$$f(v) = g(v) + h(v)$$

• $g(v)$ — расстояние от старта до $v$ (известно)
• $h(v)$ — эвристическая оценка от $v$ до цели

Если $h(v)$ никогда не переоценивает реальное расстояние (допустимая эвристика), A* находит оптимальный путь. В игровых движках (Unity, Unreal) — основной алгоритм поиска пути.

5. Алгоритм Беллмана—Форда

Как Дейкстра, но работает и с отрицательными весами (но без отрицательных циклов). Медленнее: $O(VE)$.

Применение: арбитраж валют (поиск отрицательных циклов → прибыльная цепочка обмена).

6. Алгоритм Флойда—Уоршелла

Все кратчайшие пути между всеми парами вершин. Динамическое программирование. $O(V^3)$.

7. Топологическая сортировка

Упорядочивание вершин так, что каждое ребро идёт от более ранней вершины к более поздней. Работает только для ациклических ориентированных графов (DAG).

Применение: порядок компиляции модулей, построение расписания курсов с пререквизитами, разрешение зависимостей в сборочных системах (Make, Gradle).

Остовное дерево (MST)

Остовное дерево — подграф из всех $V$ вершин и $V-1$ рёбер без циклов, соединяющий все вершины.

Алгоритм Краскала

Сортируем рёбра по весу. Добавляем, если не создаёт цикл (проверка через систему непересекающихся множеств — DSU). $O(E \log E)$.

Алгоритм Прима

Растим дерево от одной вершины, на каждом шаге добавляя минимальное ребро к непосещённой вершине. $O(E \log V)$ с кучей.

Применение: прокладка сетей (электричество, интернет) с минимальной стоимостью, кластеризация.

Раскраска графов

Присвоение цветов вершинам так, чтобы смежные вершины имели разные цвета. Хроматическое число $\chi(G)$ — минимальное число цветов.

Применение:

• Распределение радиочастот (соседние вышки — разные частоты)
• Расписание экзаменов (студент не может сдавать два экзамена одновременно)
• Компиляция: распределение регистров процессора

Теорема о четырёх красках: любой планарный граф можно раскрасить в 4 цвета. Доказана в 1976 году (первое доказательство с использованием компьютера).

Реальные применения

Социальные сети

Люди = вершины, дружба/подписка = рёбра.

• Степень вершины → популярность
• Компоненты связности → изолированные сообщества
• Кратчайший путь → теория шести рукопожатий (диаметр графа Facebook ≈ 4.57)
• Центральность (betweenness centrality) → кто связывает разные группы, ключевые инфлюенсеры

Интернет и маршрутизация

• Маршрутизаторы = вершины, каналы = рёбра с весами (задержка, пропускная способность)
• Протокол OSPF использует алгоритм Дейкстры для поиска кратчайшего пути внутри автономной системы
• BGP строит деревья маршрутов между автономными системами

PageRank (Google)

Граф веб-страниц: страницы = вершины, ссылки = ориентированные рёбра. PageRank — случайное блуждание с вероятностью «телепортации». Математика: собственный вектор матрицы переходов.

Логистика и цепи поставок

Задача коммивояжёра (TSP): посетить $n$ городов, вернуться в начальный, минимальная суммарная длина. NP-полная задача. На практике — эвристики и приближённые алгоритмы.

Рекомендательные системы

Двудольный граф: пользователи ↔ товары. Коллаборативная фильтрация: «люди, которым понравилось то же, что и вам, также купили...»

Компиляторы

Абстрактное синтаксическое дерево (AST) — граф исходного кода. Оптимизации: удаление мёртвого кода (недостижимые вершины), общие подвыражения (изоморфные подграфы). Граф потока управления (CFG) для анализа достижимости и циклов.

Продвинутые концепции

Потоки в сетях

Ориентированный граф с источником и стоком, рёбра имеют пропускную способность. Задача: максимизировать поток от источника к стоку.

Алгоритм Форда—Фалкерсона ищет увеличивающие пути. Теорема о максимальном потоке и минимальном разрезе — фундаментальный результат.

Применение: распределение трафика, планирование производства, задача о назначениях, сегментация изображений.

Кластеризация графов

Разбиение вершин на группы с плотными внутренними связями и разреженными внешними. Спектральная кластеризация через собственные векторы матрицы Лапласа. Применение: сегментация клиентов, выделение сообществ, анализ социальных сетей.

Итого

Графы — это универсальный язык для описания связей. Таблица «задача — алгоритм»: