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