Глава 17 — введение в графы. Здесь — углубление для 11 класса: взвешенные графы, матрица достижимости, алгоритм Тарьяна. Готовит к ЕГЭ №1 и олимпиадам.
Весовая матрица
Для взвешенного графа весовая матрица W — это таблица, где W[i][j] = вес ребра i→j. Если ребра нет, записываем ∞ (бесконечность) или 0 — зависит от задачи.
Для невзвешенного графа — булева матрица (0/1). Для мультиграфа — количество рёбер между вершинами.
Пример: 4 вершины с весами
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 5 | ∞ | 10 |
| B | ∞ | 0 | 3 | ∞ |
| C | ∞ | ∞ | 0 | 1 |
| D | ∞ | ∞ | ∞ | 0 |
∞ обозначает отсутствие ребра. Диагональ = 0 (расстояние до самой себя). Рёбра: A→B(5), A→D(10), B→C(3), C→D(1).
Рис. Ориентированный ациклический граф (DAG) с 5 вершинами. Рёбра: 0→1, 0→2, 1→3, 2→3, 3→4.
В ОГЭ №3 дают граф в виде таблицы расстояний или схемы. Нужно найти кратчайший путь между двумя вершинами. Матрица — один из способов задать граф.
Интерактив: построй весовую матрицу
Нажимай на рёбра SVG-графа, чтобы добавлять/убирать веса. Матрица обновляется автоматически.
Пример DAG: 5 вершин, рёбра 0→1, 0→2, 1→3, 2→3, 3→4
Матрица достижимости
Матрица достижимости D: D[i][j] = 1, если из вершины i можно дойти до j (возможно через промежуточные вершины), и 0 — иначе.
Как строить:
- Берём матрицу смежности A.
- Вычисляем транзитивное замыкание: D = A ∨ A² ∨ A³ ∨ … ∨ An
- На практике — алгоритм Уоршелла-Флойда за O(V³) или BFS из каждой вершины за O(V·(V+E)).
Применение: определить, какие вершины связаны, проверить связность графа, найти компоненты связности.
Граф для примера: A→B, B→C, C→D, A→D
Пример: граф из 4 вершин
Рёбра: A→B, B→C, C→D, A→D (напрямую). Матрица смежности A:
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 0 | 1 |
| B | 0 | 0 | 1 | 0 |
| C | 0 | 0 | 0 | 1 |
| D | 0 | 0 | 0 | 0 |
Пошаговое построение D = A ∨ A² ∨ A³ ∨ A⁴ (∨ = логическое ИЛИ):
A→B, A→D, B→C, C→D → единицы в соответствующих клетках
A¹ показывает: из A сразу в B и D, из B сразу в C, из C сразу в D
Шаг 2 — A² (пути длины 2):
A→B→C, A→D (нет), B→C→D, A→D→? нет исходящих из D
A²: A→C (через B), B→D (через C)
Шаг 3 — объединяем: D = A¹ ∨ A² ∨ …
Строим D: D[A][C]=1 (через B), D[B][D]=1 (через C)
Так как A→C→D (длина 3): ещё одно объединение даёт D[A][D]=1
Итог: D[A][B]=1, D[A][C]=1, D[A][D]=1 | D[B][C]=1, D[B][D]=1 | D[C][D]=1 | D[D][D]=1 (диагональ)
| A | B | C | D | |
|---|---|---|---|---|
| A | 1 | 1 | 1 | 1 |
| B | 0 | 1 | 1 | 1 |
| C | 0 | 0 | 1 | 1 |
| D | 0 | 0 | 0 | 1 |
Чтение: из A достижимы B, C, D; из B — C, D; из C — D; D достижима только из себя.
Реализация на Python: Флойд-Уоршелл
def floyd_warshall(adj):
# adj — матрица смежности, adj[i][j]=1 если есть ребро i→j
n = len(adj)
d = [row[:] for row in adj] # копируем A¹
for k in range(n): # промежуточная вершина
for i in range(n):
for j in range(n):
d[i][j] = d[i][j] or (d[i][k] and d[k][j])
return d # матрица достижимости
# Пример:
adj = [
[0,1,0,1], # A → B, D
[0,0,1,0], # B → C
[0,0,0,1], # C → D
[0,0,0,0] # D → никуда
]
D = floyd_warshall(adj)
# D[0][2]=1: из A можно попасть в C
print("Достижимость из A:", [j for j in range(4) if D[0][j]])
Сложность O(V³) — подходит для V ≤ 300–500. Для больших графов используй BFS из каждой вершины: O(V·(V+E)).
Сильно связные компоненты (SCC)
Сильно связная компонента (SCC) — максимальное подмножество вершин, в котором из любой вершины есть путь в любую другую (с учётом направления рёбер).
Ключевой факт: если «сжать» каждую SCC в одну вершину, получится ориентированный ациклический граф (DАГ) — это называется конденсация графа.
Сложность: O(V+E). Использует DFS + стек. Идея: находим «корневые» SCC — те, из которых нельзя выйти в ранее посещённую компоненту. Реализуется одним обходом DFS.
Пример: поиск SCC
Граф: A→B→C→A (цикл), D→E, E→D (цикл), C→F. Две SCC: {A,B,C} и {D,E}. Вершина F — отдельная SCC.
При обходе каждой вершине назначается номер (время входа) и lowlink (минимальный достижимый номер).
Вершина — корень SCC, если lowlink[v] = num[v].
При возврате из DFS все вершины стека до корня образуют одну SCC.
def tarjan_scc(n, adj):
num = [-1]*n; low = [0]*n; stack = []; on_stack = [False]*n
timer = [0]; result = []
def dfs(v):
num[v] = low[v] = timer[0]; timer[0] += 1
stack.append(v); on_stack[v] = True
for u in adj[v]:
if num[u] == -1:
dfs(u); low[v] = min(low[v], low[u])
elif on_stack[u]:
low[v] = min(low[v], num[u])
if low[v] == num[v]: # корень SCC
comp = []
while True:
w = stack.pop(); on_stack[w] = False
comp.append(w)
if w == v: break
result.append(comp)
for v in range(n):
if num[v] == -1: dfs(v)
return result # список SCC
Результат для примера: [A,B,C], [D,E], [F]. Конденсация: каждая SCC сжимается в одну вершину → получается ДАГ.
- Анализ зависимостей (библиотеки, пакеты)
- Развёртывание систем (топсорт компонент)
- Поиск циклов в ориентированных графах
- ЕГЭ №1: задачи на анализ графов
Топологическая сортировка
Топологический порядок — последовательность вершин, в которой все рёбра направлены слева направо. Возможен только в DAG (directed acyclic graph).
Алгоритм Кahn'а
- Посчитать in-degree (число входящих рёбер) для каждой вершины.
- Поместить в очередь все вершины с in-degree = 0.
- Повторять: извлечь вершину из очереди, добавить в результат, уменьшить in-degree её соседей. Если у соседа in-degree стало 0 — добавить его в очередь.
- Когда очередь пуста — порядок построен.
Сложность: O(V + E). Результат не единственен — любая вершина с in-degree 0 может быть следующей.
Зачем нужно:
- Порядок сборки проекта (Makefile)
- Планирование задач с зависимостями
- Разрешение формул в электронных таблицах
- Расписание курсов (prerequisites)
Пример: A→B означает "B зависит от A". Если есть цикл — топологический порядок невозможен.
from collections import deque
def topological_sort(n, adj):
in_deg = [0]*n
for v in range(n):
for u in adj[v]:
in_deg[u] += 1
q = deque([v for v in range(n) if in_deg[v]==0])
order = []
while q:
v = q.popleft()
order.append(v)
for u in adj[v]:
in_deg[u] -= 1
if in_deg[u]==0:
q.append(u)
return order # если len(order)!=n — есть цикл!
Справочник формул
W[i][j] = вес ребра i→j
Если ребра нет → ∞ или 0
D = A ∨ A² ∨ … ∨ Aⁿ
O(V³) — Уоршелл-Флойд
O(V+E), DFS + стек
Конденсация → ДАГ
V × V (для V вершин)
Память: O(V²)
Раскраска графа: составь расписание
Задача о раскраске — назначить цвета (время) вершинам так, чтобы соседние вершины не были одного цвета. Минимальное число цветов = хроматическое число χ(G).
Практика: расписание экзаменов. Каждый экзамен — вершина, ребро — студент сдаёт оба предмета. Нельзя ставить конфликтующие экзамены в одно время.
- Расписание — экзамены, занятия, дедлайны
- Регистровый allocation — распределение регистров в компиляторе
- Частотное планирование — Wi-Fi каналы, сотовые вышки
- Судоку — каждая цифра = цвет блока 3×3
Мини-тест: 5 вопросов
Проверь себя! 5 случайных вопросов из банка 50 заданий, 20 XP за каждый.