Обход графа (эйлеров путь). Представление об ориентированных графах
Цели и задачи
- Цель: научиться определять возможность построения эйлерова пути в графе на основе анализа степеней его вершин и познакомиться с понятием ориентированного графа.
- Образовательная задача: вывести эмпирическим путём критерий существования эйлерова пути (связь с чётностью степеней вершин).
- Развивающая задача: развивать логическое мышление и навыки исследовательской деятельности через анализ геометрических моделей.
- Воспитательная задача: формировать навыки конструктивного сотрудничества в парах и критического отношения к результатам своей деятельности.
Планируемые результаты
Личностные
- Формирование готовности к саморазвитию и самообразованию.
- Развитие находчивости и активности при решении математических задач.
- Критичность мышления, умение распознавать логически некорректные высказывания.
Метапредметные
- Познавательные: умение устанавливать причинно-следственные связи, строить логическое рассуждение и делать выводы на основе данных.
- Регулятивные: умение самостоятельно планировать пути достижения целей, осознанно выбирать наиболее эффективные способы решения задач.
- Коммуникативные: умение организовывать учебное сотрудничество с педагогом и сверстниками.
Предметные
- Знать определения эйлерова пути, ориентированного графа, дуги.
- Уметь находить степени вершин графа и определять их чётность.
- Владеть навыком проверки графа на «чертимость» одним росчерком без повторения рёбер.
Универсальные учебные действия (УУД)
Личностные УУД
- Формирование ответственного отношения к учению.
- Развитие когнитивного интереса к истории математики (задача о Кёнигсбергских мостах).
Регулятивные УУД
- Самоконтроль процесса выполнения исследовательского задания.
- Оценка правильности выполнения действий на уровне адекватной ретроспективной оценки.
Познавательные УУД
- Анализ объектов с целью выделения признаков (чётность вершин).
- Выдвижение гипотез и их обоснование.
Коммуникативные УУД
- Умение работать в паре: распределение обязанностей, обсуждение промежуточных результатов.
- Аргументация своей позиции при представлении выводов классу.
Подготовка учителя к уроку
- Распечатать рабочие листы для исследования (6 графов для проверки) — 15 экземпляров (на каждую парту).
- Подготовить презентацию со схемой Кёнигсбергских мостов и примерами ориентированных графов (схема метро, одностороннее движение).
- Подготовить цветные маркеры для работы у доски.
- Учебник «Вероятность и статистика» 7 класс (под ред. Высоцкого/Ященко), открыть на параграфе «Графы».
- Оборудование: мультимедийный проектор, компьютер, интерактивная доска.
Ход урока
Этап 1. Мотивация и постановка проблемы (4 мин)
Цель этапа: заинтересовать учащихся исторической задачей и создать ситуацию интеллектуального затруднения.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | «Здравствуйте! Сегодня мы начнём с легенды. В XVIII веке в городе Кёнигсберге было 7 мостов через реку Преголя. Жители спорили: можно ли обойти все семь мостов, пройдя по каждому ровно один раз и вернувшись в начало? Посмотрите на экран (Слайд 1). Попробуйте мысленно проложить такой маршрут. Великий Леонард Эйлер в 1736 году доказал, что это невозможно. Почему? Сегодня мы это выясним». | Слушают учителя, рассматривают схему мостов на экране, пытаются пальцем в воздухе или на черновике проложить маршрут, убеждаются в сложности задачи. |
2 мин | «Давайте упростим задачу. На ваших столах лежат карточки №1 с пятью фигурами. Задание: попробуйте обвести каждую из них, не отрывая руки от бумаги и не проводя по одной линии дважды. Отметьте те, которые удалось нарисовать». | Индивидуально пробуют обводить фигуры на карточках. Фиксируют результаты: какие фигуры «чертятся», а какие — нет. |
Завершение этапа: учитель подводит итог: «Итак, одни фигуры рисуются легко, а другие — никак не поддаются. Значит, есть какой-то секрет, скрытый в структуре этих графов. Давайте его раскроем!»
Этап 2. Актуализация знаний (5 мин)
Цель этапа: повторить базовые понятия теории графов, необходимые для исследования.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | «Прежде чем искать секрет, вспомним термины. Что мы называем графом? Что такое вершины и рёбра? И самое важное для нас сегодня — что такое степень вершины? Нарисуйте в тетради произвольную вершину и проведите из неё 3 ребра. Чему равна её степень?» | Отвечают: «Граф — это совокупность вершин и связывающих их рёбер». «Степень вершины — это количество рёбер, выходящих из неё». Рисуют вершину, подписывают: «Степень = 3». |
2 мин | «Давайте введём понятия: чётная вершина и нечётная вершина. Как вы думаете, какие вершины мы так назовём? Посмотрите на свои фигуры на карточке №1 и подпишите степени всех их вершин». | Предполагают: «Если степень — чётное число, то вершина чётная, если нечётное — нечётная». Работают с карточкой, подписывая числа (степени) у каждой точки пересечения линий. |
Завершение этапа: учитель подводит итог: «Теперь у нас есть инструмент для анализа — степени вершин. Пора переходить к исследованию».
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Этап 3. Исследовательская работа в парах (12 мин)
Цель этапа: путем анализа данных вывести критерий существования эйлерова пути.
Время | Действие учителя | Действие учеников |
|---|---|---|
8 мин | «Работаем в парах. Заполните таблицу в рабочем листе №2. Для каждой фигуры укажите: 1) Удалось ли обвести? 2) Сколько в ней нечётных вершин? 3) Сколько в ней чётных вершин? Попробуйте найти закономерность: при каком количестве нечётных вершин граф можно нарисовать одним росчерком?» | Обсуждают в парах, считают степени вершин. Заполняют таблицу. Замечают, что если нечётных вершин 0 или 2 — фигура рисуется. Если больше (например, 4) — нет. |
4 мин | «Давайте обсудим результаты. Кто готов сформулировать гипотезу? Посмотрите на Слайд 2 с правильными ответами. Совпало ли ваше исследование с реальностью?» Учитель фиксирует на доске: «0 нечётных вершин — можно; 2 нечётные — можно; >2 — нельзя». | Представители пар высказываются: «Мы заметили, что если все вершины чётные, то можно начать в любом месте и вернуться. А если есть две нечётные, то в одной надо начать, а в другой закончить». Сверяют свои таблицы с эталоном на экране. |
Запись в тетрадях
Эйлеров путь — это путь в графе, проходящий через каждое его ребро ровно один раз.
Критерий Эйлера:
1. Если все вершины графа чётные, эйлеров путь существует (и является циклом).
2. Если в графе ровно две нечётные вершины, эйлеров путь существует (начинается в одной нечётной, заканчивается в другой).
3. Если нечётных вершин больше двух — эйлерова пути нет.
Критерий Эйлера:
1. Если все вершины графа чётные, эйлеров путь существует (и является циклом).
2. Если в графе ровно две нечётные вершины, эйлеров путь существует (начинается в одной нечётной, заканчивается в другой).
3. Если нечётных вершин больше двух — эйлерова пути нет.
Завершение этапа: учитель подводит итог: «Поздравляю, вы сами открыли закон, который прославил Эйлера! Теперь вернёмся к мостам Кёнигсберга: посчитайте степени вершин на той схеме. Теперь вы понимаете, почему жители не могли их обойти?»
Этап 4. Представление об ориентированных графах (7 мин)
Цель этапа: ввести понятие направления связи в графах.
Время | Действие учителя | Действие учеников |
|---|---|---|
4 мин | «Иногда нам важно не просто наличие связи, но и её направление. Представьте карту дорог с односторонним движением. Как нам это показать на графе? (Слайд 3). Мы рисуем стрелки. Такой граф называется ориентированным, а его рёбра — дугами. Приведите примеры из жизни, где важны стрелки». | Слушают, делают наброски в тетради. Приводят примеры: «Схема пищевых цепочек в биологии», «Кто на кого подписан в соцсетях», «Схема движения автобусов», «Генеалогическое древо (от родителей к детям)». |
3 мин | «В ориентированном графе у вершины есть полустепень захода (сколько стрелок входит) и полустепень исхода (сколько выходит). Посмотрите на рисунок в учебнике на стр. 142. Найдите вершину с максимальной полустепенью исхода». | Открывают учебник, анализируют рисунок, считают стрелки, выходящие из узлов. Отвечают на вопрос учителя. |
Завершение этапа: учитель подводит итог: «Ориентированные графы — это основа программирования и логистики. Но сегодня мы сосредоточимся на практике обхода обычных графов».
Этап 5. Первичное закрепление и дифференцированная практика (8 мин)
Цель этапа: отработать навык применения критерия Эйлера на задачах разного уровня сложности.
Время | Действие учителя | Действие учеников |
|---|---|---|
8 мин | «Предлагаю вам задания на выбор. Уровень А (базовый): №456 из учебника — проверить 3 графа на эйлеровость. Уровень Б (средний): Нарисовать граф, у которого 4 вершины, и он имеет эйлеров путь, но не цикл. Уровень В (сложный): Задача о почтальоне: может ли он пройти по всем улицам района (дан граф), не проходя дважды по одной стороне, если улицы — это рёбра?» Учитель курсирует по классу, помогая тем, кто выбрал сложный уровень. | Выбирают задание по силам. Самостоятельно решают в тетрадях. Ученики уровня В обсуждают решение вполголоса. Те, кто закончил А, переходят к Б. |
Эталон решения (Уровень Б)
Для того чтобы граф имел эйлеров путь, но не цикл, у него должно быть ровно 2 нечётные вершины.
Пример: Вершины $V_1, V_2, V_3, V_4$. Рёбра: $(V_1, V_2), (V_2, V_3), (V_3, V_4)$.
Степени: $deg(V_1)=1, deg(V_2)=2, deg(V_3)=2, deg(V_4)=1$.
Две нечётные вершины (1 и 4) — условие выполнено.
Пример: Вершины $V_1, V_2, V_3, V_4$. Рёбра: $(V_1, V_2), (V_2, V_3), (V_3, V_4)$.
Степени: $deg(V_1)=1, deg(V_2)=2, deg(V_3)=2, deg(V_4)=1$.
Две нечётные вершины (1 и 4) — условие выполнено.
Завершение этапа: учитель подводит итог: «Вижу, что большинство справилось с базовым уровнем, а некоторые успешно решили задачу почтальона. Молодцы!»
Этап 6. Самостоятельная работа с самопроверкой (6 мин)
Цель этапа: индивидуальный контроль усвоения материала.
Время | Действие учителя | Действие учеников |
|---|---|---|
4 мин | «На экране (Слайд 4) три графа. Запишите в тетрадь только номера тех, которые можно начертить одним росчерком, и кратко обоснуйте (количество нечётных вершин)». | Выполняют работу самостоятельно. Считают степени, делают краткие записи: «№1 — да, т.к. 0 нечётных», «№2 — нет, т.к. 4 нечётных» и т.д. |
2 мин | «А теперь проверьте себя по эталону на обратной стороне доски. Поставьте себе плюс, если всё верно». | Сверяются с ответами, проводят самооценку. |
Этап 7. Рефлексия и домашнее задание (3 мин)
Цель этапа: осознание учащимися своей учебной деятельности, самооценка результатов.
Критерии оценивания практической работы
- «5» — верно определена возможность обхода для всех предложенных графов, правильно найдены степени вершин, решена задача повышенного уровня.
- «4» — верно определена возможность обхода, но допущены мелкие ошибки в подсчёте степеней в сложных графах.
- «3» — ученик понимает критерий (чётность), но ошибается в его применении или не может обосновать ответ.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Какое условие является ключевым для существования эйлерова пути? | Проверка усвоения главного теоретического факта урока. |
Что на уроке сегодня было для вас самым трудным? | Выявление индивидуальных затруднений для коррекции на следующем уроке. |
Где в реальной жизни вам может встретиться ориентированный граф? | Проверка понимания практической значимости темы. |
Завершающее слово учителя
«Сегодня мы с вами прошли путь от старинной загадки до серьезной математической теоремы. Вы доказали, что умеете быть исследователями. Помните, что графы — это не просто точки и линии, это язык, на котором общаются компьютеры и навигаторы. Если сегодня что-то не получилось — не беда, на следующем уроке мы закрепим эти навыки. Спасибо за работу!»
Домашнее задание
Уровень сложности | Задания | Описание |
|---|---|---|
Базовый (обязательный) | Параграф учебника, №458, 460 | Проверить графы на наличие эйлерова пути, выписать степени нечётных вершин. |
Средний (повышающий) | Творческое задание | Нарисовать свой «запутанный» граф-лабиринт, который можно пройти одним росчерком, и предложить другу его решить. |
Продвинутый (дополнительный) | Исследование | Найти информацию о «Гамильтоновых путях». Чем они отличаются от Эйлеровых? Привести пример. |
Контрольный вопрос перед выходом: «Может ли существовать эйлеров путь в графе с тремя нечётными вершинами?» (Ожидаемый ответ: «Нет, нечётных вершин всегда должно быть чётное количество, а для пути — 0 или 2»).