Пояснительная записка
Актуальность. Основной задачей школы является не подача детям большого объёма знаний, а обучение учащихся самим добывать знания, умению перерабатывать эти знания и применять их в каждодневной жизни. Поставленные задачи может решить ученик, обладающий не только умением хорошо и много работать, но и ученик с развитым логическим мышлением. В связи с этим во многие школьные предметы вложены различного типа задачи, которые и развивают у детей логическое мышление. Решая эти задачи, мы применяем различные приёмы решения. Одни из приёмов решения – это граф.
«Графы» имеют корень греческого слова «графо», что значит «пишу». Тот же корень в словах «график», «биография», «голография».
Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Толчок к развитию теория графов получила на рубеже XIX и XX столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми её связывают самые тесные узы родства. В последнее время графы и связанные с ними методы исследований пронизывают на разных уровнях едва ли не всю современную математику. Графы используются в теории планирования и управления, теории расписаний, социологии, математической лингвистике, экономике, биологии, медицине. Как более жизненный пример можно взять использование графов в геоинформационных системах. Существующие или вновь проектируемые дома, сооружения, кварталы и т.п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т.п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут. Теория графов быстро развивается, находит всё новые приложения и ждёт молодых исследователей.
Ход урока
Организационный момент
Здравствуйте! Рада вас всех видеть на нашем уроке. Кто отсутствует? Древняя китайская мудрость гласит: «Я слышу - я забываю, я вижу – я запоминаю, я делаю – я понимаю». Поэтому сегодня на уроке мы познакомимся с новыми правилами и научимся их применять при решении практических задач.
Актуализация знаний
Опрос учащихся. Решение простых задач.
Что такое граф, ребра?
Граф – это конечное множество точек, некоторые из которых соединены линиями.
Точки – называются вершинами, а соединяющие их линии – ребрами.
- Давайте посчитаем сколько в полученном графе вершин и ребер.
Число ребер, выходящих из каждой вершины графа мы будем называть степенью этой вершины.
Если из вершины выходит нечетное число ребер – она будет называться нечетной, а если четное – четной.
- Назовите, пожалуйста, сколько ребер выходит из каждой вершины и назовите степень вершины каждого графа (дети отвечают на поставленный вопрос)
Задача №1. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий, Плутон – Венера, Земля – Плутон, Плутон – Меркурий, Меркурий – Венера, Уран – Нептун, Нептун – Сатурн, Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса?
- Что же нам необходимо сделать, чтобы решить эту задачу?
Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.
- Опять, что мы с вами нарисовали?
Задача №2. Допустим, что у вас в понедельник 4 урока: русский язык, математика, история и технология. Сколькими способами можно составить расписание из 4 предметов, если первым уроком должна быть математика и предметы не повторяются.
- Как же нам можно решить эту задачу?
(Выслушиваются ответы детей).
Доклад учащегося. (историческая справка)
Хронологически первой в теории графов считается задача о семи кенигсбергских мостах, которую решил Эйлер. Она состоит в следующем. Парк города Кенигсберга был расположен на обоих берегах реки Прегель и на двух островах. Острова с берегами и друг с другом были соединены семью мостами так, как на рис. 1. Любимой забавой горожан были поиски такого маршрута, который кончался бы на том же берегу, где и начинался, проходил бы по всем мостам, но по каждому мосту – только один раз. С давних времен жители Кенигсберга бились над загадкой: можно ли пройти по всем мостам, пройдя по каждому только один раз? Эту задачу решали и теоретически, на бумаге, и на практике, на прогулках - проходя по этим самым мостам. Никому не удавалось доказать, что это неосуществимо, но и совершить такую «загадочную» прогулку по мостам никто не мог.
Разрешить проблему удалось знаменитому математику Леонарду Эйлеру. В 1736 году. Причем, он решил не только эту конкретную задачу, но придумал общий метод решения подобных задач. Задач вида «одним росчерком».
- У меня в руках 2 картинки: домик и прямоугольник, в котором проведены диагонали.
- А теперь я попрошу вас вспомнить – рисовали ли вы «домик», не отрывая карандаш от бумаги?
У вас на листочках эти фигуры. Ваша задача: выяснить, можно ли нарисовать эти фигуры, не отрывая карандаш от листа.
Кто смог нарисовать эти фигуры?
Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. Такими графы названы в честь учёного Леонарда Эйлера.
Объявление темы урока
Скажите, пожалуйста, а как можно использовать графы при решении задач?
Вот мы и отгадали название новой темы: «Использование графов при решении задач».
Изучение нового материала
Сколько существует трёхзначных чисел, состоящих из цифр 1 и 2?
Граф задачи о переправе
Задача. На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому.
Решение:
Вершины графа - это деревья, обозначенный первой буквой названия дерева. В данной задача два отношения: “быть ниже” и “быть выше”. Рассмотрим отношение “быть ниже” и проведем стрелки от более низкого дерева к более высокому. Если в задаче сказано, что рябина выше лиственницы, то стрелку ставим от лиственницы к рябине и т.д. Получаем граф, на котором видно, что самое низкое дерево – клен, затем идут яблоня, лиственница, рябина, сосна, дуб, береза и тополь.
Динамическая пауза: физкультминутка
Закрепление изученного материала
Ниже представлен разбор задач.
Для того, чтобы вы могли применить полученные навыки и оценить степень овладения ими выполните тренировочное задание. Интерактивное задание https://www.kpolyakov.spb.ru/school/test10/5.htm. После выполнения заданий учащиеся могут получить оценки, так как сразу можно выполнить проверку.
Домашнее задание. §1.3.
Рефлексия
Подготавливаются смайлики, которые учащиеся показывают учителю и одноклассникам, с каким настроением они закончили урок.
Технологическая карта урока
Список литературы
- Информатика и ИКТ, 9 класс, Л.Л.Босова, А.Ю.Босова. - М.: БИНОМ. Лаборатория знаний, 2019.
- Интерактивное задание https://www.kpolyakov.spb.ru/school/test10/5.htm