Теория графов находит применение, например, в геоинформационных системах ГИС. Существующие или вновь проектируемые дома, сооружения, кварталы и т. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут. В качестве домашнего задания ученикам было предложено подготовить небольшие объемом слайда презентации на тему "Применение графа". При проверке ученика могут показать свои презентации классу на экране. По ходу урока ученики работают с электронными тетрадями, которые можно подготовить в PowerPoint. Все необходимые зарисовки они делают с помощью средств рукописных заметок в режиме показа презентации. После урока презентацию со своими записями ученики сохраняют и уносят домой для подготовки домашнего задания приложение 3. Сегодня на уроке мы продолжим изучение графов и познакомимся с еще одним методом решения задач. Одним из крупнейших математиков XVIII века был Леонард Эйлер. Он родился в швейцарском городе Базеле, где в 15 лет закончил университет, а в 17 лет получил степень магистра. Во время обучения в университете Эйлер брал уроки у одного из самых известных математиков того времени Иоганна Бернулли. Нет такой области математики, где Эйлер не сказал своего слова. Работал он сутками напролет в любой обстановке, опубликовал примерно работ. Он легко обнаруживал новые задачи и методы их решения. Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта года:. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может". Семь мостов обозначены буквами a, b, c, d, e, f, g ". Ученики в электронных тетрадях пробуют прорисовать возможные пути движения приложение 3 , сл. Один или два ученика вызываются к доске и тоже пробуют рисовать пути движения Презентация, сл. Так можно ли обойти все Кенигсбергские мосты, проходя только один раз через каждый из этих мостов? Простой путь решения задачи, казалось бы, такой: Но, очевидно, что даже в случае только семи мостов приходится делать слишком много таких проб. А при увеличении числа мостов такой способ решения практически совершенно немыслим. Да, кроме того, при одном и том же числе мостов задача изменяется в зависимости еще от расположения этих мостов. Поэтому, чтобы найти ответ, продолжим письмо Эйлера и посмотрим, какое же правило он нашел. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, - таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре - A, B, C, D. Ход решения задачи будем представлять в виде графа, где вершины - острова и берега, а ребра - мосты. Так, в нашем случае к участку A ведут пять мостов, а к остальным - по три моста". То есть нам нужно определить степень каждой вершины и узнать какие вершины четные, а какие нечетные. Подпишем степени вершин в кружочках. И посчитаем количество нечетных вершин. А, B, C, D. Если же из этих вершин две нечетные, то и тогда можно совершить переход, как это предписано, но только начало обхода непременно должно быть взято в одной из этих двух вершин, а конец обхода непременно должен быть во второй нечетной вершине. Если, наконец, больше двух нечетных вершин, то тогда такое движение вообще невозможно Из предыдущих рассуждений мы получаем общий прием решения каждой подобной задачи о мостах. Во всяком случае, мы можем сразу убедиться в возможности или невозможности решения. Вопрос разрешимости таких задач также входит в теорию графов. Графы, которые можно нарисовать указанным способом, называются Эйлеровыми графами. Проверка проходит сразу по окончании работы: У вас в тетрадях есть этот рисунок. Можно ли обойти все мосты, проходя по каждому из них только один раз? Ученики в электронных тетрадях пробуют прорисовать возможные пути движения приложение 3, сл. Дать время на поиск решения. Поучительная сторона этих задач состоит в исследовании, возможно или нет решение данной задачи, прежде чем приниматься за само решение. Мы еще раз убедились, что теория графов позволяет быстро и изящно решать задачи, которые весьма трудно решить другими методами и позволяет решить не только одну отдельно взятую задачу, но и находить методы решения целого класса задач. Можно ли фигуры, изображенные на рисунках, нарисовать одним росчерком? Школа цифрового века Педагогический университет. Подать заявку Личный кабинет. Главная Положение о фестивале и конкурсах Содержание: Хвостова Ольга Анатольевна , учитель информатики. Школа цифрового века Педагогический университет Вебинары Педагогический марафон Учительская книга.
Теория графов применяется при решении задач из многих предметных областей: Через город протекает река Прегеля. В городе - семь мостов, расположенных так, как показано на рисунке выше. С давних времен жители Кенигсберга бились над загадкой: Эту задачу решали и теоретически, на бумаге, и на практике, на прогулках - проходя по этим самым мостам. Разрешить проблему удалось знаменитому математику Леонарду Эйлеру. Причем, он решил не только эту конкретную задачу, но придумал общий метод решения подобных задач. При решении задачи о Кенигсбергских мостах Эйлер поступил следующим образом: Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют ГРАФОМ. Граф — это совокупность непустого множества вершин и связей между вершинами. Кружки называются вершинами графа, линии со стрелками — дугами, без стрелок — ребрами. Ориентированный граф кратко орграф — рёбрам которого присвоено направление. Неориентированный граф - это граф , в котором нет направления линий. Обозначим ученых вершинами графа и проведем от каждой вершины линии к четырем другим вершинам. Получаем 10 линий, которые и будут считаться рукопожатиями. На пришкольном участке растут 8 деревьев: Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому. Вершины графа - это деревья, обозначенный первой буквой названия дерева. В данной задача два отношения: Если в задаче сказано, что рябина выше лиственницы, то стрелку ставим от лиственницы к рябине и т. Получаем граф, на котором видно, что самое низкое дерево — клен, затем идут яблоня, лиственница, рябина, сосна, дуб, береза и тополь. У Наташи есть 2 конверта: Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо? GlobalLab Глобальная школьная лаборатория Присоединиться С чего начать? Мой профиль Мои награды Моё портфолио Мои черновики Мои проекты Мои группы Редактировать профиль Мои сообщения Выход. Решение задач с помощью графа. Мне нравится Проект нравится 20 участникам. Взвешенный граф — дуги или ребра имеют вес дополнительная информация. Решение задач с помощью графов: Ниже представлен разбор задач. Перейти к разделу Исследование.
https://gist.github.com/c9e59afcf1f4071ccf032d85eb0eff09
https://gist.github.com/3e3d7a93a0a7e471173fe5edc490486a
https://gist.github.com/de0b2e17a4d15099cd4ab3f5b90f1385