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