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