Дискретная математика

Теория графов: основы

Графы - это не абстракция из учебника. Git - это DAG коммитов. npm - граф зависимостей. Интернет - граф веб-страниц. Социальные сети, карты, компиляторы, базы данных - всё это задачи на графах.

**npm/pip:** при установке пакета менеджер топологически сортирует граф зависимостей, чтобы установить всё в правильном порядке
**Google Maps:** BFS/Дейкстра на взвешенном графе дорог строит оптимальный маршрут
**Git:** история коммитов - DAG (directed acyclic graph), `git log --graph` визуализирует его
**LinkedIn:** «6 рукопожатий» - BFS по графу профессиональных связей

Предварительные знания

Inclusion-Exclusion Principle

Что такое граф

Граф G = (V, E) - это пара: множество вершин V (nodes) и множество рёбер E (edges), где каждое ребро соединяет две вершины. Графы - универсальный язык для описания отношений: маршруты на карте, зависимости между модулями, связи в социальной сети.

**Неориентированный граф:** ребро (u, v) = (v, u) - связь симметрична (дружба в соцсети). **Ориентированный граф (орграф):** ребро (u → v) ≠ (v → u) - связь однонаправленная (импорт модуля, подписка).

Тип графа	Рёбра	Пример
Неориентированный	(u, v) = (v, u)	Дорожная сеть
Ориентированный	(u → v) ≠ (v → u)	Зависимости пакетов
Взвешенный	ребро имеет вес w	Расстояния между городами
Мультиграф	несколько рёбер между парой	Авиарейсы между городами

Граф можно задать тремя способами: **матрицей смежности** (O(V²) памяти, быстрая проверка наличия ребра), **списком смежности** (O(V+E) памяти, эффективен для разреженных графов), **списком рёбер** (компактен, удобен для алгоритмов вроде Крускала).

В реальных системах графы почти всегда **разреженные** (E << V²): у каждого пользователя соцсети - сотни друзей, а не миллиарды. Список смежности - выбор по умолчанию.

Система импортов Python-модулей (A импортирует B, B импортирует C) - какой тип графа лучше всего моделирует эту зависимость?

Степень вершины и смежность

Степень вершины deg(v) - количество рёбер, инцидентных вершине v. В орграфе различают in-degree (входящие рёбра) и out-degree (исходящие). Степень - базовая характеристика: высокая степень означает «хаб» в сети.

**Лемма о рукопожатиях:** сумма степеней всех вершин равна удвоенному числу рёбер: Σ deg(v) = 2|E|. Следствие: число вершин нечётной степени всегда чётно.

Матрица смежности A[i][j] = 1, если между вершинами i и j есть ребро, иначе 0. Для взвешенного графа - A[i][j] = вес ребра. Произведение матрицы A на себя k раз даёт число путей длиной k между вершинами - мощный инструмент анализа.

PageRank Google основан на in-degree: страница «важна», если на неё ведут рёбра от других важных страниц. Это обобщение простого подсчёта степени.

В неориентированном графе с 6 вершинами и 9 рёбрами чему равна сумма степеней всех вершин?

Обходы: DFS и BFS

Обход графа - систематический визит всех достижимых вершин. Два фундаментальных метода: **DFS** (поиск в глубину) - уходит как можно дальше перед возвратом, **BFS** (поиск в ширину) - исследует все вершины на текущем уровне перед переходом к следующему.

Критерий	DFS	BFS
Структура данных	Стек (рекурсия)	Очередь (deque)
Кратчайший путь	Нет	Да (по числу рёбер)
Обнаружение циклов	Да	Да
Топологическая сортировка	Да	Нет
Сложность	O(V + E)	O(V + E)

DFS на большом графе может вызвать **stack overflow** - рекурсия достигает глубины V. Используйте итеративный DFS со явным стеком для production-кода.

BFS - естественный выбор для задач «найти ближайшее»: ближайший свободный сервер, кратчайший путь в лабиринте, минимальное число ходов. DFS - для задач «найти любой путь» или топологической сортировки.

Требуется построить функцию «найти кратчайший путь между двумя пользователями в соцсети» (минимум связей-посредников). Какой алгоритм выбрать?

Компоненты связности

Граф **связный**, если между любыми двумя вершинами существует путь. Если граф несвязный, он распадается на **компоненты связности** - максимальные связные подграфы. Нахождение компонент - первый шаг анализа любого реального графа.

**Сильная связность** в орграфах: компонент сильной связности (SCC) - максимальное множество вершин, из любой из которых можно достичь любую другую. Алгоритм Косарайю находит все SCC за O(V+E).

Union-Find (система непересекающихся множеств, DSU) - эффективная структура для динамического отслеживания компонент: поддерживает операции «объединить компоненты» и «в одной ли компоненте?» за амортизированное O(α(V)) ≈ O(1).

При анализе легаси-кода компоненты связности графа зависимостей показывают «острова» - изолированные модули. Если компонентов больше одной, возможно, это мёртвый код или неиспользуемые библиотеки.

Граф из 8 вершин имеет рёбра: {1-2, 2-3, 4-5, 6-7, 7-8}. Сколько компонент связности?

Ключевые идеи

**G = (V, E):** граф - множество вершин и рёбер; ориентированный или нет в зависимости от задачи
**Список смежности:** стандартное представление для разреженных графов O(V+E)
**Лемма о рукопожатиях:** Σ deg(v) = 2|E| - фундаментальный факт о степенях
**BFS:** кратчайший путь по числу рёбер, обходит «уровнями»
**DFS:** топологическая сортировка, обнаружение циклов, обход в глубину
**Компоненты связности:** нахождение «островов» за O(V+E) через DFS/BFS

Связанные темы

Теория графов - фундамент для более сложных алгоритмов и структур.

Деревья и их свойства — Дерево - это связный граф без циклов, частный случай
Планарность и раскраска — Свойства вложения графов в плоскость и раскраска вершин
Потоки в сетях — Нахождение максимального потока в ориентированном взвешенном графе

Вопросы для размышления

Какая структура данных (матрица или список смежности) эффективнее для графа с 10 000 вершин и 15 000 рёбер? Почему?
Как бы вы определили цикл в орграфе зависимостей пакетов и что это означает на практике?
Если BFS и DFS имеют одинаковую сложность O(V+E), почему выбор между ними всё равно важен?

Связанные уроки