Графы: основные понятия, степени и матрицы

Знакомимся с графами — универсальной моделью связей, без которой не обходится ни одна область программирования.

Граф — это пара (V, E), где V — множество вершин, а E — множество рёбер, то есть пар вершин, соединённых связью.

Зачем нужны графы

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

Из чего состоит граф

Граф — это вершины (точки, узлы) и рёбра (линии, связи между вершинами). Если ребро соединяет вершины u и v, говорят, что они смежны. Виды графов различают по свойствам рёбер:

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

Степень вершины и лемма о рукопожатиях

Степень вершины — число рёбер, выходящих из неё (в неориентированном графе). У вершины «человек» в графе дружбы степень — это число его друзей. Есть красивая и полезная теорема о степенях.

Лемма о рукопожатиях: сумма степеней всех вершин равна удвоенному числу рёбер: Σ степеней = 2·|E|. Почему? Каждое ребро соединяет две вершины и потому добавляет по единице к степени каждой из них — то есть вносит 2 в общую сумму. Отсюда мгновенное следствие: число вершин нечётной степени всегда чётно (нельзя, чтобы на вечеринке нечётное число людей сделали нечётное число рукопожатий). Название леммы как раз из этой задачи про рукопожатия.

Как хранят граф в коде

Есть два главных способа представления графа:

• Матрица смежности — таблица n×n, где в клетке (i, j) стоит 1, если есть ребро между i и j. Удобно проверять «есть ли ребро» за один шаг, но занимает n² памяти (плохо для разреженных графов).
• Список смежности — для каждой вершины список её соседей. Компактно для разреженных графов (мало рёбер), и именно так графы чаще всего хранят на практике.

Посмотрим оба представления и проверим лемму о рукопожатиях на Python.

# Список смежности: вершина -> список соседей
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B'],
    'D': ['B'],
}

# Степени вершин
degrees = {v: len(neighbors) for v, neighbors in graph.items()}
print("Степени вершин:", degrees)

# Подсчёт рёбер (каждое учтено дважды в списке смежности)
edges = set()
for v in graph:
    for u in graph[v]:
        edges.add(frozenset((u, v)))
print("Число рёбер |E|:", len(edges))

# Лемма о рукопожатиях: сумма степеней = 2|E|
print("Сумма степеней:", sum(degrees.values()))
print("2 * |E| =", 2 * len(edges))
print("Лемма о рукопожатиях выполнена:",
      sum(degrees.values()) == 2 * len(edges))

Вывод:

Степени вершин: {'A': 2, 'B': 3, 'C': 2, 'D': 1}
Число рёбер |E|: 4
Сумма степеней: 8
2 * |E| = 8
Лемма о рукопожатиях выполнена: True

Сумма степеней (8) ровно вдвое больше числа рёбер (4) — лемма подтвердилась. Обрати внимание: мы использовали frozenset для рёбер, чтобы ребро {A,B} и {B,A} считались одним (в неориентированном графе порядок концов не важен). Это типичный приём при работе с неориентированными рёбрами.

Несколько важных понятий

• Путь — последовательность вершин, где каждая следующая соединена ребром с предыдущей.
• Цикл — путь, который возвращается в начальную вершину.
• Петля — ребро из вершины в саму себя; кратные рёбра — несколько рёбер между одной парой. Граф без петель и кратных рёбер называют простым — обычно работают именно с такими.

Красивая задача на Дирихле: дружба и знакомства

Сила принципа Дирихле — в неожиданных применениях. Вот классическая задача: в любой компании из n ≥ 2 человек обязательно найдутся двое с одинаковым числом знакомых внутри этой компании. Доказательство — чистый Дирихле, и оно изящно.

У каждого человека число знакомых — от 0 до n−1 (можно не знать никого или знать всех остальных). Это n возможных значений на n человек — вроде бы Дирихле не срабатывает (предметов не больше ящиков). Но есть тонкость: значения 0 и n−1 не могут встретиться одновременно. Если кто-то знает всех (n−1), то ни у кого не может быть 0 знакомых — ведь этого «всезнайку» знают все. Значит, реально доступных значений только n−1, а людей n. Теперь предметов (людей) больше ящиков (значений) — и по Дирихле двое попадают в один «ящик», то есть имеют одинаковое число знакомых.

Обрати внимание на ключевой ход: мы не просто посчитали ящики, а заметили скрытое ограничение, которое уменьшило их число. В этом и состоит мастерство задач на Дирихле — правильно выбрать и сосчитать ящики.

Матрица смежности: степени одним взглядом

Посмотрим на второе представление — матрицу смежности. Это таблица из нулей и единиц: в клетке (i, j) стоит 1, если между вершинами i и j есть ребро. У неё есть приятное свойство: степень вершины — это просто сумма её строки. Для неориентированного графа матрица симметрична относительно диагонали.

# Матрица смежности графа из 4 вершин (0..3)
adj = [
    [0, 1, 1, 0],
    [1, 0, 1, 0],
    [1, 1, 0, 1],
    [0, 0, 1, 0],
]
for i, row in enumerate(adj):
    print(f"Вершина {i}: степень {sum(row)}")

print("Сумма степеней:", sum(sum(row) for row in adj))
print("2 * число рёбер: рёбер =",
      sum(sum(row) for row in adj) // 2)

Вывод:

Вершина 0: степень 2
Вершина 1: степень 2
Вершина 2: степень 3
Вершина 3: степень 1
Сумма степеней: 8
2 * число рёбер: рёбер = 4

Матрица особенно удобна для плотных графов и для алгебраических трюков: например, если возвести матрицу смежности в степень k, элемент (i, j) покажет число путей длины k между вершинами i и j. Так теория графов смыкается с линейной алгеброй — связь, которую активно используют в анализе сетей и ранжировании страниц.

Типичные ошибки

• Путать ориентированный и неориентированный граф. В орграфе ребро A→B не означает B→A. Для подписок и ссылок направление критично.
• Считать ребро дважды. В списке смежности неориентированное ребро записано у обеих вершин — при подсчёте рёбер это надо учитывать (делить на 2 или использовать множество).
• Забывать лемму о рукопожатиях. Если кто-то утверждает, что в графе нечётное число вершин нечётной степени — это ошибка, такого не бывает.

Итог

• Граф = вершины + рёбра; бывает ориентированным, взвешенным, полным.
• Степень вершины — число её рёбер; лемма о рукопожатиях: Σ степеней = 2·|E|.
• Число вершин нечётной степени всегда чётно.
• Хранят граф матрицей смежности (быстрый доступ, n² памяти) или списком смежности (компактно).