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