Пути в графе. Оптимальный маршрут и подсчёт путей

На небольшом графе обосновать путь минимального суммарного веса полным сравнением вариантов; в направленном ациклическом графе подсчитать все пути от заданного старта накоплением по предшественникам и проверить перечислением.

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

Для работы достаточно бумаги, ручки и памятки. Сохраняй первую попытку; исправления отмечай другим знаком.

Безопасное начало

Сухие руки, без напитков у техники. Провода и разъёмы не трогай, о неисправности сообщи учителю. Работай по правилам кабинета. Две полные минуты в середине урока — без экрана и заданий. Внешний ИИ, личные аккаунты и личные данные не требуются.

Что уже нужно знать

Вершины, дуги, направление и сумма весов из урока 009; сложение и сравнение натуральных чисел. Программирование и алгоритм Дейкстры не требуются.

S0. Допустимый путь содержит три дуги с весами 2, 1 и 4. Назови число дуг и суммарный вес. Какая величина нужна, если цель — наименьшая сумма весов?

Устная проба без отметки.

Два вопроса — два результата

Сначала задают старт, цель и критерий. Здесь оптимальный путь имеет минимальную сумму положительных весов; геометрическая длина рисунка и число рёбер не заменяют эту сумму. В небольшом графе перечисли все допустимые пути по стрелкам, проверь полноту по развилкам, вычисли суммы и сравни. Равные минимальные суммы возможны. Для подсчёта всех путей в направленном ациклическом графе не нужны веса: у выбранного старта метка 1, в каждую другую вершину приходит сумма меток непосредственных предшественников. Метка недостижимой вершины 0. Считай вершину только после всех её предшественников; в наших схемах порядок уже указан. Источник не имеет входящих дуг, сток — исходящих; в произвольном графе их может быть несколько. В выбранных задачах старт — указанный источник, цель — указанный сток. Пути разбиваются по последней дуге: каждая группа получается продолжением всех путей до её начала, группы не пересекаются. Поэтому количества складывают. Отсутствие циклов позволяет закончить такое накопление; циклические случаи этой схемой не решаем.

Вершины подписаны латиницей. Других дуг, кроме явно данных, нет. Для оптимизации все веса положительные; единицы условные. Подсчёт количества не зависит от этих весов. Все рисунки условные и не предназначены для измерения линейкой.

Концептуальная иллюстрация. Точные данные определены условиями, таблицами и схемами; предметы на рисунке не являются входными данными.

Личная проба

C1. Даны только дуги S→T (10), S→A (2), A→T (3). Других дуг нет. Найди все пути из S в T и их веса. Какой путь оптимален по минимальному суммарному весу? Объясни, почему одного ребра недостаточно для выбора.

Те же данные C1; сравниваются подписи весов, не длины линий.

Две минуты лично сравни два пути, затем две на сверку критерия. Памятка разрешена.

Проверить все маршруты, затем сравнить

Разобранная модель на U,V,W,X: только U→V (2), U→W (4), V→W (1), V→X (6), W→X (2). Все пути U→X: U→V→X весит 8; U→W→X весит 6; U→V→W→X весит 5. Из U выход в V или W, из V в W или X, из W только в X: список полный. Минимум 5 у трёхрёберного пути, хотя есть варианты по два ребра.

A1. Ориентированный ациклический граф имеет только дуги A→B (1), A→C (3), B→C (1), B→D (8), C→D (2). Перечисли все пути из A в D, вычисли каждый суммарный вес и найди минимальный. Покажи, почему список полный: отдельно разбери выходы из A, затем продолжения из B.

Сначала своя запись и основание, затем сверка.

Полная пауза

Две минуты без проекции, чтения, вычислений и обсуждения. Отведи взгляд и смени позу.

Сложить количества по последнему ребру

Разобранная модель: только M→N, M→P, N→Q, P→Q. Источник M, сток Q. В порядке M,N,P,Q метки 1,1,1,2. В Q входят два ребра, поэтому 1+1=2; пути M→N→Q и M→P→Q. Каждый оканчивается своей последней дугой. Не умножаем, не выбираем максимум и не прибавляем отдельно стартовую 1.

A2. В ациклическом графе вершины S, A, B, C, T и только дуги S→A, S→B, A→C, B→C, A→T, C→T. Веса для подсчёта не нужны. Найди источник (нет входящих дуг) и сток (нет исходящих). Считай пути от S в порядке S,A,B,C,T: у S начальная метка 1; в каждую другую вершину сложи метки всех её непосредственных предшественников. Запиши пять меток и все пути S→T для проверки.

Заготовка для своей записи:

Три минуты свои метки и перечисление, две на проверку последней дуги и полноты.

Концептуальная иллюстрация. Точные данные определены условиями, таблицами и схемами; предметы на рисунке не являются входными данными.

Своя таблица и независимая сверка

Для новой сети держи два столбца: количество всех путей до вершины и суммы отдельных полных путей. Сначала проверь предшественников и накопи количества в готовом порядке. Затем перечисли все пути до цели и для каждого сложи веса. Число строк перечня должно совпасть с меткой цели; минимум ищут среди сумм, не среди меток количества. Не копируй числа разобранной сети в новую.

B1. Собственная проверка двух вопросов. Вершины W, X, Y, Z, только дуги W→X (3), W→Y (6), X→Y (1), X→Z (7), Y→Z (2). Сначала самостоятельно заполни таблицу числа всех путей от W в порядке W,X,Y,Z: стартовая метка W=1, далее сумма по входящим дугам. Потом перечисли все пути W→Z и их веса, найди минимальный вес и соответствующий путь. Сверь количество перечисленных путей с меткой Z. Сначала своя запись, затем исправления другим знаком.

Заготовка для своей записи:

Шесть минут: 1 напомнить порядок, 4 личная таблица и три пути/суммы, 1 сверка. Не открывать ответы до своей записи.

Проверка вымышленного ответа ИИ

AI1. Вымышленный ИИ советует для B1: «Число всех путей равно минимальному весу. Выбери любой путь с наименьшим числом дуг и остальные не проверяй». Найди две ошибки и опровергни обе конкретными результатами B1.

Это заранее составленный учебный пример. Самостоятельно проверь конкретный шаг; обращение к сервису не требуется.

Помощь и резерв

• Выбирает меньше рёбер. Выпиши именно суммы весов и сравни критерий.
• Складывает веса для количества. Подпиши метку как число путей, проверь входящие дуги.
• Пропускает путь на развилке. Проверь каждый выход и каждое продолжение.
• Прибавляет стартовую единицу к ответу. Метка цели уже учитывает все продолжения старта.

D1. Резерв. В B1 измени только вес X→Z с 7 на 3. Дуги и их направления те же. Сколько теперь всех путей W→Z? Каковы минимальный вес и число путей с таким весом? Проверь все три суммы.

D1 — необязательный резерв на 3–4 минуты после основных попыток. При нехватке времени перенести. H1 и весь тест автоматически вместе не назначаются.

Индивидуальный итог

Четыре полные минуты лично. Условия заранее на бумаге. Памятка и разобранные модели разрешены; ключи и веб-разбор закрыты. Учитель не даёт учебных подсказок. Сбор после четырёх минут.

E1. В небольшой сети всего два допустимых пути от старта до цели. У первого веса рёбер 3 и 4, у второго 2, 2 и 1. Какой оптимален по сумме весов и чему равен минимум?

E2. В ациклическом графе в T входят только две дуги: из P и из Q. От выбранного старта до P есть 2 пути, до Q — 3. Сколько путей до T? Почему берём сумму?

E3. Из старта в цель есть четыре пути, минимальный суммарный вес равен 9. Назови число всех путей и минимальный вес. Можно ли только по этим данным сказать, сколько путей имеют минимальный вес?

Разбор после своей попытки

Показать ответ после выполнения

После исправления выбери один новый пример из самопроверки.

Файлы для собственной практики

• Точная схема C1

Точная схема C1 повторяет список трёх дуг. Все обязательные задачи решаются на бумаге; список дуг и порядок вершин напечатаны полностью.

Материалы и самопроверка

Презентация, самостоятельный план учителя, рабочий лист, выходной билет и бумажная самопроверка открываются отдельными карточками. DOCX можно смотреть на сайте и скачать. PDF для печати:

• Рабочий лист
• Выходной билет — два на А4
• Самопроверка на бумаге

Самопроверка на сайте: шесть вопросов с пояснениями, отдельно 6–8 минут. Бумажная версия с письменными основаниями и разбором — 8–12 минут. Все шесть новых письменных случаев — ещё 8–10 минут; выбирай прежде всего случай к своей ошибке. Эти модули не прибавляют к основным 45 минутам и не задаются целиком вместе с H1 автоматически. Пояснения и новые случаи для бумажного разбора есть в плане учителя.

Домашний перенос

H1. Дома 5–7 минут на бумаге. В ациклическом графе только дуги K→L (3), K→M (2), L→M (2), L→N (1), M→N (4). Запиши метки количества путей от K в порядке K,L,M,N. Перечисли все пути K→N, их веса, минимальный вес и оптимальный путь. Компьютер не требуется.

Полное условие и памятка есть на листе. Решение запиши в тетради. Достаточно 5–7 минут с сохранённой опорой.

Источники

ФРП информатики 7–9 классов, базовый уровень: содержание 9 класса, раздел 2 «Теоретические основы информатики», моделирование, печатные с. 40–41: оптимальный путь, источник/сток и вычисление количества путей в направленном ациклическом графе. Здесь час 010 авторского КТП 2026/2027; сложные программные алгоритмы не вводятся. Учебник школы не указан; номера параграфов не назначены.

• Федеральная рабочая программа информатики 7–9 классов, базовый уровень
• Информационно-методическое письмо по информатике на 2026/2027 год
• NIST DADS — кратчайший путь и выбор критерия
• NIST DADS — направленный ациклический граф
• NIST DADS — обработка DAG в порядке предшественников