Графы: углублённый уровень (взвешенные, MST, SCC)

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

← Вернуться к оглавлению
Alterna · глава 24
Графы: углублённый уровень (взвешенные, MST, SCC)
Дейкстра, A*, MST, SCC — для 11 класса и олимпиад.
Глава 17 — базовые графы (степени, матрицы смежности, топсорт). Эта глава —
продвинутый уровень
: взвешенные графы, алгоритмы кратчайшего пути, MST, SCC, CPM. Эксклюзивные интерактивы: MST Game, Беллман-Форд визуализатор, планировщик проекта, раскраска графа.
ФГОС · 11 класс
ФОП · углубл.
ЕГЭ №1
олимпиадный уровень
Чем эта глава отличается от главы 17?
Глава 17
Глава 24
Неориентированные графы, степени
Взвешенные ориентированные графы
Матрица смежности (0/1)
Весовая матрица + матрица достижимости
DFS/BFS, связность
SCC (Тарьян), конденсация → DAG
Топсорт, DP на DAG
CPM, критический путь, резервы
Подсчёт путей (формула)
Алгоритмы кратчайшего пути
—
MST (Прим/Краскал), A*, Беллман-Форд
—
MST Game, раскраска графа
🌍
DAG в реальной жизни
Minecraft: крафт
Деревянные доски → верстак → инструменты → алмазные инструменты. Нельзя красить стены до возведения фундамента. Каждый предмет зависит от предыдущих — типичный DAG.
Git: коммиты
Коммиты образуют DAG (directed acyclic graph). Merge commits создают параллельные ветки. Топологический порядок = порядок сборки/деплоя.
Школьная программа
Арифметика → алгебра → функции → производная. Нельзя изучать интегралы до понимания производных. Зависимости между темами — DAG.
Сборка программ (Makefile)
object.o зависит от source.cpp, final.exe зависит от всех object.o. Топологический порядок определяет правильный порядок компиляции.
Job scheduling
Задача A → задача B означает: A должна выполниться до B. Планировщик использует Kahn's algorithm для определения допустимого расписания.
Бюрократия / документооборот
Заявка → согласование → оплата. Нельзя оплатить без согласования. Каждый этап зависит от предыдущего — DAG.
24
Страницы главы
6 страниц с теорией, уникальными интерактивами и банком заданий.
24.1
Графы и весовая матрица
Взвешенные графы, матрица достижимости, SCC (Тарьяна).
Интерактив: раскраска графа (расписание экзаменов)
.
24.2
Кратчайшие пути
Дейкстра, A*, Беллман-Форд, MST (Прим/Краскал).
Интерактивы: Визуализатор Дейкстры, MST Game, Визуализатор Беллмана-Форда
.
24.3
Подсчёт путей в ДАГ
Топсорт (Кана), DP для числа путей, CPM.
Интерактив: CPM планировщик проекта (Gantt, резервы)
.
24.4
Практикум
Банк 20 заданий: 10 ОГЭ + 10 ЕГЭ №1 с разборами и математическими решениями.
24.5
Экзамен-полигон
Квест 800 XP + тест 10 мин + развёрнутая задача (Дейкстра + MST).
🎮
Уникальные интерактивы (не в главе 17)
🌲 MST Game
Построй MST по Краскалу: выбирай рёбра от лёгкого к тяжёлому. DSU показывает компоненты и циклы.
⚡ Беллман-Форд визуализатор
Пошаговая релаксация рёбер с поддержкой отрицательных весов и детекцией отрицательных циклов.
📋 CPM планировщик
Интерактивный Gantt-график: меняй длительности задач, смотри как меняется критический путь и резервы.
📅 Раскраска графа
Составь расписание экзаменов: вершины = экзамены, рёбра = конфликты студентов. Найди минимальное число слотов.
🔗
Связи
Глава 23
Моделирование — предыдущая глава. Графы используются для моделирования сетей и систем.
Глава 17
Базовые графы: степени, DFS/BFS, связность, топсорт. Основа для этой главы.
Глава 25
Деревья — частный случай графов (V-1 рёбер, связность, отсутствие циклов).
Глава 19
Деревья игры: тоже графы (minimax как DP на DAG).