Графы — модели и задачи

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

Разработчику Аналитику Инженеру

---

Зачем программисту графы

Граф — множество вершин (узлов) и рёбер (связей между ними). Одна и та же абстракция описывает дороги на карте, дружбу в соцсети, гиперссылки между страницами, зависимости в сборке проекта или цепочки вызовов в программе.

Классический пример — мосты Кёнигсберга (XVIII век): можно ли пройти по каждому мосту ровно один раз? Леонард Эйлер свёл задачу к графу и показал, что ответ зависит только от чётности степеней вершин, а не от длины мостов. С тех пор графы — стандартный язык для задач «кто с кем связан и как пройти от A до B».

---

Основные определения

Термин	Смысл
Вершина (узел)	Объект: город, страница, пользователь, функция
Ребро (дуга, звено)	Связь между двумя вершинами
Направленный граф	Ребро имеет направление (A → B, но не обязательно B → A)
Ненаправленный граф	Связь симметрична
Вес ребра	Число на связи: расстояние, время, стоимость, «важность» ссылки
Путь	Цепочка рёбер, соединяющая вершины
Цикл	Путь, начинающийся и заканчивающийся в одной вершине
Ациклический граф	Без циклов (важно для DAG в планировании и сборках)

Степень вершины — число рёбер, с которыми она соединена. В задаче Кёнигсберга эйлеров цикл существует, только если у всех вершин чётная степень (с уточнениями для несвязных компонент).

---

Как хранить граф в программе

Представление	Когда удобно
Список смежности	Разреженные графы, обход соседей
Матрица смежности	Плотные графы, быстрая проверка «есть ли ребро»
Матрица весов	Кратчайшие пути, небольшие n

В списке смежности для каждой вершины хранят список соседей (и весов). Память порядка O(V + E) для V вершин и E рёбер.

---

Типичные задачи

Задача	Идея	Куда глубже
Обход всех вершин	BFS — в ширину (очередь), DFS — в глубину (стек/рекурсия)	структуры данных
Кратчайший путь	Жадная релаксация расстояний	Дейкстра
Связность	Достижимость из точки	обход BFS/DFS
Ранжирование важности	Распространение «голосов» по ссылкам	PageRank
Коммивояжёр	Обойти все вершины с минимальной суммой весов	алгоритмическое мышление — перебор O(n!)

Обход в ширину (BFS) находит кратчайший путь в неневзвешенном графе (каждое ребро «стоит» 1). Обход в глубину (DFS) удобен для проверки циклов, топологической сортировки зависимостей.

Формальные критерии (Эйлер, Гамильтон, остовы, раскраски) — в теории графов; ниже — то, что чаще всего пишут в коде.

---

Эйлеров и гамильтонов циклы

Цикл	Проходит	Критерий (идея)	Практика
Эйлеров	каждое ребро ровно раз	в связном неорграфе все степени чётны	обход всех рёбер сети, маршрут инспекции
Гамильтонов	каждую вершину ровно раз	в общем случае NP-трудно; есть достаточные условия на степени	коммивояжёр, доставка, сверление плат

Задача коммивояжёра — гамильтонов цикл минимального веса. Полный перебор O(n!); на практике — эвристики и приближения.

---

DAG и топологическая сортировка

Ориентированный ациклический граф (DAG) — нет направленных циклов. Моделирует зависимости: модуль B импортирует A, задача C ждёт B.

Топологическая сортировка — порядок вершин, в котором все рёбра идут «слева направо». Существует только для DAG. Реализация — DFS с выводом вершин в обратном порядке завершения или алгоритм Кана (очередь вершин с нулевым входящим счётчиком).

// Проверка: можно ли собрать проект (упрощённо)
если в графе зависимостей есть цикл то
  Ошибка("циклическая зависимость")
иначе
  порядок := топологическая_сортировка(граф)
  для каждого модуля m в порядок
    Собрать(m)
  конец
конец

---

Минимальный остов (MST)

Остов связного графа — подмножество рёбер, связывающее все вершины без циклов (n−1 ребро для n вершин). Минимальный остов — остов с минимальной суммой весов.

Алгоритм	Идея	Сложность (типично)
Прим	растим дерево из старта, каждый раз добавляем ребро минимального веса к новой вершине	O(E log V) с кучей
Краскал	сортируем рёбра по весу, добавляем, если не образует цикл (система непересекающихся множеств)	O(E log E)

Применение: проектирование сети связи, кластеризация, когда нужен «дешёвый каркас» без лишних циклов.

АЛГОРИТМ BFS(G, старт)
  создать очередь Q
  пометить старт как посещённую
  добавить старт в Q
  пока Q не пуста
    v := извлечь из начала Q
    для каждого соседа u вершины v
      если u ещё не посещена
        пометить u
        добавить u в Q
      конец если
    конец для
  конец пока
КОНЕЦ

---

Графы вокруг нас

• Социальные сети — вершины люди, рёбра «дружба» или «подписка».
• Веб — страницы и гиперссылки (PageRank).
• Маршруты — перекрёстки и дороги с длиной (Дейкстра).
• Сборка ПО — модули и зависимости (DAG, без циклов).
• Параллельные вычисления — граф зависимостей операторов (граф алгоритма).

Следующий шаг

Для взвешенных дорог с неотрицательными весами — алгоритм Дейкстры. Для оценки «важности» страниц в сети ссылок — PageRank.

---

Связанные материалы

• Сортировка и поиск — линейные структуры до графов
• Нотация Большое O — сложность обходов O(V + E)
• Дискретная математика, графы — углубление
• Алгоритмы — о разделе — маршрут раздела