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