"Недостаточно иметь хороший ум.
Главное – правильно его использовать"
Рене Декарт
Тема: "Решение задач с помощью графов"/
Цели:
- Образовательные:
- закрепить понятие графа и отработать навыки использования графов для решения задач;
- проверить уровень усвоения понятия графа через умение применять имеющиеся знания для решения новых задач.
- Развивающие:
- развивать логическое и творческое мышление учащихся, сообразительность, наблюдательность, интуицию и адекватность при оценке работы одноклассника;
- формировать активный познавательный интерес к предмету.
- Воспитательная:
- воспитывать культуру общения на уроке, аккуратность, внимательность и взаимоуважение.
Оборудование:
- Карточка для разминки и домашнего задания <Приложение 1>.
- Индивидуальная карточка для работы на уроке <Приложение2>.
ПЛАН УРОКА
I. Оргмомент
II. Великий Эйлер и его задача
Кенигсбергские мосты
(совместная работа с учителем)
Осознание, осмысление, обобщение
Задача о 15 мостах
(совместная работа с учителем)
Осознание, осмысление, обобщение
В поисках сокровищ
(индивидуальная работа на карточках с взаимопроверкой) ОЦЕНКА
Стандартное применение
III. Вычерчивание фигур одним росчерком (индивидуальная работа на карточках с проверкой учителя) ОЦЕНКА
Творческое применение
IV. Домашнее задание (индивидуальная работа в тетрадях с проверкой учителя) ОЦЕНКА
Творческое применение
V. Итог урока
ХОД УРОКА
I. Организационный момент
Сегодня на уроке мы продолжим изучение графов и познакомимся с еще одним методом решения задач. В течение урока вы будете выполнять задания, за которые можно заработать баллы. Максимальное количество баллов за урок – 15 баллов.
II. Великий Эйлер и его задача
Одним из крупнейших математиков XVIII века был Леонард Эйлер. Он родился в швейцарском городе Базеле, где в 15 лет закончил университет, а в 17 лет получил степень магистра. Во время обучения в университете Эйлер брал уроки у одного из самых известных математиков того времени Иоганна Бернулли и подружился с его сыновьями Даниилом и Николаем, которые были приглашены для работы в только что созданную Петербургскую академию наук. Через год по их рекомендации туда же был приглашен и двадцатилетний Эйлер. Этот выбор оказался одним из самых удачных для России. Нет такой области математики, где Эйлер не сказал своего слова. Работал он сутками напролет в любой обстановке, опубликовал примерно 850 работ. Он легко обнаруживал новые задачи и методы их решения. Даже историю возникновения теории графов можно проследить по переписке великого ученого.
1. Кенигсбергские мосты
Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года:
"Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство... После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может".
"Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке [рис.1], на котором A обозначает остров, а B, C и D – части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a, b, c, d, e, f, g ".
Так можно ли обойти все Кенигсбергские мосты, проходя только один раз через каждый из этих мостов?
Простой путь решения задачи, казалось бы, такой: сделать все возможные пробы таких переходов, т. е. перечислить все возможные пути, и затем рассмотреть, какой или какие из них удовлетворяют условиям вопроса. Но, очевидно, что даже в случае только семи мостов приходится делать слишком много таких проб. А при увеличении числа мостов такой способ решения практически совершенно немыслим. Да, кроме того, при одном и том же числе мостов задача изменяется в зависимости еще от расположения этих мостов.
Поэтому, чтобы найти ответ, продолжим письмо Эйлера и посмотрим, какое же правило он нашел. Итак,
"Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, – таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре – A, B, C, D."
Ход решения задачи будем представлять в виде графа, где вершины – острова и берега, а ребра – мосты.
"Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста".
То есть нам нужно определить степень каждой вершины и узнать какие вершины четные, а какие нечетные. Подпишем степени вершин в кружочках. И посчитаем количество нечетных вершин. Нечетные вершины: А, B, C, D.
"Когда это определено, применяем следующее правило: если все вершины имеют четную степень, то тогда обход, о котором идет речь, возможен, и начать этот обход можно с любого участка. Если же из этих вершин две нечетные, то и тогда можно совершить переход, как это предписано, но только начало обхода непременно должно быть взято в одной из этих двух вершин, а конец обхода непременно должен быть во второй нечетной вершине. Если, наконец, больше двух нечетных вершин, то тогда такое движение вообще невозможно...".
Итак, используя правило Леонардо Эйлера мы
можем сделать
ВЫВОД. Так как количество нечетных вершин в
графе равно 4, а это > 2, то обойти все
Кенигсбергские мосты, проходя только один раз
через каждый из этих мостов нельзя.
Из предыдущих рассуждений мы получаем общий прием решения каждой подобной задачи о мостах. Во всяком случае, мы можем сразу убедиться в возможности или невозможности решения. Это правило записано у вас на карточках:
1. Нарисовать граф, где вершины –
острова и берега, а ребра – мосты.
2. Определить степень каждой вершины
и подписать возле нее.
3. Посчитать количество нечетных вершин.
4. Обход возможен:
a. ЕСЛИ все вершины – четные, и его можно начать с любого участка.
b. ЕСЛИ 2 вершины – нечетные, но его нужно начать с одной из нечетных местностей.
5. Обход невозможен, если нечетных
вершин больше 2.
6. Сделать ВЫВОД.
7. Указать Начало и Конец пути.
А теперь, основываясь на нашем правиле, решим задачу о 15 мостах.
2. Задача о 15 мостах
В некоторой местности через протоки переброшено 15 мостов.
У вас в карточках есть этот рисунок. Можно ли обойти все мосты, проходя по каждому из них только один раз?
РЕШЕНИЕ:
Построим граф, где вершины – острова и берега, а ребра – мосты.
Нечетные вершины: D, E.
ВЫВОД: Так как количество нечетных
вершин = 2, то обход возможен.
Его Начало может быть в местности D,
а Конец в местности E.
III. В поисках сокровищ
А сейчас мы отправимся на поиски сокровищ. У вас на индивидуальных карточках изображен план подземелья, в одной из комнат которого скрыты богатства рыцаря. Чтобы безопасно проникнуть в эту комнату, надо, войти через определенные ворота в одну из крайних комнат подземелья, пройти последовательно через все 29 дверей, выключая сигнализацию тревоги. Проходить дважды через одни и те же двери нельзя. Определить номер комнаты в которой скрыты сокровища и ворота через которые нужно войти?
РЕШЕНИЕ:
Для решения нужно построить граф, где вершины – номера комнат, а ребра – двери. Вершины уже построены рядом с планом подземелья. Вам нужно построить все ребра и дать ответ.
Нечетные вершины: 6, 18.
ВЫВОД: Так как количество нечетных вершин = 2, то безопасно проникнуть в комнату с сокровищами можно.
ОТВЕТ: Начать путь нужно через ворота В, а закончить в комнате № 18.
После выполнения задания, учащиеся
обмениваются карточками, и оценивают работу друг
друга (парная работа).
Оценивание проводится по балльной системе.
Правильный ход решения и ответ будет дан на
доске. За каждый пункт решения будет
выставляться 1 балл.
Общая сумма баллов за это задание = 5 баллов.
- 1 балл – правильно построенный граф;
- 1 балл – правильно найденные нечетные вершины;
- 1 балл – правильно сделан вывод;
- 1 балл – правильно указано начало пути;
- 1 балл – правильно указан конец пути.
IV. Вычерчивание фигур одним росчерком
Итак, мы с вами сегодня учились решать задачи о
прохождении по всем мостам при условии, что нужно
на каждом побывать один раз, и увидели, что на
языке теории графов каждая такая задача выглядит
как задача изображения "одним росчерком"
графа, представленного на рисунке.
Теперь нам нетрудно будет разобраться и
показать, какую из любых данных фигур можно
вычертить одним росчерком, без повторения линий,
а какую нет. Каждую из задач подобного рода можно
свести к разобранной уже нами Эйлеровой задаче о
мостах.
Например, на рисунке изображена птица.
Взяв за вершины графа точки пересечения линии, получим 7 вершин, только две из которых имеют нечетную степень.
Поэтому в этом графе существует эйлеров путь, а значит, его (т.е. птицу) можно нарисовать одним росчерком.
Нечетные вершины: две.
ВЫВОД: Так как количество нечетных вершин = 2, то птицу можно нарисовать одним росчерком. Начать путь нужно в одной нечетной вершине, а закончить в другой.
Задание. Можно ли фигуры, изображенные на рисунках, нарисовать одним росчерком? Решить с помощью графа.
На обратной стороне ваших индивидуальных
карточек нарисованы по 2 рисунка. Вам нужно будет
сделать вывод, можно ли нарисовать эти рисунки
одним росчерком и если это возможно, то указать
начало и конец пути и попробовать нарисовать
рисунок рядом с образцом.
Общая сумма баллов за это задание = 6 баллов.
1 балл – правильно найденные нечетные вершины;
1 балл – правильно сделан вывод;
1 балл – нарисован рисунок;
IV. Домашнее задание (4 балла)
(На карточках). Можно ли фигуру, изображенную на рисунке, нарисовать одним росчерком? Решить с помощью графа.
 |
 |
V. Итог урока
Сегодня мы с вами познакомились еще с одним
методом решения задач с помощью графов.
Поучительная сторона этих задач состоит в
исследовании, возможно или нет решение данной
задачи, прежде чем приниматься за само решение.
Мы еще раз убедились, что теория графов позволяет
быстро и изящно решать задачи, которые весьма
трудно решить другими методами и позволяет
решить не только одну отдельно взятую задачу, но
и находить методы решения целого класса задач.