План урока на тему:

Графы и деревья: представление, свойства и применение

Информатика11 класс63 раздела
Графы и деревья: представление, свойства и применение

Информатика · 11 класс · Открытие нового · 45 мин

Графы и деревья: представление, свойства и применение

Цели и задачи

  • Цель по 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$ вершинами? Почему добавление одного ребра в дерево создаёт цикл?»

Создайте уникальный план урока по своей теме

  • Любая тема, любой уровень
  • Структура по ФГОС
  • 100% уникальный план урока
  • Цели, ход урока, рефлексия
  • Экспорт в PDF и Word
  • Готово за 1 минуту

Другие темы по информатике для 11 класса

Единственность представления чисел в q-ичных системах счисления. Алфавиты позиционных систем счисленияВизуализация данных и интерпретация результатовАнализ правильности скобочного выраженияДискретные игры двух игроков с полной информацией; Графы. Основные понятия. Виды графов; Построение оптимального пути между вершинами графа; Количество различных путей в ориентированном ациклическомСловари (ассоциативные массивы, отображения). Хэш-таблицыДискретные игры двух игроков с полной информациейСервисы машинного перевода и распознавания устной речи; Идентификация и поиск изображений, распознавание лиц; Самообучающиеся системы; Искусственный интеллект в компьютерных играх и обучающихАдресация в сети Интернет. Система доменных имён; Веб-сайт и веб-страница. Взаимодействие браузера с веб-сервером; Сетевое хранение данныхСетевые протоколы. Сеть Интернет; Веб-сайт и веб-страница. Взаимодействие браузера с веб-сервером; Сетевое хранение данных; Принципы построения и аппаратные компоненты компьютерных сетейБазы данныхКомпьютерные сети и ИнтернетРабота в QGIS

Чем удобны планы уроков Нейрум

  • Готовый план, не набросокЦели, ход урока, планируемые результаты, рефлексия — всё по структуре ФГОС, открыли и пошли вести.
  • План урока или техкартаОдин материал — два формата экспорта в PDF. Скачали то, что нужно завучу.
  • Свой план урока за минутуНе нашли нужный? ИИ-конструктор напишет план урока по вашей теме, классу и типу урока.

Вопросы и ответы

Как скачать план урока «Графы и деревья»?

Зарегистрируйтесь бесплатно — материал сохранится в личном кабинете, откуда его можно скачать как план урока или технологическую карту.

Соответствует ли план урока ФГОС?

Да, структура урока — цели, ход урока, планируемые результаты — построена по ФГОС для 11 класса (информатике).

Можно ли изменить план под свой класс?

Да. После регистрации план урока открывается в конструкторе: этапы и содержание можно отредактировать или перегенерировать.