Графы: углубление (взвешенные, матрицы, SCC)

Содержание и основные понятия

← Вернуться к оглавлению
Alterna · глава 24 · страница 24.1
Графы: углубление (взвешенные, матрицы, SCC)
Весовая матрица, матрица достижимости, алгоритм Тарьяна для сильно связных компонент.
Глава 17 — введение в графы. Здесь — углубление для 11 класса: взвешенные графы, матрица достижимости, алгоритм Тарьяна. Готовит к ЕГЭ №1 и олимпиадам.
ФГОС · 11 кл.
ФОП · углубл.
ЕГЭ №1
олимпиадный
01
Весовая матрица
Для
взвешенного графа
весовая матрица 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).
0
1
2
3
4
Рис. Ориентированный ациклический граф (DAG) с 5 вершинами. Рёбра: 0→1, 0→2, 1→3, 2→3, 3→4.
Связь с ОГЭ
В ОГЭ №3 дают граф в виде таблицы расстояний или схемы. Нужно найти кратчайший путь между двумя вершинами. Матрица — один из способов задать граф.
02
Интерактив: построй весовую матрицу
Нажимай на рёбра SVG-графа, чтобы добавлять/убирать веса. Матрица обновляется автоматически.
0
1
2
3
4
Пример DAG: 5 вершин, рёбра 0→1, 0→2, 1→3, 2→3, 3→4
🔧
Конструктор матрицы
Клик по ребру — задать вес
03
Матрица достижимости
Матрица достижимости D
: D[i][j] = 1, если из вершины i можно дойти до j (возможно через промежуточные вершины), и 0 — иначе.
Как строить:
Берём матрицу смежности A.
Вычисляем транзитивное замыкание: D = A ∨ A² ∨ A³ ∨ … ∨ A
n
На практике — алгоритм Уоршелла-Флойда за
O(V³)
или BFS из каждой вершины за
O(V·(V+E))
.
Применение:
определить, какие вершины связаны, проверить связность графа, найти компоненты связности.
A
B
C
D
Граф для примера: 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⁴ (∨ = логическое ИЛИ):
Шаг 1 — 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)).
🔢
Флойд-Уоршелл: пошагово
04
Сильно связные компоненты (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.
A
B
C
D
E
F
Как работает Тарьян:
При обходе каждой вершине назначается
номер
(время входа) и
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
🔗
Алгоритм Тарьяна: поиск SCC
Результат для примера:
[A,B,C]
,
[D,E]
,
[F]
. Конденсация: каждая SCC сжимается в одну вершину → получается
ДАГ
.
Зачем это нужно?
Анализ зависимостей (библиотеки, пакеты)
Развёртывание систем (топсорт компонент)
Поиск циклов в ориентированных графах
ЕГЭ №1: задачи на анализ графов
05
Топологическая сортировка
Топологический порядок
— последовательность вершин, в которой все рёбра направлены слева направо. Возможен только в
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 — есть цикл!
📋
Kahn: пошаговая топологическая сортировка
06
Справочник формул
Весовая матрица
W[i][j] = вес ребра i→j
Если ребра нет → ∞ или 0
Достижимость
D = A ∨ A² ∨ … ∨ Aⁿ
O(V³) — Уоршелл-Флойд
SCC (Тарьян)
O(V+E), DFS + стек
Конденсация → ДАГ
Размер матрицы
V × V (для V вершин)
Память: O(V²)
07
Раскраска графа: составь расписание
Задача о раскраске
— назначить цвета (время) вершинам так, чтобы соседние вершины не были одного цвета. Минимальное число цветов =
хроматическое число
χ(G).
Практика: расписание экзаменов. Каждый экзамен — вершина, ребро — студент сдаёт оба предмета. Нельзя ставить конфликтующие экзамены в одно время.
📅
Graph Coloring: Экзамены
Кликни на вершину, чтобы выбрать цвет (время). Конфликты подсвечивают