Теория графов: структуры, свойства и теоремы

Граф — пожалуй, самая полезная математическая абстракция для программиста. Не потому, что «на собеседовании спрашивают BFS», а потому что граф — это минимальный язык, на котором записывается любая бинарная связь: кто на кого ссылается, что от чего зависит, кто с кем может обменяться сообщением, какой тип приводится к какому. Как только вы научились видеть граф в задаче, вы получаете доступ к столетнему багажу теорем и алгоритмов, которые уже решены за вас.

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

Карта территории

1. Строгие определения

Определение. Простой неориентированный граф — это пара G = (V, E), где V — конечное непустое множество (вершины), а E — множество неупорядоченных пар различных вершин (рёбра): E ⊆ { {u,v} : u,v ∈ V, u ≠ v }.

Разберём варианты, которые часто путают:

Условие «E — множество пар» — это в точности бинарное отношение на V из статьи про теорию множеств. Неориентированный граф = симметричное антирефлексивное отношение. Это не игра словами: многие свойства графов — переформулировки свойств отношений (транзитивное замыкание = достижимость, отношение эквивалентности = разбиение на компоненты связности).

Степень deg(v) — число инцидентных вершине рёбер (петля считается дважды); в орграфе различают indeg(v) и outdeg(v). Лемма о рукопожатиях: для любого графа sum_{v in V} deg(v) = 2 * |E|.

Доказательство в одну строку: двумя способами считаем количество пар вида (вершина, инцидентное ей ребро). Каждое ребро даёт ровно две такие пары. Это классический double counting.

Следствие. Число вершин нечётной степени всегда чётно. Отсюда сразу: в компании из 9 человек невозможно, чтобы каждый пожал руку ровно троим (9·3 = 27 нечётно). Практическая ценность леммы — быстрый sanity-check при построении графов из данных: если вы собрали граф зависимостей и sum(deg) != 2*len(edges), значит где-то ребро добавлено только в одну сторону — типичный баг при ручном заполнении списков смежности.

Изоморфизм. Графы G и H изоморфны, если существует биекция f: V(G) → V(H), сохраняющая смежность. Важный момент: «нарисовано по-разному» ≠ «разные графы». Задача проверки изоморфизма знаменита тем, что не известна ни как принадлежащая P, ни как NP-полная; лучший результат — квазиполиномиальный алгоритм Бабаи, 2015 (arxiv.org/abs/1512.03547). Почему это удивительно — в статье про теорию сложности.

2. Как граф лежит в памяти

Выбор представления определяет и сложность алгоритма, и то, влезет ли граф в RAM.

Ключевая развилка — плотность. Если E ~ V² (плотный граф), матрица выигрывает и по памяти на бит, и по кэшу. Если E ~ V (разреженный — почти все реальные графы: соцсети, веб, зависимости пакетов), матрица катастрофична: миллион вершин это 10¹² ячеек. CSR (Compressed Sparse Row) — тот же список смежности, но уложенный в два плоских массива; так графы хранят SciPy, cuGraph и GNN-фреймворки, потому что обход соседей идёт линейно по памяти, а не прыжками по указателям.

def build_csr(n, edges, directed=False):
    """Построение CSR из списка рёбер. Время O(V+E), память O(V+E)."""
    deg = [0] * n
    for u, v in edges:
        deg[u] += 1
        if not directed:
            deg[v] += 1

    offsets = [0] * (n + 1)
    for i, d in enumerate(deg):          # префиксные суммы -> границы блоков
        offsets[i + 1] = offsets[i] + d

    cursor = offsets[:-1]                # текущая позиция записи для каждой вершины
    targets = [0] * offsets[n]
    for u, v in edges:
        targets[cursor[u]] = v; cursor[u] += 1
        if not directed:
            targets[cursor[v]] = u; cursor[v] += 1
    return offsets, targets

def neighbours(offsets, targets, v):     # срез — соседи вершины v
    return targets[offsets[v]:offsets[v + 1]]

off, tgt = build_csr(4, [(0, 1), (0, 2), (1, 2), (2, 3)])
print(off)                       # [0, 2, 4, 7, 8]
print(tgt)                       # [1, 2, 0, 2, 0, 1, 3, 2]
print(neighbours(off, tgt, 2))   # [0, 1, 3]

Матрица смежности как линейный оператор

Матрица смежности — не просто способ хранения, а полноценный объект линейной алгебры, и это источник неожиданно сильных результатов.

Теорема о степенях матрицы. Элемент (A^k)[i][j] равен числу маршрутов длины ровно k из i в j (маршрут — последовательность рёбер, вершины могут повторяться). Доказательство — индукция по k: (A^{k+1})[i][j] = sum_m (A^k)[i][m] * A[m][j], то есть маршрут длины k+1 = маршрут длины k до какого-то соседа m плюс последнее ребро.

import numpy as np

A = np.array([[0, 1, 1, 0],
              [1, 0, 1, 0],
              [1, 1, 0, 1],
              [0, 0, 1, 0]])

print(A @ A)
# [[2 1 1 1]
#  [1 2 1 1]
#  [1 1 3 0]
#  [1 1 0 1]]
# (A^2)[2][2] = 3 — три маршрута длины 2 из вершины 2 обратно в себя,
# по одному через каждого соседа 0, 1, 3; в общем случае это ровно deg(v).
print(np.trace(A @ A @ A) // 6)   # 1 — число треугольников

Формула trace(A³)/6 считает треугольники: след A³ — это число замкнутых маршрутов длины 3, а каждый треугольник даёт их 6 (3 стартовые вершины × 2 направления). Не учебная игрушка: так реально считают коэффициент кластеризации в больших сетях, потому что умножение разреженных матриц отлично параллелизуется. Матричная арифметика подробно — в статье про матрицы и линейные отображения.

3. Связность, обходы и классификация рёбер

Путь — маршрут без повторения вершин. Цикл — замкнутый путь. Граф связен, если между любыми двумя вершинами есть путь. Отношение «достижим из» в неориентированном графе — отношение эквивалентности, а его классы — это в точности компоненты связности. Два базовых обхода, BFS и DFS, отличаются структурой данных (очередь vs стек) и тем, какую информацию дают:

Ключевая теоретическая вещь в DFS — классификация рёбер. Отслеживая три состояния вершины, мы получаем инструмент, решающий сразу несколько задач:

WHITE, GRAY, BLACK = 0, 1, 2

def find_cycle(graph, n):
    """Поиск цикла в орграфе трёхцветной разметкой. O(V+E) время, O(V) память."""
    color, parent = [WHITE] * n, [-1] * n

    def dfs(u):
        color[u] = GRAY
        for v in graph.get(u, ()):
            if color[v] == WHITE:
                parent[v] = u
                res = dfs(v)
                if res:
                    return res
            elif color[v] == GRAY:          # обратное ребро -> цикл
                path, x = [], u             # разматываем стек от u назад до v
                while x != v:
                    path.append(x); x = parent[x]
                path.append(v)
                return path[::-1] + [v]
        color[u] = BLACK
        return None

    for s in range(n):
        if color[s] == WHITE and (c := dfs(s)):
            return c
    return None

print(find_cycle({0: [1], 1: [2], 2: [0], 3: [1]}, 4))   # [0, 1, 2, 0]
print(find_cycle({0: [1], 1: [2], 2: [], 3: [1]}, 4))    # None

Именно этот алгоритм крутится внутри детектора взаимных блокировок в СУБД: строится wait-for graph (транзакция T1 ждёт блокировку, удерживаемую T2), и цикл в нём — это deadlock. PostgreSQL делает ровно это по таймауту deadlock_timeout (документация).

Сильная связность

В орграфе связность распадается на два понятия. Граф сильно связен, если из любой вершины достижима любая. Компоненты сильной связности (SCC) — максимальные сильно связные подграфы. Ключевой факт: если стянуть каждую SCC в одну вершину, получится DAG — граф конденсации. То есть любой орграф это DAG, у которого вместо вершин сидят «клубки» взаимной достижимости.

def tarjan_scc(graph, n):
    """SCC за один проход DFS (Тарьян, 1972). Время O(V+E), память O(V)."""
    index, low = [None] * n, [0] * n
    on_stack = [False] * n
    stack, out, counter = [], [], 0

    def dfs(v):
        nonlocal counter
        index[v] = low[v] = counter; counter += 1
        stack.append(v); on_stack[v] = True
        for w in graph.get(v, ()):
            if index[w] is None:
                dfs(w)
                low[v] = min(low[v], low[w])
            elif on_stack[w]:               # w в текущем кандидате на SCC
                low[v] = min(low[v], index[w])
        if low[v] == index[v]:              # v — корень SCC
            comp = []
            while True:
                w = stack.pop(); on_stack[w] = False; comp.append(w)
                if w == v:
                    break
            out.append(sorted(comp))

    for v in range(n):
        if index[v] is None:
            dfs(v)
    return out

g = {0: [1], 1: [2], 2: [0, 3], 3: [4], 4: [5], 5: [3], 6: []}
print(tarjan_scc(g, 7))    # [[3, 4, 5], [0, 1, 2], [6]]

Где это применяют по-настоящему. Компиляторы и линтеры: циклические импорты модулей — это SCC размера больше 1 в графе импортов (madge для JS, go list -deps для Go строят ровно этот граф). 2-SAT: формула из дизъюнкций по две переменные выполнима тогда и только тогда, когда ни для какой переменной x вершины x и ¬x не лежат в одной SCC графа импликаций — линейный алгоритм для задачи, чей «старший брат» 3-SAT NP-полон. Анализ живучести переменных и сворачивание циклов в графе потока управления.

4. Деревья: шесть определений одного объекта

Дерево — связный ациклический граф. Ценность в том, что это определение эквивалентно ещё пяти, и на практике удобно каждый раз брать подходящее.

Теорема (характеризация дерева). Для графа G с n вершинами эквивалентны:

1. G связен и не содержит циклов;
2. G связен и |E| = n - 1;
3. G ациклический и |E| = n - 1;
4. между любыми двумя вершинами существует ровно один путь;
5. G связен, но удаление любого ребра делает его несвязным (минимально связный);
6. G ациклический, но добавление любого ребра создаёт цикл (максимально ациклический).

Набросок доказательства (1) ⇒ (2): индукция по n. При n = 1 рёбер 0. При n > 1 в дереве есть лист (вершина степени 1) — иначе, идя всё время в новую вершину, мы обязаны замкнуть цикл по принципу Дирихле. Удаляем лист: получаем дерево на n−1 вершинах, у которого по предположению n−2 ребра; возвращаем лист с его единственным ребром, итого n−1.

Следствие для кода: проверка «это дерево?» — это связен && |E| == V - 1, две дешёвые проверки вместо поиска циклов. Остовное дерево (spanning tree) — подграф, являющийся деревом и содержащий все вершины; минимальное остовное дерево строится Крускалом (O(E log E), DSU) или Примом (O(E log V), куча) — детали в треке про алгоритмы.

Теорема Кэли. Число помеченных деревьев на n вершинах равно n^(n-2). Для n = 4 это 16 — можно перечислить руками. Красивое доказательство идёт через код Прюфера: биекция между деревьями и последовательностями длины n−2 из алфавита {1..n} — образцовый пример комбинаторной биекции.

Теорема Кирхгофа: считаем остовные деревья определителем

Здесь графы впервые всерьёз сливаются с линейной алгеброй. Введём лапласиан: L = D - A, где D = diag(deg(v)), а A — матрица смежности.

Теорема о матрице-дереве (Кирхгоф, 1847). Число остовных деревьев графа равно определителю любого главного минора L, полученного вычёркиванием одной строки и одноимённого столбца.

import numpy as np

def spanning_tree_count(A):
    L = np.diag(A.sum(axis=1)) - A
    minor = np.delete(np.delete(L, 0, axis=0), 0, axis=1)   # вычёркиваем строку и столбец 0
    return round(np.linalg.det(minor))

def laplacian_spectrum(A):
    return np.round(np.linalg.eigvalsh(np.diag(A.sum(axis=1)) - A), 6)

A = np.array([[0, 1, 1, 0],      # треугольник 0-1-2 плюс висячая вершина 3
              [1, 0, 1, 0],
              [1, 1, 0, 1],
              [0, 0, 1, 0]])
print(spanning_tree_count(A))    # 3 — убираем любое из трёх рёбер треугольника
print(laplacian_spectrum(A))     # [0. 1. 3. 4.] — ровно один ноль, граф связен

K4 = np.ones((4, 4), dtype=int) - np.eye(4, dtype=int)
print(spanning_tree_count(K4))   # 16 = 4^2 — совпало с формулой Кэли

two_parts = np.array([[0, 1, 0, 0], [1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0]])
print(laplacian_spectrum(two_parts))   # [0. 0. 2. 2.] — два нуля, две компоненты

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

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

Ориентированный ациклический граф — вероятно, самая частая структура в инженерной практике: сборочные системы, миграции БД, dataflow в Spark и Airflow, история коммитов git, дерево зависимостей npm и go modules, план запроса в СУБД.

История git — буквально DAG: вершины это коммиты, рёбра ведут к родителям, merge-коммит имеет двух родителей. git log --topo-order — топологическая сортировка, git merge-base — поиск наименьшего общего предка в DAG, а невозможность «цикла коммитов» гарантируется тем, что хеш родителя входит в хеш ребёнка.

Теорема. Орграф допускает топологический порядок ⟺ он ацикличен. (⇐) Алгоритм Кана строит порядок явно — существование доказано конструктивно. (⇒) Если бы был цикл v1 → v2 → ... → vk → v1, то в линейном порядке v1 обязана идти раньше себя, противоречие.

from collections import deque

def topological_sort(graph, n):
    """Алгоритм Кана. Время O(V+E), память O(V). None, если есть цикл."""
    indeg = [0] * n
    for u in range(n):
        for v in graph.get(u, ()):
            indeg[v] += 1

    # deque -> любой валидный порядок; heapq -> лексикографически минимальный
    # (детерминированные, а значит кэшируемые сборки).
    q = deque(v for v in range(n) if indeg[v] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph.get(u, ()):
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else None   # вышли не все => остался цикл

print(topological_sort({0: [1, 2], 1: [3], 2: [3], 3: [4], 4: []}, 5))  # [0, 1, 2, 3, 4]
print(topological_sort({0: [1], 1: [0]}, 2))                            # None

Практические заметки, которые стоят дороже самого алгоритма:

• Диагностика важнее факта. Ответ «есть цикл» бесполезен пользователю. Хороший сборщик печатает сам цикл — для этого используйте DFS с трёхцветной разметкой (см. выше), она возвращает конкретную последовательность вершин.
• Критический путь. На DAG задача «самый длинный путь» решается за O(V+E) одним проходом по топологическому порядку — при том, что в произвольном графе она NP-трудна. Так считают критический путь проекта и минимальное время сборки при бесконечном параллелизме.
• Динамическое программирование — это DAG. Любая корректная схема ДП есть топологический порядок на графе подзадач; если подзадачи не упорядочиваются ациклически, ДП не сойдётся. Отсюда же вывод, что мемоизация — это обход того же DAG в глубину.
• Детерминизм. Замена очереди на min-heap даёт воспроизводимый порядок при одинаковом входе, что критично для кэшируемости сборок в Bazel и Nix.

6. Двудольные графы, паросочетания и теорема Кёнига

Граф двудольный, если V разбивается на X и Y так, что все рёбра идут между X и Y. Теорема (критерий двудольности). Граф двудолен ⟺ в нём нет циклов нечётной длины. Интуиция: красим BFS-обходом по слоям в два цвета; конфликт возникнет ровно тогда, когда ребро соединит вершины одинаковой чётности слоя, что замыкает нечётный цикл.

from collections import deque

def bipartition(graph, n):
    """Двухцветная раскраска BFS. O(V+E). None, если есть нечётный цикл."""
    color = [-1] * n
    for s in range(n):
        if color[s] != -1:
            continue
        color[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in graph.get(u, ()):
                if color[v] == -1:
                    color[v] = color[u] ^ 1
                    q.append(v)
                elif color[v] == color[u]:
                    return None            # ребро внутри доли -> нечётный цикл
    return color

print(bipartition({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]}, 4))  # [0,1,0,1] — квадрат
print(bipartition({0: [1, 2], 1: [0, 2], 2: [0, 1]}, 3))             # None — треугольник

Паросочетание (matching) — множество рёбер без общих вершин. Вершинное покрытие — множество вершин, задевающее каждое ребро. Теорема Кёнига: в двудольном графе размер максимального паросочетания равен размеру минимального вершинного покрытия. Это редкий и мощный факт: минимальное вершинное покрытие в общем случае NP-полно, но на двудольных графах решается полиномиально именно благодаря Кёнигу. Максимальное паросочетание ищут алгоритмом Хопкрофта–Карпа за O(E * sqrt(V)).

Теорема Холла (о свадьбах). Паросочетание, покрывающее всё X, существует ⟺ для любого подмножества S ⊆ X выполнено |N(S)| ≥ |S|, где N(S) — множество соседей S. По-инженерному это читается так: «нельзя раздать всем задачам исполнителей, если найдётся k задач, которые в сумме умеют делать меньше k человек». Тот самый критерий, что лежит в основе назначения шардов на узлы, распределения ревьюеров на пул-реквесты и матчинга рекламных показов.

7. Эйлеровы и гамильтоновы обходы: близнецы с разной судьбой

Два внешне похожих вопроса с радикально разной вычислительной сложностью — поучительнейшая пара во всей дискретной математике. Эйлеров цикл проходит по каждому ребру ровно один раз. Гамильтонов цикл проходит через каждую вершину ровно один раз.

Теорема Эйлера (1736, задача о кёнигсбергских мостах). Связный граф содержит эйлеров цикл ⟺ степень каждой вершины чётна. Эйлеров путь (не цикл) существует ⟺ вершин нечётной степени ровно две. Интуиция необходимости: каждый раз, входя в вершину, обход должен из неё выйти по другому ребру — рёбра при вершине разбиваются на пары. Достаточность доказывается алгоритмом Хирхольцера, строящим цикл за O(E).

А для гамильтонова цикла критерия такого рода нет и, скорее всего, быть не может: задача NP-полна (одна из 21 задачи Карпа, 1972). Есть лишь достаточные условия, например теорема Дирака: если n ≥ 3 и deg(v) ≥ n/2 для всех v, гамильтонов цикл существует.

def eulerian_status(graph, n):
    """Классификация по теореме Эйлера. O(V+E). Связность считаем проверенной отдельно."""
    odd = [v for v in range(n) if len(graph.get(v, ())) % 2 == 1]
    if not odd:
        return "эйлеров цикл"
    if len(odd) == 2:
        return f"эйлеров путь между {odd[0]} и {odd[1]}"
    return f"нет эйлерова обхода: {len(odd)} вершин нечётной степени"

print(eulerian_status({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]}, 4))   # эйлеров цикл
# Кёнигсберг: мультиграф из 4 берегов и 7 мостов
print(eulerian_status({0: [1, 1, 2, 2, 3], 1: [0, 0, 3], 2: [0, 0, 3], 3: [0, 1, 2]}, 4))
# нет эйлерова обхода: 4 вершин нечётной степени

Кёнигсберг в 1736-м имел четыре вершины нечётной степени — потому прогулки по всем семи мостам ровно по разу не существует; Эйлер, отвечая на городскую головоломку, изобрёл целую дисциплину. И это не музейный экспонат: сборка геномов через графы де Брёйна сводится ровно к поиску эйлерова пути, потому что это полиномиально, тогда как наивная формулировка «пройти через каждый прочитанный фрагмент» (гамильтонов путь) NP-трудна. См. Compeau, Pevzner, Tesler, «How to apply de Bruijn graphs to genome assembly», Nature Biotechnology 2011 (PMC5531759).

8. Планарность и формула Эйлера

Граф планарен, если его можно нарисовать на плоскости без пересечения рёбер.

Формула Эйлера. Для связного планарного графа с укладкой на плоскости V - E + F = 2, где F — число граней, включая внешнюю. Проверим на кубе: V = 8, E = 12, F = 6, и 8 − 12 + 6 = 2. Следствие (ограничение на плотность). Для простого планарного графа с V ≥ 3 верно E ≤ 3V - 6; если ещё и нет треугольников (например, граф двудолен) — E ≤ 2V - 4. Вывод: каждая грань ограничена минимум тремя рёбрами, каждое ребро граничит максимум с двумя гранями, значит 3F ≤ 2E; подставляем F = 2 - V + E и получаем неравенство.

Отсюда мгновенно следует непланарность двух графов на схеме, а теорема Куратовского утверждает обратное направление в максимально сильной форме: граф планарен ⟺ он не содержит подграфа, являющегося подразбиением K5 или K3,3. То есть эти два графа — единственные «атомы» непланарности.

Ещё два следствия, которые полезно держать в голове. Во-первых, в любом планарном графе есть вершина степени ≤ 5 (иначе 2E ≥ 6V, что противоречит E ≤ 3V−6) — это ключ к доказательству, что планарный граф раскрашивается в 6, а с усилием и в 5 цветов. Во-вторых, теорема о четырёх красках (Аппель, Хакен, 1976) стала первым крупным результатом, доказанным с существенной помощью компьютера, что вызвало долгую дискуссию о природе математического доказательства; формально верифицированная версия построена в Coq (Gonthier, 2005, ams.org/notices/200811/tx081101382p.pdf). А нужна планарность в проде вот где: разводка печатных плат и трассировка микросхем (пересечение проводников = дополнительный слой = деньги), отрисовка графов (алгоритмы Тутта и ортогональные укладки в Graphviz), навигация — дорожные сети почти планарны, что позволяет строить сепараторы и радикально ускорять маршрутизацию.

9. Раскраска графов и распределение регистров

Хроматическое число χ(G) — минимальное число цветов, при котором смежные вершины покрашены по-разному. Вычисление χ(G) NP-трудно; уже вопрос «χ(G) ≤ 3?» NP-полон. Простые границы: χ(G) ≥ ω(G) (размер максимальной клики) и χ(G) ≤ Δ(G) + 1; теорема Брукса уточняет, что равенство справа достигается только на полных графах и нечётных циклах.

def greedy_coloring(graph, order):
    """Жадная раскраска в заданном порядке. O(V+E).
    Гарантирует не более Δ+1 цветов, но НЕ оптимальна."""
    color = {}
    for v in order:
        used = {color[u] for u in graph.get(v, ()) if u in color}
        c = 0
        while c in used:
            c += 1
        color[v] = c
    return color

g = {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]}
print(greedy_coloring(g, [0, 1, 2, 3]))   # {0: 0, 1: 1, 2: 2, 3: 0} — 3 цвета, оптимум
# Порядок решает: на графе-"короне" жадный алгоритм даёт V/2 цветов вместо двух.

Главное применение в системном программировании — распределение регистров. Строится граф интерференции: вершина — виртуальная переменная, ребро — «две переменные живы одновременно, значит не могут делить один физический регистр». Раскраска в k цветов = назначение k регистров. Если раскраски нет, компилятор делает spill — выгружает переменную в стек. Классика — Chaitin (1981) и Briggs; LLVM и GCC используют вариации, а некоторые JIT переходят на linear scan ради скорости компиляции (LLVM docs). Другие живые применения: составление расписаний (экзамены, слоты вещания), назначение частот базовым станциям, судоку (это раскраска в 9 цветов), анализ кэш-конфликтов, дедупликация конкурирующих задач в шедулере.

10. Потоки в сетях и теорема о максимальном потоке

Сеть — орграф с пропускными способностями c(u,v) ≥ 0, источником s и стоком t. Поток удовлетворяет ограничению 0 ≤ f(u,v) ≤ c(u,v) и закону сохранения во всех промежуточных вершинах. Теорема Форда–Фалкерсона (max-flow min-cut). Величина максимального потока равна минимальной пропускной способности разреза, отделяющего s от t. Это одна из самых плодотворных теорем прикладной математики: она превращает задачу оптимизации («максимизировать») в задачу о структуре («найти узкое место») и служит мостом к двойственности в линейном программировании.

from collections import deque

def edmonds_karp(capacity, s, t):
    """Максимальный поток BFS-путями. O(V * E^2).
    Возвращает величину потока и S-сторону минимального разреза."""
    n = len(capacity)
    cap = [row[:] for row in capacity]     # остаточная сеть
    flow = 0

    while True:
        parent = [-1] * n
        parent[s] = s
        q = deque([s])
        while q and parent[t] == -1:       # BFS -> кратчайший увеличивающий путь
            u = q.popleft()
            for v in range(n):
                if parent[v] == -1 and cap[u][v] > 0:
                    parent[v] = u; q.append(v)
        if parent[t] == -1:
            break                          # увеличивающего пути нет -> оптимум

        aug, v = float('inf'), t
        while v != s:                      # бутылочное горлышко пути
            aug = min(aug, cap[parent[v]][v]); v = parent[v]
        v = t
        while v != s:                      # прямое ребро уменьшаем, обратное увеличиваем
            cap[parent[v]][v] -= aug; cap[v][parent[v]] += aug; v = parent[v]
        flow += aug

    seen = [False] * n; seen[s] = True; q = deque([s])
    while q:                               # достижимые в остаточной сети = S-сторона разреза
        u = q.popleft()
        for v in range(n):
            if not seen[v] and cap[u][v] > 0:
                seen[v] = True; q.append(v)
    return flow, [i for i, x in enumerate(seen) if x]

C = [[0, 16, 13, 0, 0, 0],     # классическая сеть из CLRS, глава про потоки
     [0, 0, 10, 12, 0, 0],
     [0, 4, 0, 0, 14, 0],
     [0, 0, 9, 0, 0, 20],
     [0, 0, 0, 7, 0, 4],
     [0, 0, 0, 0, 0, 0]]
print(edmonds_karp(C, 0, 5))   # (23, [0, 1, 2, 4])
# Разрез S={0,1,2,4}, T={3,5}: рёбра 1->3 (12), 4->3 (7), 4->5 (4) = 23 — равно потоку.

Наивный Форд–Фалкерсон с произвольным выбором пути может не сойтись на иррациональных пропускных способностях; Эдмондс–Карп (BFS, то есть кратчайший путь) даёт гарантию O(V·E²), Диниц — O(V²·E), а на единичных пропускных способностях O(E·sqrt(E)). В 2022 году появился алгоритм почти линейной сложности m^{1+o(1)} (Chen et al., arxiv.org/abs/2203.00671) — теоретический прорыв, пока без практичных реализаций. Приложения потоков: двудольное паросочетание (сводится к потоку с единичными пропускными способностями), сегментация изображений (graph cut в компьютерном зрении), надёжность сети (теорема Менгера: число рёберно-непересекающихся путей равно минимальному разрезу), планирование загрузки в дата-центрах.

11. Типичные заблуждения

«Граф — это картинка». Граф — это множество пар. Одно и то же множество рисуется бесконечным числом способов, а свойства (связность, планарность, χ) от рисунка не зависят. Обратное тоже верно: «выглядит запутанно» не означает «непланарен».

«Матрица смежности — универсальное представление». Для графа веб-масштаба это 10¹⁸ ячеек. Реальные графы разрежены; по умолчанию берите CSR или списки смежности, а матрицу — только для плотных графов или когда нужен спектр.

«BFS даёт кратчайший путь». Только по числу рёбер. Как только появляются веса, нужен Дейкстра (веса ≥ 0) или Беллман–Форд (могут быть отрицательные). Классическая продовая ошибка — BFS на графе, где рёбра размечены задержками. И следом: «Дейкстра заработает с отрицательными весами, если сдвинуть все веса на константу». Нет. Сдвиг меняет стоимость путей неравномерно: путь из 5 рёбер получает +5c, из 2 рёбер +2c, и оптимум смещается. Корректный приём — потенциалы Джонсона, но они сами считаются Беллманом–Фордом.

«Ациклический значит дерево». Ациклический граф без связности — это лес. Дерево = ациклический и связный. И отдельно: DAG — не «направленное дерево»; в DAG у вершины может быть много родителей и много путей до неё, из-за чего число путей бывает экспоненциальным при линейном числе рёбер. «Цикл в орграфе ловится проверкой множества посещённых вершин». Нет: попадание в уже чёрную (полностью обработанную) вершину — это прямое или перекрёстное ребро, цикла оно не даёт. Цикл даёт только попадание в серую вершину. На этой ошибке ломается половина самописных детекторов циклических зависимостей.

«NP-трудность задачи на графах означает, что её не решить». Означает лишь отсутствие известного полиномиального алгоритма в худшем случае. На практике раскраска графов интерференции выполняется в компиляторах миллионы раз в день, а задача коммивояжёра решается точно на десятках тысяч городов (Concorde). Помогают структурные ограничения: планарность, малая древесная ширина (treewidth), ограниченная степень.

12. Мини-итог

• Граф = бинарное отношение; всё, что вы знаете об отношениях, переносится сюда. Лемма о рукопожатиях — простейший, но постоянно работающий инвариант и sanity-check.
• Представление выбирается по плотности: E ~ V² → матрица, E ~ V → CSR или списки смежности.
• Матрица смежности и лапласиан переводят граф на язык линейной алгебры: степени A считают маршруты, минор L считает остовные деревья, спектр L видит компоненты и «узкие места».
• У дерева шесть эквивалентных определений; для кода удобнее всего связен && E == V - 1.
• DFS с тремя цветами — универсальный инструмент: циклы, топсорт, SCC, мосты. DAG превращает NP-трудные задачи (длиннейший путь) в линейные — структура важнее алгоритма.
• Эйлер vs Гамильтон — образцовая иллюстрация того, что похожие формулировки живут в разных классах сложности.
• max-flow = min-cut — мост между оптимизацией, комбинаторикой и линейным программированием.

Источники

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 4-е изд., часть VI — каноническое изложение обходов, MST, кратчайших путей и потоков.
• Diestel R. Graph Theory, 5th ed. — стандартный современный учебник чистой теории, легально доступен на diestel-graph-theory.com; Bondy, Murty. Graph Theory with Applications — классика, свободно доступна на сайте авторов.
• Skiena S. The Algorithm Design Manual, 3rd ed., главы 7–8 и «War Stories» — про то, как графовые модели вырастают из реальных задач.
• Tarjan R. «Depth-First Search and Linear Graph Algorithms», SIAM J. Computing, 1972 — первоисточник low-link и SCC; Chaitin G. «Register Allocation and Spilling via Graph Coloring», 1982 — раскраска в компиляторах.
• Chen L. et al. «Maximum Flow and Minimum-Cost Flow in Almost-Linear Time», 2022 — arxiv.org/abs/2203.00671.
• NetworkX — де-факто справочник по практическим графовым алгоритмам в Python, исходники читаемы как учебник; SciPy sparse.csgraph — быстрые реализации поверх CSR для больших графов.

Что дальше

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

Линейная алгебра: векторы, пространства, базисы и линейная независимость