Теория графов
Основные понятия
Теория графов — раздел дискретной математики, изучающий свойства графов. Граф — это математическая абстракция, представляющая собой множество вершин (узлов) и множество рёбер, соединяющих пары вершин.
Определение графа
Формально граф $G$ определяется как пара множеств $G = (V, E)$, где:
- $V$ — непустое множество вершин (узлов)
- $E$ — множество рёбер, каждое из которых соединяет две вершины из $V$
Виды графов
- Неориентированный граф — граф, в котором рёбра не имеют направления
- Ориентированный граф (орграф) — граф, в котором рёбра имеют направление (называются дугами)
- Взвешенный граф — граф, рёбрам которого присвоены числовые значения (веса)
- Полный граф — граф, в котором каждая вершина соединена с каждой другой вершиной
- Двудольный граф — граф, вершины которого можно разделить на две группы так, что рёбра соединяют только вершины из разных групп
Представление графов
Матрица смежности
Матрица смежности графа $G$ с $n$ вершинами — это квадратная матрица $A$ размера $n \times n$, где элемент $A_{ij}$ равен:
- 1, если существует ребро из вершины $i$ в вершину $j$
- 0, если такого ребра нет
Для неориентированного графа матрица смежности симметрична относительно главной диагонали.
Список смежности
Список смежности — это массив списков, где для каждой вершины $i$ хранится список всех вершин $j$, с которыми она соединена рёбрами.
Основные характеристики графов
Степень вершины
Степень вершины $v$ (обозначается $\deg(v)$) — это количество рёбер, инцидентных данной вершине. В ориентированном графе различают входящую степень $\deg^-(v)$ и исходящую степень $\deg^+(v)$.
Лемма о рукопожатиях: Сумма степеней всех вершин графа равна удвоенному числу рёбер: $\sum_{v \in V} \deg(v) = 2|E|$.
Путь и цикл
Путь — последовательность вершин, в которой каждая вершина соединена ребром со следующей.
Цикл — путь, начинающийся и заканчивающийся в одной и той же вершине.
Простой путь — путь без повторяющихся вершин.
Простой цикл — цикл без повторяющихся вершин (кроме первой и последней).
Связность
Связный граф — граф, в котором существует путь между любыми двумя вершинами.
Компонента связности — максимальный связный подграф.
Алгоритмы на графах
Поиск в ширину (BFS)
Алгоритм поиска в ширину исследует все вершины на текущем уровне удаленности от начальной вершины, прежде чем перейти к вершинам на следующем уровне.
Применение: поиск кратчайшего пути в невзвешенном графе, проверка двудольности графа.
Сложность: $O(|V| + |E|)$, где $|V|$ — число вершин, $|E|$ — число рёбер.
Поиск в глубину (DFS)
Алгоритм поиска в глубину исследует как можно дальше вдоль каждой ветви, прежде чем возвращаться назад.
Применение: топологическая сортировка, поиск компонент сильной связности, проверка на наличие циклов.
Сложность: $O(|V| + |E|)$.
Алгоритм Дейкстры
Алгоритм нахождения кратчайших путей от одной вершины до всех остальных во взвешенном графе с неотрицательными весами рёбер.
Сложность: $O(|E| \log |V|)$ с использованием приоритетной очереди.
Алгоритм Флойда-Уоршелла
Алгоритм нахождения кратчайших путей между всеми парами вершин во взвешенном графе.
Сложность: $O(|V|^3)$.
Минимальное остовное дерево
Остовное дерево — подграф, являющийся деревом и содержащий все вершины исходного графа.
Минимальное остовное дерево (MST) — остовное дерево с минимальной суммой весов рёбер.
Алгоритм Прима: строит MST, начиная с одной вершины и добавляя рёбра минимального веса.
Алгоритм Крускала: строит MST, сортируя все рёбра по весу и добавляя их в порядке возрастания, если они не образуют цикл.
Специальные типы графов
Деревья
Дерево — связный ациклический граф. Свойства:
- Число рёбер равно числу вершин минус 1: $|E| = |V| - 1$
- Между любыми двумя вершинами существует ровно один простой путь
Эйлеров путь и цикл
Эйлеров путь — путь, проходящий через каждое ребро графа ровно один раз.
Эйлеров цикл — эйлеров путь, начинающийся и заканчивающийся в одной вершине.
Граф имеет эйлеров цикл тогда и только тогда, когда он связен и степень каждой вершины чётна.
Гамильтонов путь и цикл
Гамильтонов путь — путь, проходящий через каждую вершину графа ровно один раз.
Гамильтонов цикл — гамильтонов путь, замкнутый в цикл.
В отличие от эйлеровых путей, не существует простого критерия для определения наличия гамильтонова пути или цикла в графе.
Практические применения
Теория графов находит применение во многих областях:
- Компьютерные сети и маршрутизация
- Планирование проектов (метод критического пути)
- Социальные сети и анализ связей
- Химические структуры молекул
- Транспортные системы и логистика
- Искусственный интеллект и машинное обучение
