Графы — маршруты, остовы и раскраски

НЕ ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Архитектору Инженеру

Обзор графов, BFS, Дейкстры и комбинаторики — в 32. Здесь — теория графов в объёме классического курса дискретной математики: представления, связность, остовы, разрезы, раскраски.

---

Задание графа

Ориентированный граф G = ⟨M; R⟩ — множество вершин M и бинарное отношение дуг R ⊆ M². Неориентированный — пары {a,b}; взвешенный — функция веса на дугах μ(a,b).

Способ	Плюсы	Минусы
Список смежности	разреженные графы, обход соседей	проверка ребра O(deg)
Матрица смежности	O(1) проверка ребра	O(n²) памяти
Матрица весов W	алгоритмы всех пар	та же память

Подграф — подмножество вершин и дуг; остов связного графа — связный подграф на всех вершинах без циклов (дерево на n вершинах имеет n−1 ребро).

---

Пути, связность, расстояния

• Маршрут — цепочка дуг; простой — без повторяющихся вершин.
• Связность — между любыми двумя вершинами есть маршрут (в орграфе — слабая/сильная).
• Расстояние ρ(a,b) — длина кратчайшего маршрута; эксцентриситет, радиус, центр — см. 32.

Кратчайшие пути во взвешенном графе с неотрицательными весами — жадные и динамические методы (матрица весов, последовательное улучшение расстояний). В энциклопедии реализации и сложность — в алгоритмах и обзоре 32 (Дейкстра, Флойд–Уоршелл).

---

Эйлер, Гамильтон, коммивояжёр

Задача	Что ищем	Критерий / сложность
Эйлеров цикл	цикл через каждое ребро	в связном неорграфе все степени чётны
Гамильтонов цикл	цикл через каждую вершину	достаточные условия на степени; в общем случае NP-трудно
TSP	гамильтонов цикл минимального веса	перебор O(n!), эвристики на практике

Задача коммивояжёра моделирует обход складов, сверление отверстий на плате, маршрут курьера.

---

Остовы, циклы, разрезы

Фундаментальный цикл — цикл, появляющийся при добавлении одного ребра к остову дерева. Разрез — множество рёбер, удаление которых увеличивает число компонент связности. В сетях разрез — «узкое место»: отказ всех рёбер разреза рвёт связность.

Минимальный остов (MST) — остов минимального суммарного веса; алгоритмы Прима и Краскала — в 32.

---

Раскраски и планарность

Раскраска вершин — присвоить цвета так, чтобы смежные вершины различались. Хроматическое число — минимальное число цветов. Прикладные аналоги:

• распределение регистров или частот без конфликта;
• планирование экзаменов без пересечения аудиторий у одного студента (модель конфликтного графа).

Планарный граф можно нарисовать на плоскости без пересечения рёбер. Критерий Эйлера для связного планарного графа: m ≤ 3n − 6 (для n ≥ 3). Планарность важна при разводке печатных плат и топологии сетей на плоскости.

---

Куда дальше

Практика обходов и оценка сложности — раздел «Алгоритмы». Параллельные и распределённые графы — 4.16.

Назад: 32. Формальные основы множеств: 321. Самопроверка: 325.

---