Использование графов, при решение задач

Разделы: Информатика

Класс: 9

Ключевые слова: информатика, графы, решение задач с помощью графов


Пояснительная записка

Актуальность. Основной задачей школы является не подача детям большого объёма знаний, а обучение учащихся самим добывать знания, умению перерабатывать эти знания и применять их в каждодневной жизни. Поставленные задачи может решить ученик, обладающий не только умением хорошо и много работать, но и ученик с развитым логическим мышлением. В связи с этим во многие школьные предметы вложены различного типа задачи, которые и развивают у детей логическое мышление. Решая эти задачи, мы применяем различные приёмы решения. Одни из приёмов решения – это граф.

«Графы» имеют корень греческого слова «графо», что значит «пишу». Тот же корень в словах «график», «биография», «голография».

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Толчок к развитию теория графов получила на рубеже XIX и XX столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми её связывают самые тесные узы родства. В последнее время графы и связанные с ними методы исследований пронизывают на разных уровнях едва ли не всю современную математику. Графы используются в теории планирования и управления, теории расписаний, социологии, математической лингвистике, экономике, биологии, медицине. Как более жизненный пример можно взять использование графов в геоинформационных системах. Существующие или вновь проектируемые дома, сооружения, кварталы и т.п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т.п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут. Теория графов быстро развивается, находит всё новые приложения и ждёт молодых исследователей.

Ход урока

Организационный момент

Здравствуйте! Рада вас всех видеть на нашем уроке. Кто отсутствует?  Древняя китайская мудрость гласит: «Я слышу - я забываю, я вижу – я запоминаю, я делаю – я понимаю». Поэтому сегодня на уроке мы познакомимся с новыми правилами и научимся их применять при решении практических задач.

Актуализация знаний

Опрос учащихся. Решение простых задач.

Что такое граф, ребра?

Граф – это конечное множество точек, некоторые из которых соединены линиями.

Точки – называются вершинами, а соединяющие их линии – ребрами.

- Давайте посчитаем сколько в полученном графе вершин и ребер.

Число ребер, выходящих из каждой вершины графа мы будем называть степенью этой вершины.

Если из вершины выходит нечетное число ребер – она будет называться нечетной, а если четное – четной.

- Назовите, пожалуйста, сколько ребер выходит из каждой вершины и назовите степень вершины каждого графа (дети отвечают на поставленный вопрос)

Задача №1. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий, Плутон – Венера, Земля – Плутон, Плутон – Меркурий, Меркурий – Венера, Уран – Нептун, Нептун – Сатурн, Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса?

- Что же нам необходимо сделать, чтобы решить эту задачу?

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

- Опять, что мы с вами нарисовали?

Задача №2. Допустим, что у вас в понедельник 4 урока: русский язык, математика, история и технология. Сколькими способами можно составить расписание из 4 предметов, если первым уроком должна быть математика и предметы не повторяются.

- Как же нам можно решить эту задачу?

(Выслушиваются ответы детей).

Доклад учащегося. (историческая справка)

Хронологически первой в теории графов считается задача о семи кенигсбергских мостах, которую решил Эйлер. Она состоит в следующем. Парк города Кенигсберга был расположен на обоих берегах реки Прегель и на двух островах. Острова с берегами и друг с другом были соединены семью мостами так, как на рис. 1. Любимой забавой горожан были поиски такого маршрута, который кончался бы на том же берегу, где и начинался, проходил бы по всем мостам, но по каждому мосту – только один раз. С давних времен жители Кенигсберга бились над загадкой: можно ли пройти по всем мостам, пройдя по каждому только один раз? Эту задачу решали и теоретически, на бумаге, и на практике, на прогулках - проходя по этим самым мостам. Никому не удавалось доказать, что это неосуществимо, но и совершить такую «загадочную» прогулку по мостам никто не мог.
Разрешить проблему удалось знаменитому математику Леонарду Эйлеру. В 1736 году. Причем, он решил не только эту конкретную задачу, но придумал общий метод решения подобных задач. Задач вида «одним росчерком».

- У меня в руках 2 картинки: домик и прямоугольник, в котором проведены диагонали.

- А теперь я попрошу вас вспомнить – рисовали ли вы «домик», не отрывая карандаш от бумаги?

У вас на листочках эти фигуры. Ваша задача: выяснить, можно ли нарисовать эти фигуры, не отрывая карандаш от листа.

Кто смог нарисовать эти фигуры?

Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. Такими графы названы в честь учёного Леонарда Эйлера.

Объявление темы урока

Скажите, пожалуйста, а как можно использовать графы при решении задач?

Вот мы и отгадали название новой темы: «Использование графов при решении задач».

Изучение нового материала

Сколько существует трёхзначных чисел, состоящих из цифр 1 и 2?

Граф задачи о переправе

Задача. На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому.

Решение:

Вершины графа - это деревья, обозначенный первой буквой названия дерева. В данной задача два отношения: “быть ниже” и “быть выше”. Рассмотрим отношение “быть ниже” и проведем стрелки от более низкого дерева к более высокому. Если в задаче сказано, что рябина выше лиственницы, то стрелку ставим от лиственницы к рябине и т.д. Получаем граф, на котором видно, что самое низкое дерево – клен, затем идут яблоня, лиственница, рябина, сосна, дуб, береза и тополь.

Динамическая пауза: физкультминутка

Закрепление изученного материала

Ниже представлен разбор задач.

Для того, чтобы вы могли применить полученные навыки и оценить степень овладения ими выполните тренировочное задание. Интерактивное задание  https://www.kpolyakov.spb.ru/school/test10/5.htm. После выполнения заданий учащиеся могут получить оценки, так как сразу можно выполнить проверку.

Домашнее задание. §1.3.

Рефлексия

Подготавливаются смайлики, которые учащиеся показывают учителю и одноклассникам, с каким настроением они закончили урок.

Технологическая карта урока

Список литературы

  1. Информатика и ИКТ, 9 класс, Л.Л.Босова, А.Ю.Босова. - М.: БИНОМ. Лаборатория знаний, 2019.
  2. Интерактивное задание https://www.kpolyakov.spb.ru/school/test10/5.htm