Урок по теме «Графы. Решение алгоритмических задач, связанных с анализом графов»
Класс: 11.
Тип урока: урок систематизации и обобщения знаний и умений / урок применения знаний и навыков.
Цель: показать многообразие практических задач, решаемых с помощью графов; отработать алгоритмы анализа графов на практике.
Время: 40 мин.
Задачи:
Образовательные: закрепить понятия «граф», «вершина», «ребро», «путь», «степень вершины», «ориентированный/неориентированный граф»; отработать типовые алгоритмы (поиск пути, подсчет степеней, анализ связности).
Развивающие: развить логическое и алгоритмическое мышление, умение строить математические модели реальных ситуаций.
Воспитательные: сформировать навыки работы в паре/группе, культуру обсуждения решений.
Формы работы:
фронтальная (объяснение, обсуждение);
парная/групповая (решение задач);
индивидуальная (самостоятельная работа, рефлексия).
Оборудование и материалы
презентация с определениями и примерами графов;
раздаточные листы с задачами и схемами графов;
доска/флипчарт для схематичного изображения графов;
(опционально) компьютеры с ПО для визуализации графов
План урока (40мин)
Организационный момент (1 мин)
Приветствует учащихся, проверяет их готовность к уроку.
Сегодня вы пройдете очередной шаг по дороге знаний, и я с радостью помогу вам сделать этот шаг.
Так уж получилось, что сегодня мы начинаем работу над новой темой «Информационное моделирование». Данная тема нам хорошо знакома с курса основной школы, поэтому наша задача повторить и углубить знания в данной области.
Актуализация знаний (7 мин)
Перед вами имеются карточки с ключевыми слова из изучаемой нами темы. Ваша задача собрать интеллект-карту по теме «Моделирование».
Модель — это упрощённое представление реального объекта или процесса, созданное с целью усвоения, анализа или улучшения этого объекта или процесса.
Моделирование — это создание и исследование моделей с целью их изучения.
Виды моделей
В информатике модели делятся на материальные (предметные) и информационные.
Материальные — воспроизводят геометрические, физические, химические, биологические свойства объектов в материальной форме.
Примеры: модель глобуса, манекен человека, чучело животного.
Информационные — представляют объекты и процессы в форме схем, чертежей, таблиц, формул, текстов и т. д.. Информационные модели нельзя потрогать, они не имеют материального воплощения, потому что строятся только на информации.
Информационные модели включают следующие модели: вербальные, табличные, графические, математические.
Графы.
Огромное спасибо, вы проделали огромную работу, восстановив знания по теме «Моделирование», но теперь давайте сформулируем тему урока, а также чем мы будем заниматься на нем:
Повторим… Что такое граф? Приведите примеры из жизни. Назовите основные элементы графа (вершина, ребро).
Изучим… Чем отличается ориентированный граф от неориентированного? Что такое степень вершины? Как её найти?
Узнаем…
Изложение нового материала / повторение алгоритмов (10 мин)
Графы используют во всех отраслях нашей жизни. Знание основ теории графов необходимо в управлении производством, бизнесе, при построении путей транспортировки и доставки, решении задач.
Графы используют в связи с развитием теории вероятности, математической логики и информационных технологий.
Степенью вершины называют количество ребер, выходящих из одной вершины.
Для петли ребро выходит из вершины дважды.
Обозначать степень вершины а будем как γ(а).
Виды графов:
Простой граф — это граф, в котором нет петель (ребер, соединяющих вершину саму с собой) и кратных ребер (ребер, соединяющих одну и ту же пару вершин).
Примером простого графа может быть схема дорог между городами, где вершины — это города, а ребра — это дороги.
Псевдограф — это граф, в котором могут быть петли и кратные ребра.
Примером псевдографа может быть схема электрической цепи, где вершины — это узлы цепи, а ребра — это провода.
Мультиграф — это граф, в котором могут быть кратные ребра, но не петли.
Примером мультиграфа может быть схема перелетов авиакомпании, где вершины — это аэропорты, а ребра — это рейсы.
Ориентированный граф (или орграф) — это граф, в котором ребра имеют направление. Такие ребра называются дугами.
Примером ориентированного графа может быть схема интернет-сайтов, где вершины — это страницы сайтов, а дуги — это ссылки.
Смешанный граф — это граф, в котором есть как ориентированные, так и неориентированные ребра.
Примером смешанного графа может быть схема железнодорожной сети, где вершины — это станции, а ребра — это пути: однонаправленные или двунаправленные.
Полный граф — это простой граф, в котором каждая пара различных вершин соединена ровно одним ребром.
Примером полного графа может быть схема телефонной связи между абонентами, если каждый абонент может позвонить любому другому.
Двудольный граф — это простой граф, в котором множество вершин можно разбить на два подмножества так, что никакое ребро не соединяет вершины одного и того же подмножества.
Примером двудольного графа может быть схема связи между работниками и проектами в компании, если каждый работник участвует хотя бы в одном проекте, а каждый проект включает хотя бы одного работника.
Эйлеров граф — это простой связный граф, в котором можно обойти все ребра, проходя по каждому из них ровно один раз. Такой путь называется эйлеровым циклом.
Примером эйлерова графа может быть схема маршрута туриста, который хочет посетить все достопримечательности города, не проходя дважды по одной и той же улице.
Свойства графов:
В любом графе есть, по крайней мере, две вершины, имеющие одинаковую степень.
Для любого графа количество вершин нечетной степени всегда будет четное.
Сумма степеней всех вершин графа равна удвоенному числу его
Всего есть 3 типа задач с графами: Неоднозначное и однозначное соотнесение таблицы с графом и задачи на алгоритм Декстера. Алгоритм Дейкстры — алгоритм на графах, который находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм широко применяется в программировании и технологиях.
Кардинальных различий между ними нет, лишь то, что в “Неоднозначных” не всегда можно точно определить полное соответствие между вершинами графа и их значением в таблице. Но в этих задачах это не требуется. Также в таблице смежности не указаны вершины, а их названия заменены на цифры. Обычно нам нужно найти соответствие между заданной вершиной и цифрой или длину ребра между двумя вершинами (если вместо звездочек стоят числа, соответствующие длине дороги).
Главная идея решения этой задачи заключается в том, что нужно найти одну или несколько вершин, которые чем-то отличаются от других. Они могут отличаться степенью или степенями смежных с ними вершин. И уже для этих вершин мы можем сделать некоторые выводы и от них строить соответствие между таблицей и графом.
Алгоритм решения:
1. Нужно у каждой вершины рядом записать ее степень
2. Разбить все вершины на группы по их степени
3. Установить соответствие между группой вершин и номерами вершин в таблице, которые им соответствуют. Если есть вершины со степенью, которая не повторяется у других вершин, то можно установить однозначное соответствие для этой вершины.
4. Разбить в одной группе на подгруппы по степени смежных с ними вершин
5. Проанализировать полученную информацию.
Физминутка (1 мин)
Медленно опишите глазами круг по часовой стрелке, затем против. По 3 круга в каждую сторону (≈10 сек).
Расслабление. Закройте глаза, глубоко вдохните и выдохните (≈5 сек).
Важно: не напрягайте лоб и брови, движения глаз — плавные.
Закрепление: решение задач (15 мин)
Рассмотрим пример «Представление графа таблицей смежности»:
Задача 4
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о дорогах между населенными пунктами (звездочка означает, что дорога между соответствующими городами есть).
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите номера населенных пунктов A и G в таблице. В ответе запишите числа в порядке возрастания без разделителей.
В этой задаче нам необходимо определить под какими номерами записаны вершины A и G, причем нам не необязательно определять точное соответствие, достаточно найти два номера.
Начнем решать, пройдемся по пунктам нашего алгоритма
1. A – 3, B – 3, C –2, D – 3, E – 2, F – 6, G –3.
2. У нас получилось 3 группы. F-6 вершин, C и E – 2 вершины и A, B, D, G – 3 вершины.
3. Мы можем заключить, что вершине F соответствует номер 3, C и E — 4 и 5, а A, B, D и G — 1, 2, 6 и 7.
4. Заметим, что некоторые вершины графа симметричны C – E, D – B, G – A, также заметим, что группу степени 3 можно разбить на 2 подгруппы, те у которых смежные вершины имеют степень 3, 3, 6 и 3, 2, 6, вершины первой подгруппы - A, G, а вершины второй подгруппы - D, B.
5. Начнем анализировать информацию, вершины 4,5 (C, E) связаны с вершинами 3, 1, 2, мы знаем, что F-3, значит 1, 2 соответствуют B, D. Значит вершинам A и G соответствуют вершины 6 и 7.
Задача 5
Рассмотрим еще одну задачу, в ней вместо звездочек нам даны числа, обозначающие длину ребер между вершин. Нам нужно найти сумму длин ребер Б - Д и В - Е.
Воспользуемся нашим алгоритмом
1. А - 2, Б - 3, В - 3, Г - 3, Д - 3, Е - 3, К - 3.
2. Здесь у нас получается всего две группы А - 2 вершины и Б, В, Г, Д, Е, К - 2 вершины.
3. Мы можем понять, что вершине А соответствует номер 4 из таблицы.
4. В группе Б, В, Г, Д, Е, К можем выделить подгруппу Б, В у них смежные вершины имеют степень 2, 3, 3, в то время как у всех остальных смежные вершины имеют степень 3, 3, 3.
5. Начнем анализировать информацию. Вершина А соединена с вершинами Б, В, а судя по таблице 4 вершина соединена с 3 и 6 вершиной, значит вершинам Б, В соответствуют вершины 3, 6. Рассмотрим вершины 3, 6, они соединены с вершинами 2, 4, 6 и 1, 3, 4 соответственно. Можем сделать вывод, что вершинам Д, Е соответствуют номера 1, 2. Тогда ребрам Б - Д и В - Е соответствуют ребра 3 – 2, 6 – 1. Их длина равна 14 и 8, а их сумма равна 22.
6. Итог урока. Теперь давайте вспомним задачи урока, которые мы сформулировали в начале урока:
Повторим…
Достиг ли урок своих целей?
Все ли задачи были выполнены в ходе урока?
7. Д\З. Параграф 11 стр. 148-158. Выполнить задание на стр.159 №2
8.Рефлексия
Сегодня я узнал….
Было трудно…
Я выполнил задание…
Теперь я могу….