Графы. Основные понятия, виды графов и построение оптимального пути между вершинами
Цели и задачи
- Цель по SMART: к концу урока научиться распознавать основные элементы и виды графов, вычислять длину маршрута как сумму весов рёбер и выбирать оптимальный путь между двумя вершинами взвешенного графа в заданиях рабочего листа.
- Сформировать знания о вершинах, рёбрах, петлях, степени вершины, весах рёбер, простых, ориентированных и взвешенных графах.
- Научить применять алгоритм поиска оптимального пути: определить начальную и конечную вершины, перечислить маршруты, сложить веса рёбер и выбрать маршрут с наименьшей длиной.
- Развивать умение анализировать схему графа, выделять существенные свойства, проверять решение и аргументировать выбор маршрута.
- Воспитывать ответственность за точность вычислений, готовность к сотрудничеству и интерес к применению графов в навигации, логистике и информационных технологиях.
Планируемые результаты
Личностные
- Осознавать практическую ценность графовых моделей для навигации, транспортных сетей, компьютерных сетей и будущей профессиональной деятельности.
- Проявлять познавательный интерес к поиску наиболее эффективного решения задачи.
- Понимать значение точности, последовательности действий и проверки результата.
- Принимать учебную задачу и оценивать собственный уровень понимания темы.
Метапредметные
- Извлекать информацию из схемы графа, текста задания и числовых данных.
- Планировать решение задачи поиска оптимального пути и контролировать каждый шаг алгоритма.
- Сравнивать несколько маршрутов по вычисленным длинам и аргументированно выбирать лучший.
- Работать в паре, формулировать вопросы и объяснять способ решения с использованием терминов темы.
Предметные
- Знать понятия «вершина», «ребро», «петля», «степень вершины», «вес ребра», «маршрут», «длина пути» и «оптимальный путь».
- Уметь распознавать простой, ориентированный и взвешенный граф.
- Уметь вычислять длину маршрута как сумму весов его рёбер.
- Уметь выбирать кратчайший путь между двумя вершинами по результатам сравнения маршрутов.
- Уметь отличать действия алгоритма поиска пути от действий, не относящихся к решению задачи.
Универсальные учебные действия (УУД)
Личностные УУД
- Определяют личную значимость умения находить оптимальные решения в цифровой среде.
- Осознают связь изучаемой модели с реальными маршрутами и сетями.
- Проявляют самостоятельность при выборе способа проверки ответа.
- Оценивают собственную готовность использовать терминологию графов.
Регулятивные УУД
- Формулируют цель работы с заданиями рабочего листа.
- Планируют последовательность поиска кратчайшего пути.
- Сверяют вычисленную длину маршрута с эталоном и находят арифметические ошибки.
- Корректируют решение после обсуждения с партнёром.
- Оценивают результат по критериям точности и полноты объяснения.
Познавательные УУД
- Выделяют вершины, рёбра и веса на графовой схеме.
- Классифицируют графы по наличию направления, петель и повторяющихся рёбер.
- Моделируют маршрут последовательностью вершин и рёбер.
- Сравнивают числовые значения длин маршрутов.
- Применяют общий алгоритм к новым наборам весов.
Коммуникативные УУД
- Объясняют партнёру, почему конкретный объект является вершиной или ребром.
- Задают уточняющие вопросы о направлении и весе ребра.
- Согласуют общий ответ пары и приводят аргумент.
- Корректно принимают замечания и уточняют собственную формулировку.
Подготовка учителя к уроку
- Распечатать рабочий лист «Графы и деревья» по одному экземпляру на каждого ученика.
- Подготовить карточки с изображениями простого, ориентированного и взвешенного графов — по одной на пару.
- Вывести на доску схему: «вершина — ребро — вес ребра — маршрут — длина маршрута — оптимальный путь».
- Подготовить слайд с алгоритмом: определить начало и конец → перечислить маршруты → сложить веса → сравнить суммы → выбрать минимум.
- Подготовить маркеры трёх цветов для обозначения вершин, рёбер и выбранного маршрута.
- Распечатать карточки для взаимопроверки с ответами к заданиям №2, №5, №7, №10, №12 и №15 — по одной на пару.
- Подготовить таймер на 3 минуты для самостоятельной работы и рефлексии.
- Оборудование: компьютер, проектор или интерактивная доска, доска и маркеры.
- Заранее отметить на рабочем листе задания для урока: №1–2, №4–7, №9–12, №14–15; задания со схемами №3, №8 и №13 разобрать по материалу, который учитель выведет на экран.
Ход урока
Этап 1. Организационный момент и мотивация (3 мин)
Цель этапа: включить учеников в учебную деятельность и показать практическую проблему выбора оптимального маршрута.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель приветствует класс и показывает на экране схему нескольких городов, соединённых дорогами, у которых указана длина. «Представьте, что вы строите навигатор. Пользователь задал начальный и конечный город. Достаточно ли просто увидеть, что города соединены дорогами? Что ещё нужно узнать, чтобы предложить ему лучший маршрут?» | Рассматривают схему, формулируют проблему: «Нужно сравнить длины маршрутов и выбрать самый короткий». Записывают дату и тему урока. |
2 мин | Учитель объявляет приём «Проблемный вопрос»: «Сегодня мы будем работать не с реальной картой, а с универсальной моделью сети. Как обозначить города и дороги так, чтобы компьютер мог выполнять такие сравнения? Какие термины потребуются?» Учитель фиксирует предположения на доске и сообщает, что ответы будут проверены заданиями рабочего листа. | Высказывают предположения: «точки можно назвать вершинами», «соединения — рёбрами», «числа на рёбрах показывают расстояние». Формулируют ожидаемый результат урока. |
Завершение этапа: учитель подводит итог: «Мы увидели практическую задачу: среди нескольких маршрутов нужно выбрать лучший. Для этого сначала восстановим язык графов, а затем построим понятный алгоритм сравнения маршрутов».
Этап 2. Актуализация знаний. Основные элементы графа (6 мин)
Цель этапа: актуализировать термины «вершина», «ребро», «степень вершины», «маршрут» и связать их с заданиями рабочего листа.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель предлагает выполнить задания №1 и №2. «В задании №1 Алексей обозначил города и станции точками. Как называется отдельная точка графа? В задании №2 восстановите определение: граф состоит из чего, а соединяющая элементы линия называется как?» Учитель просит назвать ответы полными предложениями. | Индивидуально заполняют задания №1–2. Отвечают: «Отдельная точка называется вершиной». Восстанавливают: «Граф состоит из вершин и рёбер, а соединяющая их линия называется ребром». |
2 мин | Учитель показывает граф из пяти точек и нескольких соединений. «Посмотрите на схему. Назовите вершины, рёбра и один возможный маршрут. Сколько рёбер инцидентно вершине, отмеченной цветом? Это число называется степенью вершины». | Показывают на схеме вершины и рёбра, называют маршрут последовательностью вершин. Считают рёбра у выделенной вершины и формулируют: «Степень вершины — количество рёбер, инцидентных этой вершине». |
2 мин | Учитель организует «Подумай — обсуди в паре — поделись». «В задании №4 найдите лишний термин: вершина, ребро, степень вершины, абзац. Объясните не только ответ, но и критерий выбора». | Сначала выбирают ответ индивидуально, затем обсуждают в паре. Формулируют: «Абзац — лишний термин, потому что остальные обозначают элементы или характеристики графа». |
Запись в тетрадях
Граф состоит из вершин и рёбер. Вершины изображают точками, рёбра — линиями, соединяющими вершины. Степень вершины — количество рёбер, инцидентных этой вершине.
Завершение этапа: учитель подводит итог: «Мы восстановили, из каких элементов состоит граф и как описывается вершина. Теперь выясним, какие свойства рёбер позволяют различать виды графов и вычислять длину маршрута».
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Этап 3. Постановка проблемы и целеполагание (4 мин)
Цель этапа: выявить необходимость классификации графов и точного алгоритма поиска оптимального пути.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель показывает три изображения: граф без повторяющихся рёбер и петель, граф с направленными стрелками и граф с числами на рёбрах. «Все схемы являются графами, но работать с ними нужно по-разному. Какое свойство вы заметили? Что изменится, если ребро имеет направление или число?» | Сравнивают изображения, называют различия: «В одном графе нет петель и повторяющихся рёбер; во втором рёбра направлены; в третьем рёбра имеют веса». |
2 мин | Учитель обращается к заданию №9: «Какое свойство не является обязательным для простого графа: наличие вершин и рёбер, отсутствие петель или обязательное направление каждого ребра?» Затем формулирует цель: «Сегодня нам нужно не просто назвать виды графов, а научиться использовать веса для выбора кратчайшего маршрута». | Выбирают «обязательное направление каждого ребра» и объясняют: «Простой граф не обязан быть ориентированным». Записывают цель: распознавать виды графов, вычислять длину пути и выбирать минимальный маршрут. |
Завершение этапа: учитель подводит итог: «Мы определили, какие признаки нужно замечать на схеме. Далее построим определения видов графов и проверим их на заданиях №7 и №9».
Этап 4. Открытие нового знания. Виды графов и длина пути (9 мин)
Цель этапа: вывести классификацию графов и алгоритм вычисления длины маршрута.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель демонстрирует карточки трёх графов. «В графе без повторяющихся рёбер и петель граф называют простым. Если рёбра имеют направление, граф называют ориентированным. Если рёбрам назначены числа, их называют весами, а граф — взвешенным. Заполните пропуски в задании №7 и объясните каждый выбор». | Заполняют №7: «простым», «ориентированным», «весами». Сопоставляют определения с изображениями. |
3 мин | Учитель записывает на доске: «Длина маршрута = сумма весов всех рёбер маршрута». «Рассмотрим задание №5. Не угадываем ответ по внешнему виду выражения, а складываем веса последовательно: $4+7$, $3+5+2$, $6+1+8+2$. Что показывает каждая сумма?» | Вычисляют: $4+7=11$, $3+5+2=10$, $6+1+8+2=17$. Формулируют: «Сумма показывает длину соответствующего маршрута». |
3 мин | Учитель показывает слайд с алгоритмом. «Первый шаг — назвать начальную и конечную вершины. Второй — выписать возможные маршруты. Третий — сложить веса рёбер каждого маршрута. Четвёртый — сравнить суммы. Пятый — выбрать маршрут с наименьшей длиной. В задании №14 найдите действие, которое не входит в алгоритм». | Записывают алгоритм. В задании №14 выбирают «изменить название вершины», объясняя: «Это не влияет на длину маршрута и не относится к поиску оптимального пути». |
Запись в тетрадях
Простой граф не имеет петель и повторяющихся рёбер. Ориентированный граф имеет рёбра с направлением. Вес ребра — число, назначенное ребру. Длина пути равна сумме весов его рёбер. Оптимальный путь — путь между двумя вершинами взвешенного графа с наименьшим суммарным весом.
Завершение этапа: учитель подводит итог: «Теперь у нас есть и термины, и рабочий алгоритм. Проверим его сначала вместе на коротких числовых примерах, а затем вы примените его самостоятельно».
Этап 5. Первичное закрепление. Сравнение маршрутов (7 мин)
Цель этапа: отработать вычисление длины маршрута и выбор меньшего значения с проговариванием алгоритма.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель разбирает задание №10. «Перед вами три маршрута с длинами $5+4$, $2+3+1$ и $7+2+5$. Сначала каждый посчитает суммы, затем в паре проверит вычисления. Не называйте оптимальный путь до того, как получите все три длины». | Вычисляют: $5+4=9$, $2+3+1=6$, $7+2+5=14$. Сравнивают значения и выбирают маршрут длиной 6. |
2 мин | Учитель задаёт вопрос по заданию №11: «Как называется путь между двумя вершинами взвешенного графа, имеющий наименьший суммарный вес? Чем слово “оптимальный” отличается от просто “допустимый”?» | Отвечают: «Оптимальный путь». Объясняют: «Допустимый путь соединяет вершины, а оптимальный среди допустимых имеет наименьшую длину». |
2 мин | Учитель просит восстановить определения из задания №12 и проговорить их по цепочке: «Путь начинается в начальной..., заканчивается в конечной..., сумма весов называется длиной...» | Заполняют: «вершине», «вершине», «пути». Один ученик проговаривает полное определение, остальные сверяют запись. |
Эталон решения
Для задания №10: 1) вычислить длины маршрутов: $5+4=9$, $2+3+1=6$, $7+2+5=14$; 2) сравнить числа 9, 6 и 14; 3) выбрать наименьшее значение 6; 4) сделать вывод: оптимальным является второй маршрут.
Завершение этапа: учитель подводит итог: «Мы убедились, что выбор маршрута всегда должен опираться на вычисленные суммы, а не на количество рёбер или зрительное впечатление от схемы. Теперь каждый выполнит блок заданий самостоятельно».
Этап 6. Самостоятельная работа с самопроверкой (10 мин)
Цель этапа: проверить самостоятельное применение понятий графа, видов графов и алгоритма поиска оптимального пути.
Время | Действие учителя | Действие учеников |
|---|---|---|
6 мин | Учитель раздаёт рабочие листы или предлагает продолжить работу с ними. «Выполните задания №6, №7, №9, №11, №12, №14 и №15. В №15 обязательно запишите промежуточные суммы, а не только меньшую длину. Если завершите раньше, объясните письменно, почему изменение названия вершины не меняет длину пути». Учитель устанавливает таймер и консультирует, не сообщая готовый ответ. | Индивидуально решают задания. Для №15 вычисляют длины: $4+3+2=9$, $6+1+1+2=10$, $3+2+4=9$ и выбирают меньшие значения в соответствующих сравнениях. Записывают определения и аргументы. |
2 мин | Учитель организует взаимопроверку по карточкам. «Обменяйтесь листами с соседом. Проверяйте не только итог, но и наличие правильных терминов, промежуточных сумм и выбора минимума. Ошибку обозначьте вопросительным знаком, а не исправляйте за автора». | Сверяют ответы по карточке, отмечают совпадения и ошибки, задают партнёру уточняющий вопрос по одному спорному пункту. |
2 мин | Учитель проводит приём «Светофор»: «Покажите зелёный цвет, если можете самостоятельно пройти весь алгоритм, жёлтый — если путаетесь в терминах или вычислениях, красный — если нужна пошаговая помощь». Для жёлтой группы повторяет схему алгоритма на доске. | Показывают цвет, фиксируют в листе самооценки пункт, который требует повторения: виды графов, степень вершины, сумма весов или выбор минимума. |
Завершение этапа: учитель подводит итог: «Самостоятельная работа показала, что алгоритм состоит из простых действий, но каждое из них важно. Осталось применить его к схеме и сформулировать общий вывод урока».
Этап 7. Применение к схеме и рефлексия (6 мин)
Цель этапа: перенести алгоритм с числовых выражений на графовую схему и осознать результат обучения.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель показывает схему из задания №3 с подписанными вершинами и рёбрами. «Назовите начальную и конечную вершины. Найдите два возможных маршрута, выпишите их последовательности и веса. Теперь сравните длины. Какой путь является оптимальным?» Учитель просит одного ученика выделить выбранный маршрут на экране. | Определяют вершины начала и конца, выписывают два маршрута, складывают веса их рёбер, сравнивают суммы. Объясняют: «Оптимален маршрут с меньшей суммой весов». Один ученик выделяет его цветом. |
3 мин | Учитель раздаёт стикеры для приёма «Билет на выход»: «Ответьте на три вопроса: что называют вершиной графа; как вычисляют длину пути; почему самый короткий по числу рёбер путь не всегда является оптимальным? Прикрепите стикер у выхода». | Письменно отвечают: «Вершина — отдельная точка графа»; «длина равна сумме весов рёбер»; «потому что одно ребро может иметь большой вес». |
Завершение этапа: учитель подводит итог: «Сегодня мы перешли от отдельных терминов к модели, которая позволяет принимать обоснованное решение. На следующем уроке мы рассмотрим алгоритмы поиска кратчайших путей на более сложных графах».
Критерии оценивания практической работы
- «5» — верно выполнены не менее 90% заданий рабочего листа, правильно использованы термины, в заданиях на маршруты записаны промежуточные суммы и аргументированно выбран минимальный путь.
- «4» — верно выполнены не менее 75% заданий, допущена одна содержательная ошибка в определении вида графа или вычислении длины маршрута, общий алгоритм применён правильно.
- «3» — верно выполнены не менее 55% заданий, ученик различает вершину и ребро, умеет складывать веса по образцу, но нуждается в подсказке при сравнении маршрутов.
- Ниже базового уровня — ученик не различает основные элементы графа или не может вычислить длину маршрута; требуется повторное выполнение заданий №1–2, №5 и №11–12 с опорой на схему.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Что называют вершиной, ребром и весом ребра? | Проверка освоения базовой терминологии графов. |
Какие шаги нужно выполнить, чтобы найти оптимальный путь? | Выявление понимания алгоритма действий. |
Какое задание рабочего листа оказалось самым сложным и почему? | Выявление точек затруднения и причин ошибок. |
Почему маршрут с меньшим количеством рёбер не обязательно является оптимальным? | Проверка понимания роли весов рёбер и осмысленного выбора пути. |
Завершающее слово учителя
«Сегодня мы научились описывать сеть с помощью графа: выделять вершины и рёбра, определять вид графа и находить степень вершины. Мы увидели, что длина маршрута определяется суммой весов рёбер, а оптимальным становится маршрут с наименьшей суммой. Типичная ошибка — выбрать путь по количеству рёбер, не выполнив вычисления. На следующем уроке мы продолжим работу с алгоритмами поиска путей и более сложными графовыми схемами».
Домашнее задание
Уровень | Что задать | Зачем |
|---|---|---|
Базовый (обязательный) | Повторить определения вершины, ребра, степени вершины, простого, ориентированного и взвешенного графа. Решить 4 задания: восстановить термины в определениях, вычислить длины трёх маршрутов и выбрать меньшую длину в двух парах выражений. | Закрепляет терминологию и алгоритм сложения весов; при проверке смотреть на правильность терминов и наличие промежуточных вычислений. |
Средний (повышающий) | Составить собственный взвешенный граф из 5 вершин и не менее 7 рёбер. Обозначить два маршрута между выбранными вершинами, вычислить их длины и указать оптимальный путь. | Формирует умение моделировать граф и применять алгоритм к самостоятельно созданной ситуации; проверить наличие подписей вершин, весов и обоснования выбора. |
Продвинутый (дополнительный) | Разработать задачу о маршрутах между пятью объектами: изобразить граф, задать веса рёбер, предложить не менее трёх маршрутов между начальной и конечной вершинами и доказать выбор оптимального маршрута. | Развивает исследовательское и алгоритмическое мышление; при проверке смотреть на связность схемы, корректность всех сумм и доказательность сравнения. |
Контрольные вопросы перед выходом из класса: «Что является вершиной графа? Как называется линия между вершинами? Что показывает вес ребра? Как вычислить длину маршрута? Как называется путь с наименьшим суммарным весом?»
