Решение задач с помощью графов

Разделы: Информатика, Конкурс «Презентация к уроку»


Презентация к уроку

Загрузить презентацию (1 МБ)


Цели:

Образовательные:

  • закрепить понятие графа и отработать навыки использования графов для решения задач;
  • проверить уровень усвоения понятия графа через умение применять имеющиеся знания для решения новых задач.

Развивающие:

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

Воспитательная:

  • воспитывать культуру общения на уроке, аккуратность, внимательность и взаимоуважение.

ПЛАН УРОКА

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

Проверка домашнего задания

2. Великий Эйлер и его задача

Кенигсбергские мосты (совместная работа с учителем)

Осознание, осмысление, обобщение

3. Задача о 15 мостах (самостоятельная работа)

Осознание, осмысление, обобщение

4. Итог урока

ХОД УРОКА

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

Презентация, сл.1

Домашнее задание. (Презентация, сл.2)

Применение теории графов. Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередач и т. п. - как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.

В качестве домашнего задания ученикам было предложено подготовить небольшие (объемом 1-2 слайда) презентации на тему "Применение графа".При проверке 2-3 ученика могут показать свои презентации классу на экране. (приложение 1, приложение 2)

Давайте вспомним основные понятия теории графов (Презентация, сл.3)

По ходу урока ученики работают с электронными тетрадями, которые можно подготовить в PowerPoint. Все необходимые зарисовки они делают с помощью средств рукописных заметок в режиме показа презентации. После урока презентацию со своими записями ученики сохраняют и уносят домой для подготовки домашнего задания (приложение 3)

2. Великий Эйлер и его задача

Учитель: Сегодня на уроке мы продолжим изучение графов и познакомимся с еще одним методом решения задач.

(Презентация, сл.4)

Одним из крупнейших математиков XVIII века был Леонард Эйлер. Он родился в швейцарском городе Базеле, где в 15 лет закончил университет, а в 17 лет получил степень магистра. Во время обучения в университете Эйлер брал уроки у одного из самых известных математиков того времени Иоганна Бернулли. Нет такой области математики, где Эйлер не сказал своего слова. Работал он сутками напролет в любой обстановке, опубликовал примерно 850 работ. Он легко обнаруживал новые задачи и методы их решения.

Кенигсбергские мосты

Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года:

"Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство... После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может".

(Презентация, сл.5)

"Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке, на котором A обозначает остров, а B, C и D - части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a, b, c, d, e, f, g ".

Ученики в электронных тетрадях пробуют прорисовать возможные пути движения (приложение 3, сл. 2). Один или два ученика вызываются к доске и тоже пробуют рисовать пути движения (Презентация, сл.5)

Так можно ли обойти все Кенигсбергские мосты, проходя только один раз через каждый из этих мостов?

Дать время на поиск решения.

Простой путь решения задачи, казалось бы, такой: сделать все возможные пробы таких переходов, т. е. перечислить все возможные пути, и затем рассмотреть, какой или какие из них удовлетворяют условиям вопроса. Но, очевидно, что даже в случае только семи мостов приходится делать слишком много таких проб. А при увеличении числа мостов такой способ решения практически совершенно немыслим. Да, кроме того, при одном и том же числе мостов задача изменяется в зависимости еще от расположения этих мостов.

Поэтому, чтобы найти ответ, продолжим письмо Эйлера и посмотрим, какое же правило он нашел. Итак,

"Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, - таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре - A, B, C, D."

(Презентация, сл.6)

Ход решения задачи будем представлять в виде графа, где вершины - острова и берега, а ребра - мосты.

"Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным - по три моста".

(Презентация, сл.7)

То есть нам нужно определить степень каждой вершины и узнать какие вершины четные, а какие нечетные. Подпишем степени вершин в кружочках. И посчитаем количество нечетных вершин. Нечетные вершины: А, B, C, D.

"Когда это определено, применяем следующее правило: если все вершины имеют четную степень, то тогда обход, о котором идет речь, возможен, и начать этот обход можно с любого участка. Если же из этих вершин две нечетные, то и тогда можно совершить переход, как это предписано, но только начало обхода непременно должно быть взято в одной из этих двух вершин, а конец обхода непременно должен быть во второй нечетной вершине. Если, наконец, больше двух нечетных вершин, то тогда такое движение вообще невозможно...".

Итак, используя правило Леонардо Эйлера мы можем сделать

ВЫВОД. Так как количество нечетных вершин в графе равно 4, а это > 2, то обойти все Кенигсбергские мосты, проходя только один раз через каждый из этих мостов нельзя.

(Презентация, сл.8) (приложение 3, сл.3)

Из предыдущих рассуждений мы получаем общий прием решения каждой подобной задачи о мостах. Во всяком случае, мы можем сразу убедиться в возможности или невозможности решения.

Это правило записано у вас в тетрадях:

(Презентация, сл.9) (приложение 3, сл.4)

1. Нарисовать граф, где вершины - острова и берега, а ребра - мосты.

2. Определить степень каждой вершины и подписать возле нее.

3. Посчитать количество нечетных вершин.

4. Обход возможен:

a. ЕСЛИ все вершины - четные, и его можно начать с любого участка.

b. ЕСЛИ 2 вершины - нечетные, но его нужно начать с одной из нечетных местностей.

5. Обход невозможен, если нечетных вершин больше 2.

6. Сделать ВЫВОД.

7. Указать Начало и Конец пути.

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

Задание: Графы,нарисованные у вас в тетрадях,необходимо достроить до Эйлеровых.

(Презентация, сл.10) (приложение 3, сл.5)

Проверка проходит сразу по окончании работы: либо учитель сам дорисовывает недостающие линии на доске, либо запускает анимацию.

А теперь, основываясь на нашем правиле, решим задачу о 15 мостах.

Задача о 15 мостах.

(Презентация, сл.11)

В некоторой местности через протоки переброшено 15 мостов.

У вас в тетрадях есть этот рисунок. Можно ли обойти все мосты, проходя по каждому из них только один раз?

Ученики в электронных тетрадях пробуют прорисовать возможные пути движения (приложение 3, сл.6).Дать время на поиск решения.

РЕШЕНИЕ:

Построим граф, где вершины - острова и берега, а ребра - мосты.

(Презентация, сл.12)

Нечетные вершины: D, E.

ВЫВОД: Так как количество нечетных вершин = 2, то обход возможен.

Его Начало может быть в местности D, а Конец в местности E.

4. Итог урока

Сегодня мы с вами познакомились еще с одним методом решения задач с помощью графов.

Поучительная сторона этих задач состоит в исследовании, возможно или нет решение данной задачи, прежде чем приниматься за само решение.

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

Домашнее задание: Можно ли фигуры, изображенные на рисунках, нарисовать одним росчерком? (решить с помощью графа)

(Презентация, сл.13) (приложение 3, сл.7)