Графы: моделирование, основы, ДАГ

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

← Вернуться к оглавлению
Alterna · глава 17
Графы: моделирование, основы, ДАГ
Модели и графы — фундамент для ОГЭ №4,9 и ЕГЭ №1.
Граф — самый мощный инструмент дискретной математики. Соцсети, карты, сборка проектов, нейросети — всё это графы. В этой главе — основы: вершины, рёбра, степени, матрица смежности. В главе 21 — углублённые алгоритмы (Дейкстра, A*).
ФГОС · 9 класс
ФОП · базовый
ОГЭ №4,9
ЕГЭ №1
17
Страницы главы
5 страниц с теорией, интерактивами и банком заданий.
17.1
Моделирование и информационные модели
Что такое модель. Виды моделей (материальные/информационные). Этапы моделирования.
17.2
Графы: основы
Вершины, рёбра, степени. Матрица смежности, список смежности.
Canvas-редактор графа
.
17.3
Подсчёт путей в ДАГ
ДАГ, топологическая сортировка, метод DP.
Симулятор
с пошаговой трассировкой dp[v].
17.4
Практикум
Банк 20 заданий: 10 ОГЭ + 10 ЕГЭ №1 с разборами. Фильтры, прогресс-индикатор.
17.5
Экзамен-полигон
Квест 800 XP + тест 10 мин + развёрнутая задача с эталоном.
🔗
Связи с другими главами
Глава 15
Логика: таблицы истинности, операции ∧, ∨, ¬. Эти операции — основа для анализа путей в графах.
Глава 16
Схемы: логические вентили, связи между элементами. Графы — способ представить эти связи.
Глава 18
Булева алгебра: законы Де Моргана, поглощения, склеивания. Эти законы — ключ к упрощению булевых формул на графах.
Глава 21
Продвинутые алгоритмы: Дейкстра, A*, Беллман-Форд, максимальный поток.
Глава 22
Деревья: связный граф без циклов. Остовные деревья, бинарные деревья решений.
Глава 23
Сети и потоки: задача максимального потока, транспортные задачи.
Глава 24
Игры и стратегии: графы состояний, поиск выигрышных путей в играх.