граф, связный граф, представление задачи с помощью графа

Ход урока

1. 11. Организационный момент и мотивация

   5 минут

   Учитель

   • Приветствует класс: «Здравствуйте! Сегодня мы будем учиться изображать связи между объектами так, чтобы сложная задача стала наглядной»
   • Показывает схему нескольких городов, соединённых дорогами.
   • Спрашивает: «Как можно быстро показать, какие города соединены дорогами, не рисуя сами города и дороги подробно?»
   • Подводит к теме: «Сегодня мы познакомимся с графами и научимся переводить условие задачи на язык графов».

   Ученики

   • Приветствуют учителя и готовят тетради.
   • Рассматривают предложенную схему.
   • Предлагают способы обозначения объектов и связей.
   • Формулируют тему урока.

   Результат

   Учащиеся формулируют, что для описания объектов и связей между ними удобно использовать специальную схему.

2. 22. Изучение понятия «граф»

   8 минут

   Учитель

   • Говорит: «Граф состоит из объектов, которые мы назовём вершинами, и связей между ними, которые назовём рёбрами».
   • Показывает граф из пяти точек и нескольких соединяющих их линий.
   • Объясняет: «Точка обозначает объект, а линия между двумя точками — наличие связи между объектами».
   • Спрашивает: «Что в этой модели являются вершинами? Что являются рёбрами?»
   • Уточняет: «Важно: форма рисунка не имеет значения, важны только заданные вершины и связи между ними».

   Ученики

   • Записывают определения.
   • Называют вершины и рёбра на рисунке.
   • Отвечают на вопросы учителя.

   Результат

   Учащиеся правильно различают вершины и рёбра на изображённом графе и воспроизводят определения.

3. 33. Связный граф

   7 минут

   Учитель

   • Показывает два графа: один состоит из одной связной части, второй — из двух отдельных частей.
   • Спрашивает: «Можно ли из любой вершины первого графа попасть в любую другую, двигаясь по рёбрам?»
   • Объясняет: «Граф называется связным, если между любыми двумя его вершинами существует путь».
   • Показывает путь между двумя выбранными вершинами.
   • Спрашивает: «Почему второй граф не является связным?»

   Ученики

   • Сравнивают два графа.
   • Находят путь между указанными вершинами.
   • Формулируют причину несвязности второго графа.

   Результат

   Учащиеся определяют, является ли граф связным, и объясняют ответ через существование путей между вершинами.

4. 44. Представление текстовой задачи с помощью графа

   10 минут

   Учитель

   • Предлагает задачу: «В деревне есть четыре населённых пункта: А, Б, В и Г. Дороги соединяют А с Б, А с В, Б с В и В с Г. Представьте эту информацию с помощью графа».
   • Спрашивает: «Что здесь является объектами?»
   • Уточняет: «Что обозначим вершинами? Что будет означать ребро?»
   • Строит первый фрагмент графа вместе с классом.
   • Спрашивает: «Какие рёбра должны появиться после этого? Проверьте, все ли дороги отражены».

   Ученики

   • Выделяют населённые пункты как объекты.
   • Предлагают обозначить пункты вершинами.
   • Соединяют вершины рёбрами согласно условию.
   • Сверяют полученный граф с текстом задачи.

   Результат

   Учащиеся строят граф, точно отражающий заданные в тексте связи между четырьмя объектами.

5. 55. Первичное закрепление

   7 минут

   Учитель

   • Раздаёт карточки: «Пять учеников: Аня, Борис, Вика, Глеб и Даша знакомы попарно следующим образом: Аня с Борисом и Викой, Борис с Глебом, Вика с Глебом и Дашей. Постройте граф знакомств».
   • Говорит: «Сначала выпишите вершины, затем последовательно отметьте каждую связь из условия».
   • Предлагает учащимся сравнить решения в парах.
   • Разбирает ошибку: «Если связь указана в условии, ребро должно присутствовать на графе; если не указана, добавлять его нельзя».

   Ученики

   • Строят граф самостоятельно.
   • Сравнивают решение с соседом.
   • Исправляют обнаруженные ошибки.

   Результат

   Большинство учащихся самостоятельно строят граф по текстовому описанию и объясняют соответствие рёбер условию.

6. 66. Итог урока и рефлексия

   3 минуты

   Учитель

   • Спрашивает: «Что называют вершиной и ребром?»
   • Спрашивает: «Когда граф называют связным?»
   • Просит сформулировать алгоритм: «Что мы делаем первым, вторым и третьим при переводе задачи на язык графов?»
   • Подводит итог: «Сегодня мы научились превращать текстовое описание связей в графическую модель».

   Ученики

   • Дают определения.
   • Объясняют признак связного графа.
   • Формулируют последовательность построения графа.

   Результат

   Учащиеся формулируют определения графа и связного графа и называют основные шаги построения графа по условию задачи.