Теория графов
Основные понятия
Теория графов — раздел дискретной математики, изучающий свойства графов. Граф — это математическая абстракция, представляющая собой множество вершин (узлов) и множество рёбер, соединяющих пары вершин.
Определение графа
Формально граф \(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\)
- Между любыми двумя вершинами существует ровно один простой путь
Эйлеров путь и цикл
Эйлеров путь — путь, проходящий через каждое ребро графа ровно один раз.
Эйлеров цикл — эйлеров путь, начинающийся и заканчивающийся в одной вершине.
Граф имеет эйлеров цикл тогда и только тогда, когда он связен и степень каждой вершины чётна.
Гамильтонов путь и цикл
Гамильтонов путь — путь, проходящий через каждую вершину графа ровно один раз.
Гамильтонов цикл — гамильтонов путь, замкнутый в цикл.
В отличие от эйлеровых путей, не существует простого критерия для определения наличия гамильтонова пути или цикла в графе.
Практические применения
Теория графов находит применение во многих областях:
- Компьютерные сети и маршрутизация
- Планирование проектов (метод критического пути)
- Социальные сети и анализ связей
- Химические структуры молекул
- Транспортные системы и логистика
- Искусственный интеллект и машинное обучение
