Графы — маршруты, остовы и раскраски
Play ITЗагрузка интерактивного демо…
Обзор графов, BFS, Дейкстры и комбинаторики — в Дискретная математика. Здесь — теория графов в объёме классического курса дискретной математики — представления, связность, остовы, разрезы, раскраски.
Школа (этап 28). Виды графов, эйлеровы и гамильтоновы пути, смежность, матрицы — кратко в разделе 22 «Базовой информатики».
Задание графа
Ориентированный граф G = ⟨M; R⟩ — множество вершин M и бинарное отношение дуг R ⊆ M². Неориентированный — пары {a,b}; взвешенный — функция веса на дугах μ(a,b).
| Способ | Плюсы | Минусы |
|---|---|---|
| Список смежности | разреженные графы, обход соседей | проверка ребра O(deg) |
| Матрица смежности | O(1) проверка ребра | O(n²) памяти |
| Матрица инцидентности | явная связь вершина–ребро | O(n·m) для m рёбер |
Матрица весов W | алгоритмы всех пар | та же память, что у смежности |
Лемма о рукопожатиях: сумма степеней всех вершин равна удвоенному числу рёбер: Σ d(v) = 2|E|. Следствие — в любом графе число вершин нечётной степени чётно (иначе сумма была бы нечётной). Быстрая проверка «сходится ли статистика по рёбрам» при импорте графа из CSV.
Изоморфизм графов G₁ ≅ G₂ — существует биекция вершин, сохраняющая смежность. Изоморфные графы не различают по «форме» связей, только по именам узлов. В IT: одна и та же топология микросервисов, перенесённая в другой namespace; сравнение схем без привязки к id.
Подграф — подмножество вершин и дуг; остов связного графа — связный подграф на всех вершинах без циклов (дерево на n вершинах имеет n−1 ребро).
Пути, связность, расстояния
- Маршрут — цепочка дуг; простой — без повторяющихся вершин.
- Связность в неорграфе — между любыми двумя вершинами есть маршрут.
- В орграфе: слабая связность — связность после игнорирования направлений дуг; сильная — для любой пары
u, vесть ориентированный путьu → v. - Расстояние
ρ(a,b)— длина кратчайшего маршрута; эксцентриситет, радиус, центр — см. Дискретная математика.
Кратчайшие пути во взвешенном графе с неотрицательными весами — жадные и динамические методы (матрица весов, последовательное улучшение расстояний). В энциклопедии реализации и сложность — в алгоритмах и обзоре Дискретная математика (Дейкстра, Флойд–Уоршелл).
Достижимость и алгоритм Уоршелла
Матрица достижимости M* орграфа: m*ᵢⱼ = 1, если существует ориентированный путь из i в j (длина ≥ 0 для рефлексивного варианта). Это транзитивное замыкание отношения дуг — см. формальный слой.
Алгоритм Уоршелла строит M* за O(n³) итераций:
M⁽⁰⁾ ← матрица смежности (с единицами на диагонали, если нужна рефлексивность)
для k от 1 до n:
для i, j от 1 до n:
M⁽ᵏ⁾[i,j] ← M⁽ᵏ⁻¹⁾[i,j] ИЛИ (M⁽ᵏ⁻¹⁾[i,k] И M⁽ᵏ⁻¹⁾[k,j])
вернуть M⁽ⁿ⁾
Идея: путь i → j либо не проходит через k, либо разбивается на i → k и k → j. Применения: «какие модули транзитивно зависят от библиотеки X», проверка reachability в RBAC, анализ орграфа вызовов.
Флойд–Уоршелл — тот же каркас тройного цикла, но вместо логического OR–AND берут минимум сумм весов; на выходе — кратчайшие расстояния, а не только факт достижимости.
Эйлер, Гамильтон, коммивояжёр
| Задача | Что ищем | Критерий / сложность |
|---|---|---|
| Эйлеров цикл | цикл через каждое ребро | в связном неорграфе все степени чётны |
| Гамильтонов цикл | цикл через каждую вершину | достаточные условия на степени; в общем случае NP-трудно |
| TSP | гамильтонов цикл минимального веса | перебор O(n!), эвристики на практике |
Задача коммивояжёра моделирует обход складов, сверление отверстий на плате, маршрут курьера.
Остовы, циклы, разрезы
Фундаментальный цикл — цикл, появляющийся при добавлении одного ребра к остову дерева. Разрез — множество рёбер, удаление которых увеличивает число компонент связности. В сетях разрез — "узкое место": отказ всех рёбер разреза рвёт связность.
Минимальный остов (MST) — остов минимального суммарного веса; алгоритмы Прима и Краскала — в Дискретная математика.
Раскраски и планарность
Раскраска вершин — присвоить цвета так, чтобы смежные вершины различались. Хроматическое число χ(G) — минимальное число цветов. Прикладные аналоги:
- распределение регистров или частот без конфликта;
- планирование экзаменов без пересечения аудиторий у одного студента (модель конфликтного графа).
Реберная раскраска — разные цвета у рёбер, инцидентных одной вершине. Хроматический индекс χ′(G) — минимальное число цветов рёбер. Аналог: смены курьеров по рёбрам маршрута или временные слоты каналов, выходящих из одного узла. Для простого графа всегда χ′(G) ≤ Δ(G) + 1, где Δ(G) — максимальная степень вершины.
Планарный граф можно нарисовать на плоскости без пересечения рёбер. Критерий Эйлера для связного планарного графа: m ≤ 3n − 6 (для n ≥ 3). Планарность важна при разводке печатных плат и топологии сетей на плоскости.
Практика обходов и оценка сложности — раздел "Алгоритмы".
Параллельные и распределённые графы — 4.16.
Назад: Дискретная математика. Формальные основы множеств: Множества и отношения — формальный слой. Рекуррентности в алгоритмах: Рекуррентные соотношения. Самопроверка: Дискретная математика — чек-лист самопроверки.