Граф. Весовая матрица, длина пути и количество путей в направленном ациклическом графе
Цели и задачи
- Цель по SMART: к концу урока научиться по изображению направленного ациклического графа составлять его весовую матрицу, находить длину заданного пути и вычислять количество путей между указанными вершинами методом последовательного суммирования.
- Сформировать представление о графе как модели объектов и связей между ними, а также о назначении весов рёбер.
- Научиться различать вершины, рёбра, путь, длину пути и весовую матрицу графа.
- Отработать алгоритм подсчёта количества путей в направленном ациклическом графе на типичных заданиях, близких к формату ОГЭ.
- Развивать точность записи, умение проверять результат и объяснять выбор алгоритма.
Планируемые результаты
Личностные
- Осознают практическую ценность графов для описания маршрутов, компьютерных сетей и зависимостей между задачами.
- Повышают уверенность при решении заданий, связанных с графами, и воспринимают ошибку как источник коррекции алгоритма.
- Проявляют ответственное отношение к точности вычислений и записи данных.
- Связывают изучаемый материал с возможностями профессионального самоопределения в сфере информационных технологий.
Метапредметные
- Извлекают информацию из схемы графа, таблицы и условия задачи.
- Планируют последовательность решения и контролируют промежуточные результаты.
- Сравнивают несколько маршрутов, анализируют структуру графа и обосновывают вывод.
- Сотрудничают в паре, формулируют вопросы и представляют решение с использованием математической и информатической терминологии.
Предметные
- Знать понятия «вершина», «ребро», «ориентированный граф», «вес ребра», «путь», «длина пути», «ациклический граф».
- Уметь составлять весовую матрицу по заданному взвешенному ориентированному графу.
- Уметь находить длину пути как сумму весов входящих в него рёбер.
- Уметь вычислять количество путей в направленном ациклическом графе последовательным суммированием количества способов попасть в вершину.
- Уметь проверять решение перебором маршрутов на небольшом графе и исправлять типичные ошибки.
Универсальные учебные действия (УУД)
Личностные УУД
- Определяют личный уровень готовности к заданиям ОГЭ по теме «Графы».
- Осознают значение алгоритмического мышления для решения практических и профессиональных задач.
- Формируют положительную установку на последовательную проверку результата.
- Оценивают собственный вклад в парную работу.
Регулятивные УУД
- Формулируют цель урока на основе проблемной ситуации.
- Планируют алгоритм составления матрицы и подсчёта путей.
- Сверяют промежуточные значения с условием и эталоном.
- Находят ошибку в решении, объясняют её причину и выполняют коррекцию.
Познавательные УУД
- Классифицируют элементы графа и устанавливают соответствие между схемой и матрицей.
- Моделируют граф с помощью таблицы и массива чисел.
- Анализируют направленность рёбер и отсутствие циклов.
- Применяют рекуррентное правило подсчёта количества путей.
Коммуникативные УУД
- Распределяют роли при решении задания в паре.
- Формулируют уточняющие вопросы о направлении ребра и его весе.
- Аргументируют ответ, используя термины «вершина», «путь», «вес».
- Сопоставляют решения и корректно сообщают об обнаруженной ошибке.
Подготовка учителя к уроку
- Подготовить презентацию или изображение трёх небольших ориентированных взвешенных графов: для мотивации, открытия правила и самостоятельной работы.
- Вывести на доску памятку: «матрица: строка — откуда, столбец — куда; нет ребра — 0», а также формулы $L(P)=w_1+w_2+...+w_k$ и $N(v)=\sum N(u)$ для всех предшественников $u$.
- Распечатать карточки с графами трёх уровней сложности: по одной карточке на каждого ученика и по одному эталону на пару.
- Подготовить лист самооценки с пунктами «составляю матрицу», «нахожу длину пути», «считаю количество путей».
- Подготовить отдельный слайд с заданием в стиле ОГЭ и слайд с пошаговым эталоном решения.
- Подготовить цветные маркеры или фишки для обозначения вершин и путей.
- Обеспечить проектор, компьютер и интерактивную доску либо распечатанную демонстрационную схему.
- Разместить на доске карточки терминов: «вершина», «ребро», «вес», «путь», «длина пути», «матрица».
Ход урока
Этап 1. Организационный момент и мотивация (3 мин)
Цель этапа: включить учащихся в учебную деятельность и показать практическую значимость графов.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель приветствует класс: "Здравствуйте, ребята. Проверьте, пожалуйста, наличие тетради, ручки и листа для самостоятельной работы. Сегодня мы будем решать задачи, похожие на задания ОГЭ, но сначала увидим, что графы встречаются не только в экзаменационных вариантах." | Проверяют готовность, открывают тетради, записывают дату. |
2 мин | Учитель показывает схему маршрутов доставки между пунктами и говорит: "Представьте, что компьютер строит маршрут доставки между складами. Как записать такую схему в таблице? Как узнать стоимость конкретного маршрута? А если нужно определить, сколько разных маршрутов существует? Сегодня мы найдём ответы на все три вопроса." | Рассматривают схему, предполагают: "Нужно указать пункты, направления и стоимость перехода"; формулируют возможные способы подсчёта маршрутов. |
Завершение этапа: учитель подводит итог: "Мы увидели, что граф позволяет описывать реальные связи и маршруты. Теперь вспомним его основные элементы и подготовим основу для нового алгоритма."
Этап 2. Актуализация знаний (5 мин)
Цель этапа: восстановить понятия графа и направленного ребра, необходимые для открытия нового знания.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель показывает граф из пяти вершин и обращается к классу: "Назовите элементы, которые вы видите. Чем отличается стрелка от обычной линии? Куда можно двигаться по стрелке A → B?" Учитель фиксирует ответы на доске. | Называют вершины и рёбра, отвечают: "По стрелке можно двигаться из A в B, но не обязательно обратно". |
3 мин | Учитель задаёт вопросы: "Что называется путём? Как определить длину пути, если рёбра имеют веса 4, 2 и 7? Почему в направленном графе важно читать стрелки?" | Формулируют: "Путь — последовательность соединённых рёбрами вершин"; вычисляют $4+2+7=13$; объясняют, что обратное направление может отсутствовать. |
Завершение этапа: учитель подводит итог: "Мы вспомнили, что путь зависит не только от набора вершин, но и от направления движения. Осталось научиться компактно записывать веса и считать все возможные пути."
Этап 3. Постановка проблемы и целеполагание (4 мин)
Цель этапа: выявить затруднение и совместно сформулировать цель урока.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель показывает граф с вершинами A, B, C, D и спрашивает: "Попробуйте перечислить данные о графе так, чтобы другой человек сразу понял, из какой вершины в какую ведёт ребро и каков его вес. Что неудобно при словесном описании?" | В парах обсуждают 1 минуту, называют трудность: "Словесное описание длинное, можно перепутать направление или вес". |
2 мин | Учитель задаёт проблемный вопрос: "Как представить граф в виде таблицы? Как найти длину пути и не пропустить ни одного маршрута? Сформулируйте цель урока одним предложением." | Формулируют цель: "Научиться составлять весовую матрицу, находить длину пути и считать количество путей"; записывают тему урока. |
Завершение этапа: учитель подводит итог: "Затруднение стало понятным: нам нужен точный табличный способ записи и последовательный алгоритм подсчёта. Сейчас мы сами откроем оба способа на конкретном графе."
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Этап 4. Открытие нового знания (10 мин)
Цель этапа: вывести правила построения весовой матрицы, вычисления длины пути и подсчёта количества путей.
Время | Действие учителя | Действие учеников |
|---|---|---|
4 мин | Учитель выводит граф: A → B с весом 3, A → C с весом 5, B → C с весом 2, B → D с весом 4, C → D с весом 1. "Посмотрите на таблицу. В строке указываем вершину, из которой выходим, в столбце — вершину, в которую приходим. Если ребра нет, ставим 0. Заполним матрицу вместе: из A в B записываем 3, из A в C — 5." | Заполняют заготовку матрицы и проговаривают: "Строка — откуда, столбец — куда"; получают строки A: 0, 3, 5, 0; B: 0, 0, 2, 4; C: 0, 0, 0, 1; D: 0, 0, 0, 0. |
3 мин | Учитель говорит: "Рассмотрим путь A–B–D. Его длина равна сумме весов рёбер. Запишите формулу и вычислите длину пути A–B–C–D." Учитель напоминает, что длина — это сумма весов, а не число вершин. | Записывают $L(P)=w_1+w_2+...+w_k$; вычисляют длину A–B–D: $3+4=7$, длину A–B–C–D: $3+2+1=6$. |
3 мин | Учитель показывает тот же граф без весов и объясняет: "Чтобы посчитать количество путей, начнём с исходной вершины A: способов попасть в A — 1. В B можно попасть одним способом из A, значит N(B)=1. В C можно прийти из A или B, поэтому N(C)=N(A)+N(B)=2. В D можно прийти из B или C: N(D)=1+2=3. Циклов нет, поэтому вершины можно обрабатывать слева направо." | Заполняют таблицу значений $N(A)=1$, $N(B)=1$, $N(C)=2$, $N(D)=3$; перечисляют пути: A–B–D, A–C–D, A–B–C–D. |
Запись в тетрадях
- Весовая матрица: строка показывает начальную вершину, столбец — конечную; в клетке записывается вес ребра, а при отсутствии ребра — 0.
- Длина пути равна сумме весов всех рёбер пути: $L(P)=w_1+w_2+...+w_k$.
- Для направленного ациклического графа количество путей считают по правилу $N(v)=\sum N(u)$, где $u$ — вершины, из которых есть ребро в $v$; для исходной вершины $N=1$.
Завершение этапа: учитель подводит итог: "Мы получили три инструмента: матрица описывает граф, сумма весов даёт длину пути, а суммирование способов попасть в вершину даёт количество путей. Теперь проверим алгоритм на коротком задании и проговорим каждый шаг."
Этап 5. Первичное закрепление и межпредметная связь (7 мин)
Цель этапа: применить новый алгоритм к модели, связанной с математикой, географией и транспортной логистикой.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель раздаёт парам карточку: "На карте четыре пункта P, Q, R, S. Дороги направлены P → Q с длиной 6, P → R с длиной 4, Q → R с длиной 3, Q → S с длиной 8, R → S с длиной 2. Найдите длину маршрута P–Q–R–S и число всех направленных маршрутов из P в S." Учитель напоминает приём «Подумай — обсуди в паре — поделись». | Сначала решают индивидуально 30 секунд, затем обсуждают в парах; вычисляют длину $6+3+2=11$; перечисляют маршруты P–Q–S, P–R–S, P–Q–R–S и получают 3. |
2 мин | Учитель связывает задачу с географией и математикой: "Такая схема может описывать движение по рекам, транспортные направления или этапы технологического процесса. Почему нельзя использовать дорогу в обратную сторону, если стрелка её не показывает?" | Объясняют: "Направление является частью условия, поэтому обратный маршрут не считается"; приводят пример односторонней дороги. |
2 мин | Учитель просит одну пару представить решение, а остальные применяют взаимопроверку «Две звезды и пожелание»: называют два верных шага и один вопрос или совет. | Представляют решение, сверяют направление рёбер, длину и список маршрутов; формулируют замечание: "Нужно явно проверить, что маршрут проходит только по стрелкам". |
Эталон решения
Маршрут $P-Q-R-S$ имеет длину $6+3+2=11$. Все пути из $P$ в $S$: $P-Q-S$, $P-R-S$, $P-Q-R-S$. Следовательно, количество путей равно $3$. При подсчёте по вершинам: $N(P)=1$, $N(Q)=1$, $N(R)=N(P)+N(Q)=2$, $N(S)=N(Q)+N(R)=3$.
Завершение этапа: учитель подводит итог: "Мы применили граф к маршрутам и убедились, что алгоритм работает независимо от предметной области. Теперь каждый самостоятельно решит задание в формате ОГЭ и покажет, какой шаг алгоритма уже выполняет уверенно."
Этап 6. Самостоятельная работа с самопроверкой (10 мин)
Цель этапа: проверить индивидуальное владение алгоритмами и снизить тревожность перед заданиями ОГЭ через работу по понятному чек-листу.
Время | Действие учителя | Действие учеников |
|---|---|---|
6 мин | Учитель раздаёт карточки трёх уровней. Базовое задание: "По графу с рёбрами A → B вес 2, A → C вес 7, B → C вес 4, B → D вес 5, C → D вес 1 составьте весовую матрицу и найдите длину пути A–B–C–D." Повышенное задание дополнительно просит найти количество путей A–D. Учитель напоминает: "Сначала выпишите вершины, затем заполните матрицу, после этого отдельно посчитайте длину и количество путей." | Индивидуально выполняют выбранный уровень; составляют матрицу, вычисляют $2+4+1=7$, находят три пути A–B–D, A–C–D, A–B–C–D. |
2 мин | Учитель выводит эталон: матрица строками A: 0,2,7,0; B: 0,0,4,5; C: 0,0,0,1; D: 0,0,0,0. "Проверьте не только ответ, но и каждую клетку: направление, вес, отсутствие ребра." | Сверяют решение построчно, отмечают ошибки цветным карандашом и исправляют их. |
2 мин | Учитель предлагает самооценку: "Поставьте знак + напротив действия, которое выполняете без помощи, знак ± — если нужна тренировка, знак ? — если остался вопрос." | Заполняют лист самооценки, формулируют личный затрудняющий шаг; при необходимости задают вопрос. |
Эталон решения
Матрица имеет вид: строки A, B, C, D; $A=(0,2,7,0)$, $B=(0,0,4,5)$, $C=(0,0,0,1)$, $D=(0,0,0,0)$. Длина пути $A-B-C-D$ равна $2+4+1=7$. Количество путей: $N(A)=1$, $N(B)=1$, $N(C)=2$, $N(D)=N(B)+N(C)=3$.
Завершение этапа: учитель подводит итог: "Самостоятельная работа показала, что задача становится простой, если не перескакивать через шаги. В конце проверим, какие признаки помогают отличить правильное решение от случайного ответа, и зафиксируем план дальнейшей тренировки."
Этап 7. Рефлексия и домашнее задание (6 мин)
Цель этапа: осмыслить способы действия, выявить затруднения и сообщить варианты домашней тренировки.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель проводит рефлексию «Светофор»: "Покажите зелёную карточку, если умеете составлять матрицу и считать пути; жёлтую — если нужен пример; красную — если алгоритм пока неясен. Одним предложением объясните свой выбор." | Поднимают карточки, формулируют: "Зелёный: могу проверить каждую клетку матрицы" или "Жёлтый: путаю входящие и исходящие вершины". |
2 мин | Учитель задаёт вопросы: "Что означает число в клетке весовой матрицы? Почему в исходной вершине ставим один способ? Зачем граф должен быть ациклическим при таком подсчёте?" | Отвечают: "Число — вес направленного ребра"; "в исходную вершину можно попасть одним начальным способом"; "цикл может привести к бесконечному или неоднозначному подсчёту". |
2 мин | Учитель сообщает домашнее задание и говорит: "Выберите уровень осознанно. Базовый уровень обязателен, повышенный и дополнительный помогут тем, кто хочет уверенно решать задания ОГЭ." | Записывают домашнее задание, отмечают выбранный уровень и задают уточняющие вопросы. |
Завершение этапа: учитель подводит итог: "Сегодня вы научились видеть в схеме граф, переводить его в весовую матрицу, складывать веса на пути и считать число маршрутов по предшествующим вершинам. Если где-то появилась ошибка, вернитесь к памятке и проверьте направление стрелок. На следующем уроке мы продолжим работу с алгоритмами обработки графов."
Критерии оценивания практической работы
- «5» — правильно составлена вся весовая матрица, без ошибок определены направления рёбер, верно найдена длина пути и указано количество всех путей с обоснованием.
- «4» — алгоритм выбран правильно, но допущена одна вычислительная или оформительская ошибка, не повлиявшая на основную логику решения.
- «3» — верно определены основные вершины и часть рёбер, однако допущены ошибки в матрице или пропущен один путь; решение содержит отдельные верные шаги.
- Ниже «3» — направление рёбер систематически не учитывается, матрица не соответствует графу, длина и количество путей не обоснованы.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Что означает число в клетке весовой матрицы и что записывается при отсутствии ребра? | Проверка понимания структуры матрицы и различения нулевого веса и отсутствия ребра. |
Как по графу найти длину пути? | Выявление осознания правила суммирования весов. |
Как вы определяли количество путей в конечной вершине? | Проверка понимания зависимости от предшествующих вершин. |
Какой шаг алгоритма оказался самым сложным и какую помощь нужно повторить? | Выявление индивидуальных точек затруднения и планирование коррекции. |
Завершающее слово учителя
"Сегодня мы увидели, что граф — это не просто рисунок со стрелками, а точная модель связей, которую можно представить матрицей и обработать по алгоритму. Мы научились складывать веса рёбер для нахождения длины пути и суммировать способы попасть в вершину для подсчёта маршрутов. Самая частая ошибка — перепутать строку и столбец или пройти против стрелки, поэтому всегда проверяйте направление. На следующем уроке мы продолжим анализ графов и потренируемся выбирать наиболее надёжный способ решения задания ОГЭ."
Домашнее задание
Уровень | Что задать | Зачем |
|---|---|---|
Базовый (обязательный) | Решить 3 задания: по небольшому ориентированному взвешенному графу составить весовую матрицу, найти длину двух заданных путей и определить количество путей между двумя вершинами в ациклическом графе. | Закрепляет базовые алгоритмы; при проверке обратить внимание на направление рёбер, нулевые элементы матрицы и полноту перечисления путей. |
Средний (повышающий) | Решить 4 задания в формате ОГЭ: два на чтение весовой матрицы и длину пути, два на подсчёт количества путей методом значений $N(v)$. Для каждого решения записать последовательность шагов. | Формирует устойчивый алгоритм и навыки самопроверки; проверить наличие обоснования, а не только числового ответа. |
Продвинутый (дополнительный) | Составить собственный направленный ациклический граф из 6 вершин с весами рёбер, подготовить его матрицу, указать два пути с разными длинами и вычислить количество путей из начальной вершины в конечную. | Развивает создание и моделирование; проверить отсутствие циклов, согласованность схемы и матрицы, правильность подсчёта маршрутов. |
Контрольные вопросы перед выходом: «Как определить, что ребро направлено из вершины A в вершину B? Что складывают при нахождении длины пути? Какое начальное значение используют для количества способов попасть в исходную вершину? Почему при подсчёте путей важно отсутствие циклов?»
