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