Степень (валентность) вершины. Путь в графе. Цепи и циклы
Цели и задачи
- Цель: Сформировать понятия степени вершины, пути, цепи и цикла в графе, а также доказать и научиться применять лемму о рукопожатиях.
- Образовательная задача: Научить вычислять степени вершин, определять виды путей в графе и проверять возможность существования графа с заданными степенями.
- Развивающая задача: Развивать логическое мышление через анализ структурных связей и моделирование реальных систем с помощью теории графов.
- Воспитательная задача: Формировать культуру доказательного рассуждения и интерес к применению математики в современных ИТ-технологиях и социологии.
- Методическая задача: Использовать ИКТ-инструменты для визуализации графов и поиска кратчайших путей.
Планируемые результаты
Личностные
- Готовность к осознанному выбору дальнейшей образовательной траектории в области ИТ или анализа данных.
- Критичность мышления при анализе информации, представленной в виде сетевых структур.
- Умение аргументированно отстаивать свою точку зрения в процессе группового обсуждения гипотез.
- Понимание значимости математического моделирования для решения глобальных транспортных и логистических задач.
Метапредметные
- Умение создавать и преобразовывать знаково-символические модели (графы) для решения практических задач.
- Навык анализа сложных систем через выделение их компонентов и связей между ними.
- Способность самостоятельно планировать пути достижения целей при решении исследовательских задач.
- Владение навыками смыслового чтения технической и математической терминологии.
Предметные
- Знать определения степени вершины, изолированной и висячей вершин, пути, цепи, цикла.
- Уметь формулировать и применять лемму о рукопожатиях (сумма степеней вершин равна удвоенному количеству ребер).
- Уметь находить в графах простые цепи и простые циклы.
- Владеть навыком построения графа по заданному набору степеней его вершин.
Универсальные учебные действия (УУД)
Личностные УУД
- Формирование навыков самоанализа при выполнении самостоятельной работы.
- Развитие познавательного интереса к дискретной математике как основе программирования.
Регулятивные УУД
- Умение определять последовательность промежуточных целей с учетом конечного результата.
- Осуществление самоконтроля и коррекции действий при построении контрпримеров к ложным утверждениям.
Познавательные УУД
- Поиск и выделение необходимой информации в тексте определений.
- Установление причинно-следственных связей между четностью суммы степеней и количеством нечетных вершин.
Коммуникативные УУД
- Умение работать в парах, распределяя обязанности при поиске путей в сложных графах.
- Использование адекватных языковых средств для выражения своих мыслей в математическом дискурсе.
Подготовка учителя к уроку
- Распечатать рабочие листы с изображениями графов для анализа (по 1 шт. на каждого ученика).
- Подготовить интерактивную презентацию с визуализацией алгоритмов обхода графа.
- Настроить доступ к онлайн-конструктору графов (или аналогичному ПО для интерактивной доски).
- Подготовить карточки с наборами чисел (степеней вершин) для игры «Существует ли такой граф?».
- Проверить работоспособность проектора и интернет-соединения для демонстрации межпредметных связей (социальные графы).
Ход урока
Этап 1. Мотивация и самоопределение (3 мин)
Цель этапа: актуализировать интерес к теме через современные социальные и технологические контексты.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | "Здравствуйте, одиннадцатиклассники! Сегодня мы продолжаем погружение в теорию графов. Посмотрите на экран. Перед вами визуализация связей в социальной сети. Каждая точка — это человек, каждая линия — дружба. Почему некоторые точки кажутся огромными и яркими, а другие почти незаметны? Как математически описать 'популярность' узла? И как алгоритм находит путь от вас к знаменитости всего за 6 рукопожатий? Сегодня мы узнаем, как эти вопросы решаются с помощью понятий степени вершины и путей." | Слушают учителя, рассматривают изображение на слайде. Высказывают предположения: "Яркие точки — те, у кого много друзей", "Популярность — это количество связей". Записывают дату и тему урока в тетради. |
Завершение этапа: учитель подводит итог: "Ваши догадки верны. Количество связей в математике называется степенью вершины. Давайте разберемся с этим понятием официально."
Этап 2. Актуализация знаний и фиксация затруднения (5 мин)
Цель этапа: повторить базовые элементы графа и столкнуться с проблемой подсчета связей.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | "На прошлом уроке мы узнали, что такое граф, вершины и ребра. Нарисуйте в тетради произвольный граф с 5 вершинами и 6 ребрами. Теперь попробуйте посчитать, сколько ребер выходит из каждой вершины. Запишите эти числа рядом с вершинами." | Рисуют граф в тетрадях, выполняют подсчет. Подписывают числа (например, 2, 3, 1, 4, 2). |
3 мин | "А теперь вопрос на засыпку: может ли существовать граф, у которого степени вершин равны 1, 2, 2, 3? Попробуйте его нарисовать быстро. Если не получается — почему? Есть ли какое-то правило, ограничивающее наши фантазии в рисовании графов?" | Пытаются нарисовать граф с заданными степенями. Сталкиваются с затруднением: одно ребро всегда остается «лишним» или его не хватает. Высказывают гипотезы о четности. |
Завершение этапа: учитель подводит итог: "Мы наткнулись на важное правило. Чтобы его доказать, нам нужно строгое определение степени и одна фундаментальная лемма."
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Этап 3. Открытие нового знания: Степень вершины (12 мин)
Цель этапа: ввести понятие степени вершины и доказать лемму о рукопожатиях.
Время | Действие учителя | Действие учеников |
|---|---|---|
4 мин | "Запишем определение: Степенью (или валентностью) вершины называется количество ребер, инцидентных ей. Обозначается deg(v). Если степень равна 0 — вершина изолированная, если 1 — висячая. Давайте вместе выведем формулу. Если мы сложим степени всех вершин графа, что мы получим относительно количества ребер? Подсказка: каждое ребро имеет два конца." | Записывают определения в тетрадь. Анализируют свои рисунки из предыдущего этапа. Предлагают вариант: "Сумма степеней в два раза больше количества ребер". |
4 мин | "Верно! Это называется Лемма о рукопожатиях. Представьте: на вечеринке каждый, кто здоровается, участвует в одном рукопожатии двумя руками. Сумма 'пожатых рук' всегда четна. Запишем формулу: $\sum deg(v_i) = 2|E|$. Из этого следует следствие: в любом графе количество нечетных вершин (вершин с нечетной степенью) обязательно четно." | Записывают теорему и следствие. Проверяют свой неудачный пример из этапа 2: 1+2+2+3 = 8. Сумма четная, но нарисовать сложно. Учитель поясняет, что четность суммы — необходимое, но не всегда достаточное условие для простых графов. |
4 мин | "Используем ИКТ. Откройте на планшетах онлайн-редактор графов. Создайте граф, в котором 4 вершины имеют степень 3. Сколько ребер у вас получилось? Посмотрите, как меняется структура, когда вы добавляете всего одно ребро." | Работают с интерактивным инструментом. Экспериментируют с формой графа, убеждаются в истинности леммы (4*3 / 2 = 6 ребер). |
Запись в тетрадях
- deg(v) — степень вершины.
- Изолированная вершина: deg(v) = 0.
- Висячая вершина: deg(v) = 1.
- Лемма о рукопожатиях: Сумма степеней всех вершин графа равна удвоенному числу его ребер.
- Следствие: Число нечетных вершин графа всегда четно.
Завершение этапа: учитель подводит итог: "Теперь мы знаем, как устроены узлы. Но граф — это не только точки, это движение. Как пройти из пункта А в пункт Б?"
Этап 4. Открытие нового знания: Пути, цепи и циклы (8 мин)
Цель этапа: классифицировать способы перемещения по графу.
Время | Действие учителя | Действие учеников |
|---|---|---|
4 мин | "Представьте, что граф — это схема метро. Путь — это любая последовательность ребер, где конец одного совпадает с началом другого. Но в математике важна точность. Если все ребра в пути различны — это цепь. Если при этом еще и все вершины различны — это простая цепь. Как вы думаете, как называется путь, который возвращается в исходную точку?" | Слушают, проводят аналогии с транспортом. Отвечают: "Цикл", "Кольцевая линия". |
4 мин | "Именно. Цикл — это замкнутая цепь. Простой цикл — это цикл, в котором не повторяются вершины (кроме первой и последней). Посмотрите на схему на доске [учитель рисует сложный граф]. Найдите в нем простую цепь длиной 4 и простой цикл длиной 3. Кто готов показать на доске?" | Изучают схему. Один ученик выходит к доске, цветным маркером выделяет простую цепь, другой — цикл. Остальные фиксируют примеры в тетрадях. |
Завершение этапа: учитель подводит итог: "Отлично. Мы научились различать 'прогулки' по графу. Теперь проверим, как это работает в реальных задачах."
Этап 5. Первичное закрепление и межпредметные связи (7 мин)
Цель этапа: применить знания к задачам из информатики и биологии.
Время | Действие учителя | Действие учеников |
|---|---|---|
4 мин | "Применим метод 'Think-Pair-Share'. Задача из области ИТ: Локальная сеть построена так, что каждый компьютер соединен ровно с тремя другими. Может ли в такой сети быть 15 компьютеров? Обсудите в парах 1 минуту, используя лемму о рукопожатиях." | Обсуждают в парах. Выполняют расчет: 15 * 3 = 45. Сумма степеней нечетная, что невозможно. Отвечают: "Нет, не может, так как сумма степеней должна быть четной". |
3 мин | "Межпредметная связь: Биология. Нейронная сеть мозга — это гигантский граф. Синапсы — это ребра. Ученые обнаружили, что 'интеллект' часто зависит не от количества нейронов, а от их степени связности. Как вы думаете, будет ли в такой сети много циклов или это скорее дерево (граф без циклов)?" | Дискутируют. Предполагают, что циклы нужны для памяти и обработки сигналов (обратная связь). Приходят к выводу, что биологические сети очень сложны и содержат множество циклов. |
Завершение этапа: учитель подводит итог: "Как видите, графы — это язык, на котором говорит природа и техника. Пора проверить ваши силы в индивидуальном зачете."
Этап 6. Самостоятельная работа с самопроверкой (5 мин)
Цель этапа: индивидуальная диагностика усвоения материала.
Время | Действие учителя | Действие учеников |
|---|---|---|
4 мин | "На рабочих листах выполните два задания. 1. Дан граф (матрица смежности или рисунок), выпишите степени всех вершин и проверьте лемму о рукопожатиях. 2. Найдите кратчайшую простую цепь между вершинами А и К. На выполнение — 4 минуты." | Самостоятельно решают задачи на листах. Считают степени, суммируют их, ищут путь на схеме. |
1 мин | "Посмотрите на экран, там эталон решения. Оцените себя: если все верно — поставьте '+', если есть ошибка в подсчете — '!', если не поняли, как искать путь — '?'." | Сверяют свои ответы с эталоном. Проводят самооценку. |
Эталон решения
Задание 1: Вершины $V_1(3), V_2(2), V_3(3), V_4(4)$. Сумма: $3+2+3+4 = 12$. Ребер в графе 6. $12 = 2 \times 6$. Лемма верна. Задание 2: Кратчайшая цепь $A \to B \to D \to K$ (длина 3).
Этап 7. Рефлексия и домашнее задание (2 мин)
Цель этапа: осознание результатов деятельности и постановка задач на дом.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | "Наш урок подходит к концу. Мы сегодня 'пожали руки' математической логике. Запишите домашнее задание. Оно разделено по уровням сложности. И не забудьте заполнить 'Билет на выход' на краю стола." | Записывают домашнее задание. Заполняют краткие опросники (рефлексия). |
Критерии оценивания практической работы
- "5" — Ученик безошибочно определяет степени всех вершин, правильно применяет лемму о рукопожатиях для обоснования существования графа, находит кратчайшие простые цепи и циклы.
- "4" — Допущены незначительные вычислительные ошибки при подсчете суммы степеней, но алгоритм поиска путей и понимание определений верны.
- "3" — Ученик знает определения, может посчитать степень вершины на простом рисунке, но затрудняется в применении леммы о рукопожатиях и путает понятия простой цепи и пути.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Какое утверждение сегодня показалось самым удивительным? | Оценка эмоционального вовлечения и интереса к предмету. |
В чем разница между путем и простой цепью своими словами? | Проверка глубины понимания ключевых терминов урока. |
Где в твоей будущей профессии могут пригодиться графы? | Связь с профессиональным самоопределением (10 класс). |
Завершающее слово учителя
"Сегодня мы убедились, что за простыми точками и линиями скрываются строгие законы. Лемма о рукопожатиях — это только верхушка айсберга. На следующем уроке мы узнаем, как графы помогают находить выход из лабиринта и почему некоторые карты нельзя раскрасить меньше чем в 4 цвета. Вы отлично поработали, особенно в исследовательской части. До встречи в мире дискретной математики!"
Домашнее задание
Уровень | Что задать | Зачем |
|---|---|---|
Базовый | Решить 3 задачи на проверку возможности существования графа по набору степеней вершин (например: 2, 2, 3, 4, 4) и нарисовать их, если они существуют. | Закрепление леммы о рукопожатиях и навыка визуализации графов. |
Средний | На схеме дорог (граф с 8-10 вершинами) найти все простые циклы, проходящие через заданную 'столицу', и определить их длину. | Развитие навыка поиска структурных элементов (циклов) в сложных графах. |
Продвинутый | Мини-исследование: 'Граф моих контактов'. Построить фрагмент графа своих друзей в соцсети (5-7 узлов), вычислить их степени и найти 'центр' графа. | Применение теории графов к реальным данным, развитие навыков моделирования. |
