Графы и деревья: представление, свойства и применение
Цели и задачи
- Цель по SMART: к концу урока научиться распознавать графы и деревья, выделять вершины и рёбра, определять степень вершины, связность и наличие циклов, а также применять эти свойства при решении не менее двух практических задач.
- Сформировать представление о графе как модели объектов и связей между ними, познакомить с понятиями вершины, ребра, степени вершины, пути, цикла и связности.
- Научиться отличать дерево от произвольного графа по ключевым признакам и обосновывать свой вывод.
- Развивать алгоритмическое и логическое мышление через исследование моделей и поиск закономерностей.
- Воспитывать ответственность за точность построения моделей, готовность аргументировать решение и интерес к применению графов в программировании, сетях и анализе данных.
Планируемые результаты
Личностные
- Осознавать практическую значимость графовых моделей для будущей профессиональной деятельности в сфере информатики, программирования и анализа данных.
- Проявлять познавательную инициативу при исследовании свойств графов и деревьев.
- Понимать ценность точного описания связей и ответственности за корректность цифровой модели.
- Развивать готовность к самостоятельному выбору способа решения и оценке его обоснованности.
Метапредметные
- Извлекать информацию из схем, формулировок задач и таблиц смежности.
- Строить модель ситуации в виде графа и преобразовывать её между различными представлениями.
- Планировать последовательность решения, проверять результат по свойствам графа и корректировать ошибочные рассуждения.
- Аргументированно обсуждать гипотезы в паре или группе и представлять результат исследования.
- Применять логические операции сравнения, классификации и доказательства.
Предметные
- Знать определения графа, вершины, ребра, степени вершины, пути, цикла, связного графа и дерева.
- Уметь находить степень вершины, определять связность графа и обнаруживать цикл по его изображению.
- Уметь объяснять, почему дерево является связным графом без циклов.
- Уметь строить граф по описанию предметной области и представлять его списком рёбер или таблицей смежности.
- Владеть способом проверки утверждения о том, что связный граф с $n$ вершинами и $n-1$ рёбрами является деревом.
Универсальные учебные действия (УУД)
Личностные УУД
- Определяют личный интерес к применению графовых моделей в выбранной профессиональной области.
- Осмысливают необходимость точности и проверяемости алгоритмического рассуждения.
- Оценивают собственную готовность объяснить решение, а не только назвать ответ.
- Проявляют самостоятельность при выборе стратегии исследования.
Регулятивные УУД
- Совместно формулируют цель исследования свойств графа и дерева.
- Планируют порядок действий при проверке связности и наличия циклов.
- Осуществляют самопроверку по определениям и контрольным вопросам.
- Находят ошибку в построенной модели и предлагают способ её исправления.
- Оценивают достижение цели по результатам самостоятельной работы.
Познавательные УУД
- Выделяют существенные признаки графа и дерева.
- Сравнивают графы по числу вершин, рёбер, степени вершин и наличию циклов.
- Строят схемы, списки рёбер и таблицы смежности.
- Выдвигают и проверяют гипотезу о связи числа вершин и рёбер в дереве.
- Используют логическое доказательство и контрпример.
Коммуникативные УУД
- Распределяют роли в малой группе при исследовании графовой модели.
- Формулируют уточняющие вопросы и отвечают на них с использованием предметной терминологии.
- Аргументируют вывод о принадлежности графа к деревьям.
- Сопоставляют разные способы решения и корректно оценивают доводы одноклассников.
- Достигают общего решения при расхождении гипотез.
Подготовка учителя к уроку
- Подготовить презентацию с изображениями социальных связей, компьютерной сети, карты дорог и иерархии папок.
- Вывести на доску или экран рабочие определения: вершина, ребро, путь, цикл, связный граф, дерево.
- Распечатать карточки трёх уровней: распознавание свойств, построение модели, исследовательская задача — по одной карточке на каждого ученика.
- Подготовить по одному комплекту карточек для каждой группы из 3–4 человек с рисунками графов и таблицами списков рёбер.
- Распечатать лист самооценки и билет на выход — по одному экземпляру на каждого ученика.
- Подготовить маркеры, стикеры, листы А3 для групповых схем и магнитные обозначения вершин и рёбер.
- Проверить работу проектора или интерактивной доски; заранее открыть презентацию с графами без подписей.
- Разместить на доске шаблон таблицы: «Число вершин — Число рёбер — Есть цикл? — Связен ли граф? — Дерево?»
- Подготовить таймер на 2–4 минуты для исследовательских заданий.
Ход урока
Этап 1. Организационный момент и мотивация (4 мин)
Цель этапа: включить учащихся в исследовательскую деятельность и показать практическую значимость графов.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель приветствует класс и показывает на экране схему из точек и линий без подписей: «Посмотрите на изображение. Перед вами несколько объектов и связи между ними. Это могут быть станции метро, страницы сайта, компьютеры или люди. Как одним языком описать все такие ситуации? Не спешите называть термин: сначала предложите, что здесь является объектами, а что — связями». | Рассматривают схему, индивидуально формулируют гипотезы, затем обсуждают их с соседом. Предполагают: «Точки — это объекты, линии — отношения между ними», «Схему можно использовать для маршрутов и сетей». |
2 мин | Учитель объявляет приём «Проблемный вопрос»: «Как по рисунку понять, существует ли маршрут между двумя объектами, есть ли замкнутый путь и можно ли назвать такую структуру деревом? Сегодня мы не просто запомним определения, а исследуем признаки и проверим их на задачах». | Записывают тему, формулируют личную цель: «Научиться отличать дерево от графа и объяснять решение», «Находить путь, цикл и степень вершины». |
Завершение этапа: учитель подводит итог: «Мы увидели, что одна и та же модель описывает дороги, сети и иерархии. Теперь вспомним математический язык, который поможет нам точно анализировать такие схемы».
Этап 2. Актуализация знаний (6 мин)
Цель этапа: актуализировать навыки чтения схем, подсчёта объектов и проверки связности.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель раздаёт карточку с графом из пяти вершин и семи рёбер: «Работаем по приёму “Подумай — обсуди в паре — поделись”. Сначала самостоятельно назовите число вершин и рёбер. Затем найдите степень вершины A и запишите один путь из A в E. Через минуту сравните ответы в паре». | Подсчитывают вершины и рёбра, находят число рёбер, инцидентных вершине A, записывают путь, например «A–B–D–E», обсуждают различия в парах. |
3 мин | Учитель выводит на экран два утверждения: «Если между двумя вершинами есть линия, они соседние» и «Любой путь обязан начинаться и заканчиваться в одной вершине». Спрашивает: «Поднимите зелёную карточку, если утверждение верно, красную — если неверно. Обоснуйте второй ответ». | Показывают карточки, исправляют второе утверждение: «Путь может начинаться и заканчиваться в разных вершинах; замкнутый путь образует цикл». Называют степень выбранной вершины и проверяют её по рисунку. |
Завершение этапа: учитель подводит итог: «Мы умеем читать граф, считать вершины и рёбра, находить путь и отличать путь от цикла. Теперь выясним, каких признаков достаточно, чтобы назвать граф деревом».
Этап 3. Постановка проблемы и целеполагание (4 мин)
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Цель этапа: обнаружить затруднение при классификации графов и сформулировать план исследования.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель показывает три схемы: связный граф без циклов, связный граф с циклом и несвязный граф без циклов. «Все три изображения состоят из вершин и рёбер. Какое из них можно использовать для иерархии папок или структуры разделов сайта? Какой признак мешает двум другим быть деревьями? Запишите гипотезу, не сверяясь с определением». | Сравнивают схемы, формулируют гипотезы: «В дереве не должно быть циклов», «Все вершины должны быть соединены», «Одной связи может не хватать». |
2 мин | Учитель организует «Снежный ком»: «Объединитесь сначала в пары, затем по две пары. Согласуйте два обязательных признака дерева и план проверки. На доске зафиксируем только те признаки, которые группа сможет проверить по рисунку или списку рёбер». | Объединяют гипотезы, предлагают план: «Проверить связность, найти циклы, сравнить число рёбер с числом вершин». Формулируют цель урока: «Вывести и применять признаки дерева». |
Завершение этапа: учитель подводит итог: «Проблема поставлена: одного подсчёта вершин недостаточно. Сейчас исследуем определения и проверим, какие признаки действительно работают всегда».
Этап 4. Открытие нового знания (11 мин)
Цель этапа: сформировать понятия графа и дерева и вывести основные свойства дерева через исследование.
Время | Действие учителя | Действие учеников |
|---|---|---|
4 мин | Учитель демонстрирует схему и записывает на доске: «Граф — это множество вершин и соединяющих их рёбер. Степень вершины — число рёбер, инцидентных этой вершине. Путь — последовательность вершин, в которой соседние вершины соединены ребром. Цикл — замкнутый путь без повторения промежуточных вершин». Просит найти эти элементы на схеме. | Записывают определения, показывают на схеме вершины, рёбра, путь и цикл. Отвечают: «Степень вершины равна числу линий, выходящих из неё». |
4 мин | Учитель раздаёт группам изображения четырёх графов: «Исследуйте схемы. Для каждой отметьте связность, наличие цикла и число вершин и рёбер. Не называйте граф деревом, пока не приведёте два аргумента. Используйте таблицу на доске». Учитель задаёт уточняющие вопросы: «Можно ли попасть из любой вершины в любую? Что изменится, если убрать одно ребро цикла?» | В группах распределяют роли, заполняют таблицу, находят циклы и проверяют маршруты. Формулируют выводы: «Граф связен, если между любыми двумя вершинами существует путь», «Удаление ребра цикла не разрушает связность». |
3 мин | Учитель подводит к обобщению: «Для дерева важны два признака: связность и отсутствие циклов. Для дерева с $n$ вершинами число рёбер равно $n-1$. Это не отдельное случайное правило: если добавить ребро к дереву, появится цикл, а если убрать ребро, дерево распадётся на части. Проверим это на нашей схеме». | Сравнивают число вершин и рёбер, формулируют правило: «В дереве с $n$ вершинами $n-1$ рёбер». Объясняют, почему лишнее ребро создаёт цикл, а удаление ребра разрушает связность. |
Запись в тетрадях
Граф — множество вершин и рёбер. Дерево — связный граф без циклов. Для дерева с $n$ вершинами число рёбер равно $n-1$. Степень вершины — число рёбер, соединённых с этой вершиной.
Завершение этапа: учитель подводит итог: «Мы получили рабочее определение дерева и его числовой признак. Теперь применим их сначала вместе, проговаривая каждый шаг, а затем самостоятельно».
Этап 5. Первичное закрепление (7 мин)
Цель этапа: закрепить алгоритм классификации графа и нахождения степеней вершин.
Время | Действие учителя | Действие учеников |
|---|---|---|
4 мин | Учитель предлагает задачу: «Рассмотрим граф с вершинами A, B, C, D, E и рёбрами AB, BC, CD, DE. Определите число вершин и рёбер, степень каждой вершины, является ли граф деревом. Объясните ответ по двум признакам». Просит одного ученика комментировать решение у доски. | Составляют схему или используют список рёбер, называют степени: A — 1, B — 2, C — 2, D — 2, E — 1. Делают вывод: «Граф связен, циклов нет, рёбер 4, а $5-1=4$, поэтому это дерево». |
3 мин | Учитель даёт парную задачу: «Граф имеет вершины 1, 2, 3, 4, 5 и рёбра 12, 23, 34, 41, 45. Является ли он деревом? Запишите краткое обоснование». После решения просит применить взаимопроверку по критериям: названы связность, цикл и число рёбер. | В парах обнаруживают цикл 1–2–3–4–1, проверяют связность и отвечают: «Граф не является деревом, потому что содержит цикл; также в нём 5 рёбер, а для пяти вершин в дереве должно быть 4». Взаимно отмечают наличие двух аргументов. |
Эталон решения
В графе пять вершин и пять рёбер. Вершины 1, 2, 3, 4 образуют цикл $1-2-3-4-1$. Вершина 5 соединена с 4, поэтому граф связен, но дерево не может содержать цикл. Дополнительно проверяем число рёбер: для дерева с пятью вершинами должно быть $5-1=4$, а дано пять рёбер. Следовательно, граф не является деревом.
Завершение этапа: учитель подводит итог: «Алгоритм проверки работает в любом порядке: можно начать с цикла, связности или подсчёта рёбер, но итог нужно подтвердить определениями. Теперь каждый проверит себя на новой ситуации».
Этап 6. Самостоятельная работа с самопроверкой (9 мин)
Цель этапа: проверить индивидуальное освоение понятий и умение применять их к новой модели.
Время | Действие учителя | Действие учеников |
|---|---|---|
6 мин | Учитель раздаёт карточки трёх уровней. «Выберите уровень по готовности: обязательный минимум, базовый или повышенный. На каждом листе нужно не только дать ответ, но и указать признак, на который вы опирались. Минимум: по рисунку определить степени двух вершин и наличие цикла. Базовый: определить, является ли граф деревом. Повышенный: восстановить одно ребро, которое нужно удалить, чтобы граф с одним циклом стал деревом». | Индивидуально решают выбранный вариант, записывают ход рассуждения. Проверяют, что для утверждения о дереве указаны связность, отсутствие цикла или соотношение $m=n-1$. |
3 мин | Учитель выводит эталон на экран: «Сверьте не только ответ, но и способ. Если есть расхождение, поставьте рядом знак вопроса и исправьте решение другим цветом. Затем оцените себя: зелёный — могу объяснить, жёлтый — нужна тренировка, красный — нужна помощь». | Сверяют решения с эталоном, исправляют ошибки, отмечают цвет самооценки и формулируют конкретное затруднение, например: «Не всегда замечаю цикл», «Путаю число рёбер со степенью вершины». |
Завершение этапа: учитель подводит итог: «Самопроверка показала, что важен не случайно угаданный ответ, а последовательность проверки. Осталось связать графы с реальными информационными системами и сформулировать личный вывод».
Этап 7. Включение в систему знаний и рефлексия (4 мин)
Цель этапа: применить понятия к жизненному контексту и осознать результаты урока.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель показывает четыре контекста: «Определите, где естественно использовать дерево: структура папок, карта дорог с альтернативными маршрутами, социальная сеть или схема наследования классов. Объясните выбор. Помните: дерево не содержит циклов, а между двумя вершинами дерева существует единственный путь». | Выбирают структуру папок и схему наследования, обосновывают: «В иерархии от корня к объекту идёт единственный путь». Приводят контрпример для карты дорог: «Альтернативные маршруты создают циклы». |
2 мин | Учитель проводит «Билет на выход»: «Запишите три коротких ответа: что такое дерево; как проверить, что граф не является деревом; где графы применяются вне урока». Затем спрашивает: «Какой следующий вопрос вы бы исследовали на уроке алгоритмов?» | Заполняют билет на выход, формулируют ответы и один исследовательский вопрос, например: «Как найти кратчайший путь?» или «Как хранить граф в программе?» |
Завершение этапа: учитель подводит итог: «Сегодня вы перешли от рисунка к строгой модели: научились видеть вершины и рёбра, проверять связность и циклы, доказывать, что граф является деревом или не является им. На следующем уроке мы рассмотрим способы хранения графов и алгоритмы поиска путей».
Критерии оценивания практической работы
- «5» — верно выполнены все пункты выбранной карточки, правильно найдены степени вершин, связность и циклы, вывод о дереве обоснован минимум двумя признаками.
- «4» — выполнено не менее 80% задания, допущена одна неточность в подсчёте или записи, но общий способ проверки дерева выбран верно.
- «3» — определены основные объекты графа и дан частично верный вывод, однако отсутствует одно из обоснований или допущена ошибка при проверке цикла.
- Ниже базового уровня — ученик перечисляет отдельные признаки, но не связывает их с конкретным графом; требуется индивидуальная коррекция алгоритма проверки.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Что такое дерево и какие два признака помогают его распознать? | Проверка осознания ключевого определения и критериев классификации. |
Как вы докажете, что данный граф не является деревом? | Выявление умения использовать цикл, несвязность или число рёбер как аргумент. |
Какое действие оказалось самым сложным: найти цикл, проверить связность или подсчитать степени вершин? | Выявление точек затруднения в алгоритме анализа графа. |
Где графовая модель может пригодиться в вашей будущей профессии? | Связывание предметного знания с профессиональной мотивацией и функциональной грамотностью. |
Завершающее слово учителя
«Сегодня мы научились рассматривать граф не как случайный рисунок, а как строгую модель объектов и связей. Особенно важно не путать связность с отсутствием циклов: дерево должно обладать обоими признаками. Если вы сомневаетесь, проверьте путь между вершинами, найдите цикл и сравните число рёбер с $n-1$. На следующем уроке мы переведём графовые модели в структуры данных и обсудим алгоритмы поиска путей».
Домашнее задание
Уровень | Что задать | Зачем |
|---|---|---|
Базовый (обязательный) | Выполнить 4 задания на распознавание вершин, рёбер, степеней вершин, путей и циклов по предложенным схемам графов. | Закрепляет терминологию и базовый алгоритм чтения графа; при проверке обратить внимание на точность подсчёта степени вершины. |
Средний (повышающий) | Решить 3 задачи на определение, является ли граф деревом, с обязательным обоснованием через связность, циклы и соотношение $m=n-1$. | Формирует умение доказывать вывод несколькими признаками; проверить наличие полного рассуждения, а не только ответа. |
Продвинутый (дополнительный) | Смоделировать одну реальную систему: структуру папок, сеть маршрутов или зависимости учебных курсов. Представить её графом, указать вершины и рёбра и объяснить, является ли модель деревом. | Развивает проектное мышление и перенос знаний в практический контекст; оценить адекватность модели и качество аргументации. |
Контрольные вопросы перед выходом: «Что называется вершиной и ребром? Чем путь отличается от цикла? Какие два свойства обязательны для дерева? Сколько рёбер должно быть в дереве с $8$ вершинами? Почему добавление одного ребра в дерево создаёт цикл?»