План урока на тему:

Графы: основные понятия и применение

Информатика9 класс65 разделов
Графы: основные понятия и применение

Информатика · 9 класс · Открытие нового · 45 мин

Граф. Весовая матрица, длина пути и подсчёт путей в направленном ациклическом графе

Цели и задачи

  • Цель по 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 вершин, назначить веса дугам, составить его весовую матрицу и задать другому ученику вопросы о длине двух путей и количестве всех путей.
Развивает моделирование и создание собственного задания; при проверке смотреть на отсутствие циклов, согласованность рисунка и матрицы, однозначность вопросов.
Контрольные вопросы перед выходом из класса: «Что записывается в строке и столбце весовой матрицы? Как вычислить длину пути? Почему количество путей в вершину складывается из количества путей в её предшественники? Назовите одну ошибку, которую необходимо проверить перед сдачей ответа».

Создайте уникальный план урока по своей теме

  • Любая тема, любой уровень
  • Структура по ФГОС
  • 100% уникальный план урока
  • Цели, ход урока, рефлексия
  • Экспорт в PDF и Word
  • Готово за 1 минуту

Другие темы по информатике для 9 класса

Построение таблиц истинностиПравила техники безопасности и правила поведения в компьютерном классеФишингПубличные аккаунтыПонятие об этапах разработки программ и приемах отладки программ4 задание ОГЭ: нахождение кратчайшего пути в графеГраф: вершина, ребро, путьДерево: корень, узел, лист, ребро, высота, поддерево; перебор вариантов с помощью дереваБаза данных. Разработка однотабличной базы данныхПонятие об электронных таблицах. Типы данных в ячейках; Встроенные функции: максимум, минимум, сумма, среднее арифметическое; Построение диаграмм: гистограмма, круговая, точечная; УсловныеМодель. Задачи, решаемые с помощью моделирования; Граф: вершина, ребро, путь; Ориентированные и неориентированные графы. Длина (вес) ребра; Весовая матрица графа. Поиск оптимального пути в графеСоставление алгоритмов и программ для управления исполнителем

Чем удобны планы уроков Нейрум

  • Готовый план, не набросокЦели, ход урока, планируемые результаты, рефлексия — всё по структуре ФГОС, открыли и пошли вести.
  • План урока или техкартаОдин материал — два формата экспорта в PDF. Скачали то, что нужно завучу.
  • Свой план урока за минутуНе нашли нужный? ИИ-конструктор напишет план урока по вашей теме, классу и типу урока.

Вопросы и ответы

Как скачать план урока «Граф: весовая матрица, длина пути и вычисление количества путей в направленном ациклическом графе»?

Зарегистрируйтесь бесплатно — материал сохранится в личном кабинете, откуда его можно скачать как план урока или технологическую карту.

Соответствует ли план урока ФГОС?

Да, структура урока — цели, ход урока, планируемые результаты — построена по ФГОС для 9 класса (информатике).

Можно ли изменить план под свой класс?

Да. После регистрации план урока открывается в конструкторе: этапы и содержание можно отредактировать или перегенерировать.