Программа курса предпрофильной подготовки Решение задач методом графов (9 классы)

Муниципальное бюджетное общеобразовательное учреждение

«Средняя общеобразовательная школа №5 г. Льгова»

Курской области

«Согласовано» «Утверждено»

Руководитель МО Директор школы

_________/Языкова С.А./ _________ /Жеромский О.В./

протокол № __ от

от __________ 2015 г. Приказ № ___ от _____ 2015 г.

Рассмотрено на заседании

педагогического совета

протокол № ___ от _________ 2015 г.

ПРОГРАММА ЭЛЕКТИВНОГО КУРСА

предпрофильной подготовки обучающихся 9-х классов

в 2015-2016 учебном году

РЕШЕНИЕ ЗАДАЧ МЕТОДОМ ГРАФОВ

Составитель:

Агеева Наталья Валентиновна,

учитель математики и информатики,

высшая квалификационная категория

2015 год

г. Льгов

Курской области

«Да, что ты знаешь в детстве - знаешь на всю жизнь,

но и чего не знаешь в детстве - не знаешь на всю жизнь»

М.Цветаева

Элективный курс «Решение задач методом графов»

(в рамках предпрофильной подготовки обучающихся 9 класса)

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

Предлагаемый курс носит интегративный характер, так как в нем представлена естественная реализация межпредметных связей математики с информатикой. Его цель - подготовить учащихся к осознанному выбору сферы деятельности, а также познакомить учащихся с теорией графов, показать ее практическую направленность и применение в жизни, расширить кругозор обучающихся по темам «Представление информации» и «Моделирование». Изучив данный курс в 9 классе, учащиеся более успешно будут осваивать одну из наиболее сложных тем информатики «Программирование», а также, смогут показать высокие результаты при прохождении итоговой аттестации по информатике.

Содержание курса ориентировано на самые занимательные разделы математики и информатики, на изучение которых в рабочих программах, как правило, закладывается не слишком много времени. Но тема "Теория графов" имеет ярко выраженную, прикладную направленность. На простых примерах обучающимся показывается, как можно применить язык теории графов к решению различных практических задач. Методы теории графов завоевали признание не только математиков, но и инженеров, экономистов, психологов, лингвистов, биологов, химиков. Использование языка и методов теории графов часто ускоряет решение практических задач, упрощает расчеты, повышает эффективность научной, инженерной и конструкторской деятельности. Графы эффективно используются в теории планирования и управления, теории расписаний, социологии, математической лингвистике, экономике, биологии, медицине. Широкое применение находят графы в таких областях прикладной математики, как программирование, теория конечных автоматов, электроника, в решении вероятностных и комбинаторных задач. Теория графов быстро развивается, находит все новые приложения и ждет молодых исследователей.

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

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

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

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

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

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

Задачи курса

• овладение конкретными математическими знаниями, необходимыми для применения в практической деятельности, для изучения смежных дисциплин;

• познакомиться с нетрадиционными приёмами и методами решения задач;

• показать связь математических методов с наукой и техникой через теорию графов;

• повысить мотивацию обучения;

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

• создать положительную мотивационную базу для самостоятельного изучения теории графов;

• формирование у обучающихся интереса к профессиям, связанным с информатикой и ее приложениями.

В результате изучения курса «Решение задач методом графов» учащиеся должны:

• знать элементарные основы теории графов;

• уметь применить теоретические знания при решении задач;

• получить навыки решения нестандартных задач;

• повысить математическую культуру и качество знаний.

Содержание курса.

Понятие графа и его элементов. Примеры графов. Полный граф. Четность вершины графа. Основные теоремы теории графов.

• Если все вершины графа четные, граф можно начертить одним росчерком. Порядок движения любой.

• Граф с двумя нечетными вершинами можно начертить одним росчерком, начиная движение с одной и заканчивая на другой нечетной вершине.

• Граф с более чем двумя нечетными вершинами нельзя начертить одним росчерком.

Графы Эйлера.

Задачи о лабиринтах. Методы решения задач о лабиринтах.

Деревья как класс графов.

Программа курса состоит из пяти разделов и рассчитана на обучающихся 9-х классов. На изучение курса предполагается 8 часов в рамках предпрофильной подготовки обучающихся основной школы МБОУ СОШ №5 г. Льгова в 2015-2016 учебном году.

Формы и методы обучения.

Наряду с традиционными формами и методами, в преподавании курса предусмотрено применение таких форм занятий, как дискуссия, обсуждение, «мозговой штурм. В преподавании курса опорными станут метод проектов, творческих и практических заданий по курсу.

Учебно-тематический план курса

№ п/п

Тема занятия

Кол-во часов

1

Сведения из истории графов. Граф и его элементы.

1

2-3

Графы Эйлера. Задачи о мостах.

Рисование фигур единым росчерком.

2

4

История лабиринтов. Способы прохождения лабиринта.

1

5-6

Понятие дерева в теории графов, применение деревьев в решении различных задач.

2

7-8

Графы и логические задачи.

2

всего

8 часов

Тема 1. Граф и его элементы.

Теория графов - это направление математики, особенностью которой является геометрический подход к изучению математических объектов. Она пересекается со многими направлениями теории множеств, комбинаторной математики, алгебры, геометрии, теории игр, математической логики и другими математическими дисциплинами.

На практике этой теорией пользуется инженер при вычеркивании электрических схем, химик при анализе валентных связей в сложных молекулах, историк при вычерчивании родственных связей в генеалогических деревьях, социолог при анализе иерархии подчиненности в огромных корпорациях, военачальник при вычерчивании коммуникаций, по которым доставляются подкрепления, и другие.

В каждом их этих примеров фигурирует схема, состоящая из точек, соединенных между собой линиями. Первым применил графы для решения математических задач великий математик Леонард Эйлер(1707-1783). Эйлер родился и вырос в Швейцарии, а работал в России и в Германии.

А слово «граф» первым стал использовать английский математик Джеймс Дж. Сильвестр. Рассмотрим ту самую задачу, для решения которой Л. Эйлер впервые применил графы, - это знаменитая задача о мостах города Кенигсберга (сейчас это Калининград).

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

Понятие графа

Рассмотрим две задачи.

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

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

Теперь сразу видно, что долететь с Земли до Марса нельзя.

Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4x4 убрать угловые клетки.

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

Решение: Занумеруем последовательно клетки доски:

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

Мы рассмотрели две непохожие задачи. Однако решения этих двух задач объединяет общая идея - графическое представление решения. При этом и картинки, нарисованные для каждой задачи, оказались похожими: каждая картинка - это несколько точек, некоторые из которых соединены линиями.

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

Другое замечание касается вида графа. Попробуйте проверить, что граф для одной и той же задачи можно нарисовать разными способами; и наоборот, для разных задач можно нарисовать одинаковые по виду графы. Здесь важно лишь то, какие вершины соединены друг с другом, а какие - нет. Например, граф для задачи 1 можно нарисовать по-другому:

Такие одинаковые, но по-разному нарисованные графы, называются изоморфными.

Задача №3. На квадратной доске 3x3 расставлены 4 коня так, как показано на рис.1. Можно ли сделав несколько ходов конями, переставить их в положение, показанное на рис.2?

Решение. Занумеруем клетки доски, как показано на рисунке:

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

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

Задача №4. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3. Можно ли долететь по воздуху из города 1 в город 9 ?

Решение. Поставив в соответствие каждому городу точку и соединив точки линией, если сумма цифр делится на 3, получим граф, в котором цифры 3, 5, 9 связаны между собой, но не связаны с остальными. Значит долететь из города 1 в город 9 нельзя.

Степени вершин и подсчет числа ребер графа

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

С понятием степени вершины связана одна из основных теорем теории графов -теорема о четности числа нечетных вершин. Докажем ее мы немного позднее, а сначала для иллюстрации рассмотрим задачу.

Задача 5. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра - провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа - 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится равным 15*5/2 = 37,5. Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным.

Ответ. Соединить телефоны таким образом невозможно.

Теорема: Любой граф содержит четное число нечетных вершин.

Доказательство: Количество ребер графа равно половине суммы степеней его вершин. Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной. А это возможно только в том случае, если граф содержит четное число нечетных вершин.

Задача №6. В государстве 100 городов к из каждого города выходит 4 дороги. Сколько всего дорог в государстве.

Решение. Подсчитаем общее количество выходящих городов дорог - 100 ^. 4 = 400. Однако при таком подсчете каждая дорога посчитана 2 раза - она выходит из одного города и входит в другой. Значит всего дорог в два раза меньше, т.е. 200.

4. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 - по 4 друга, а 10 - по 5 друзей ?

Ответ. Нет (теорема о четности числа нечетных вершин).

Задача №7. У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей ?

Ответ. Нет, не может.

Задача №8. Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?

Решение. Подсчитаем число городов. Число дорог равно числу городов х, умноженному на 3 (число выходящих из каждого города дорог) и разделенному на 2 (см. задачу 3). Тогда 100 = Зх/2 => Зх=200, чего не может быть при натуральном х. Значит 100 дорог в таком государстве быть не может.

Связность графа

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

Задача 9. В стране Семерка 15 городов, каждый из городов соединен дорогами не менее, чем с семью другими. Докажите, что из каждого города модно добраться в любой другой.

Доказательство: Рассмотрим два произвольных А и В города и допустим, что между ними нет пути. Каждый из них соединен дорогами не менее, чем с семью другими, причем нет такого города, который был бы соединен с обоими рассматриваемыми городами (в противном случае существовал бы путь из A в B). Нарисуем часть графа, соответствующую этим городам:

Теперь явно видно, что мы получили не менее различных 16 городов, что противоречит условию задачи. Значит утверждение доказано от противного.

Если принять во внимание предыдущее определение, то утверждение задачи можно переформулировать и по-другому: "Доказать, что граф дорог страны Семерка связен"

Несвязный граф имеет вид нескольких "кусков", каждый из которых - либо отдельная вершина без ребер, либо связный граф. Пример несвязного графа вы видите на рисунке:

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

Задача 10. В Тридевятом царстве только один вид транспорта - ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний - одна, а из всех остальных городов, - по 20. Докажите, что из столицы можно долететь в город Дальний.

Доказательство: Понятно, что если нарисовать граф ковролиний Царства, то он может быть несвязным. Рассмотрим компоненту связности, которая включает в себя столицу Царства. Из столицы выходит 21 ковролиния, а из любых других городов, кроме города Дальний - по 20, поэтому, чтобы выполнялся закон о четном числе нечетных вершин необходимо, чтобы и город Дальний входил в эту же самую компоненту связности. А так как компонента связности - связный граф, то из столицы существует путь по ковролиниям до города Дальний, что и требовалось доказать.

Задача №11. В шахматном турнире по круговой системе, по которой каждый участник встречается с каждым, участвуют 7 школьников. Известно, что в настоящий момент Ваня сыграл 6 партий, Толя - 5,Леша и Дима -по 3, Семен и Илья - по 2, Женя- 1. С кем играл Леша?

Решение. Поставим в соответствие каждому игроку точку плоскости - вершину графа. Если два игрока встретились между собой, то соединим соответствующие вершины линией - ребром графа. Таким образом, мы построим граф встреч игроков. Пусть в этом графе вершина 1 соответствует Ване, вершина 2 - Толе, вершина 3 - Леше, вершина 4 - Диме, вершина 5 - Семену, вершина 6 - Илье и вершина 7 - Жене.

Поскольку Ваня провел 6 встреч, то степень вершины 1 равна 6, и эту вершину соединим со всеми вершинами графа. Степень вершины 2 должна быть равна 5, так как Толя провел 5 встреч. Из вершины 2 уже выходит 1 ребро. Оставшиеся 4 ребра проведем из 2 в вершины 3, 4, 5 и 6, поскольку вершина 7, степень которой равна 1 (Женя провел одну встречу), соединена уже ребром с вершиной 1.

Теперь вершины 5 и 6 соответствующие Семену и Илье, должны иметь степень 2, так как эти участники провели по две встречи. Вершины 3 и 4 соединим ребром, поскольку они должны иметь степени 3, так как Леша и Дима провели по 3 встречи.

Это означает, что граф, описывающий встречи участников, имеет вид:

Рис.3. граф, описывающий встречи участников.

Поэтому Леша, которому соответствует вершина 3, встретился с Ваней, Толей и Димой, которым соответствуют вершины 1, 2 и 4.

Задача №12. В стране из каждого города выходит 100 дорог и из каждого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь из любого города можно добраться до любого другого.

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

Тест по теме №1 «Граф и его элементы»

1. Изобразите с помощью графа договорные отношения между предприятиями А, Б, В, Г, Д, Е, если к рассматриваемому моменту:

предприятие А установило договорные отношения со всеми другими предприятиями;

Б установило с Г и Д;

В установило со всеми предприятиями, кроме предприятия Е.

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

1. 1. 5 вершин и 10 ребер

   2. 6 вершин и 12 ребер

   3. 6 вершин и 11 ребер

2. Среди семи стран установлены экономические отношения, причем каждая страна имеет экономические договоры с каждой другой страной. Изобразите в виде графа результат установленных экономических отношений. Сколько ребер имеет полученный граф?

   1. 49

   2. 36

   3. 21

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

   1. 1

   2. 2

   3. 4

   

4. Между четырьмя государствами были подписаны двухсторонние договорные обязательства таким образом, как это отображено с помощью графа на рисунке. Каждый договор был подписан президентами обоих договаривающихся государств. Сколько всего подписей фигурировало в договорах, если каждый договор подписывался в двух экземплярах?

   1. 18 подписей

   2. 10 подписей

   3. 20 подписей

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

   1. 3 закономерность

   2. 1 закономерность

   3. 2 закономерность

6. Можно ли начертить граф, имеющий всего две нечетные вершины, не отрывая карандаш от бумаги? И в какой закономерности об этом говориться?

   1. да , 7 закономерность

   2. нет, 4 закономерность

   3. да , 6 закономерность

7. Какие из указанных в графе на рисунке маршрутов являются путем?

   1. АВГВД

   2. АВГ

   3. АВДАБ

   4. АБВАД

   

8. Используя рисунок предыдущей задачи, укажите сколько существует путей из вершины А в вершину Д.

   1. 4

   2. 3

   3. 5

9. Какие из указанных циклов являются простыми?

   1. АВГА

   2. ЕБВГБЕ

   3. ДВАГВД

   4. ЕБАГЕ

10. Определите, связный или несвязный граф изображен на рисунке:

Тема 2. Графы Эйлера. Задачи о мостах.

Рисование фигур единым росчерком.

Графы Эйлера

Теория графов - наука сравнительно молодая: во времена Ньютона такой науки еще не существовало, хотя и были в ходу «генеалогические деревья», представляющие собой разновидности графов. Первая работа по теории графов принадлежит Леонарду Эйлеру, и появилась она в 1736 году в публикациях петербургской Академии наук. Начиналась эта работа с рассмотрения следующей задачи:

Город Кенигсберг (ныне Калининград) расположен на берегах и двух островах реки Прегель (Преголи). Различные части города были соединены семью мостами, как показано на рисунке. В воскресные дни горожане совершают прогулки по городу. Можно ли выбрать такой маршрут, чтобы пройти один и только один раз по каждому мосту и потом вернуться в начальную точку пути?

Прежде чем рассмотреть решение данной задачи, мы введем понятие «Эйлеровы графы .

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

Фигура эта, такая простая на вид, оказывается, имеет интересную особенность. Если мы начнем движение из вершины В, то у нас это обязательно получится. А что будет, если мы начнем движение из вершины А? Легко убедиться, что обвести линию в этом случае нам не удается: у нас всегда будет оставаться не пройденные ребра, добраться до которых уже невозможно.

.

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

Графы, начерченные на рис.6 также можно начертить одним росчерком пера.

Теперь попробуйте вычертить одним росчерком граф, изображенный на рис.7

Вам это сделать не удалось! Почему? Вы не можете найти нужную вершину? Нет! Дело не в этом. Этот граф вообще нельзя вычертить одним росчерком пера.

Проведем рассуждения, которые убедят нас в этом. Рассмотрим узел А. Из него выходят три вершины. Начнем вычерчивать граф с этой вершины. Чтобы пройти по каждому из этих ребер, мы должны выйти из вершины А по одному из них, в какой - то момент обязательно вернуться в него по второму и выйти по третьему. А вот снова войти уже не сможем! Значит, если мы начнем вычерчивание с вершины А, то закончить в нем не сможем.

Допустим теперь, что вершина А не является началом. Тогда в процессе вычерчивания мы должны войти в него по одному из ребер, выйти по другому и снова вернуться по третьему. А так как выйти из него мы не сможем, то вершина А в этом случае должен являться концом.

Итак, вершина А должен быть или началом, или конечным узлом вычерчивания.

Но про три другие вершины нашего графа можно сказать то же самое. Но ведь и начальной вершиной вычерчивания может быть только одна вершина, и конечной вершиной также может быть только одна вершина! А значит, вычерчивать этот граф одним росчерком невозможно.

Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым (рис.6).

Такими графы названы в честь учёного Леонарда Эйлера.

Закономерность1. (вытекает из рассмотренной нами теоремы).
Невозможно начертить граф с нечетным числом нечетных вершин.
Закономерность 2.

Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.
Закономерность 3.

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

Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».
Фигура (граф), которую можно начертить, не отрывая карандаш от бумаги, называется уникурсальной.

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

Граф называется несвязным, если это условие не выполняется.

рис.7рис.8

На рисунке 7, очевидно, изображен несвязный граф. Если, например, на рисунке между вершинами Д и Е провести ребро, то граф станет связным. (рис.8)
Такое ребро в теории графов (после удаления которого граф из связного превращается в несвязный) называется мостом.

Примерами мостов на рисунке 7 могли бы служить ребра ДЕ, A3, ВЖ и др., каждое из которых соединяло бы вершины «изолированных» частей графа.(рис.8)

Несвязный граф состоит из нескольких «кусков». Эти «куски» называются компонентами связности графа. Каждая компонента связности является, конечно, связным графом. Отметим, что связный граф имеет одну компоненту связности.

ТЕОРЕМА.

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

Доказательство:

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

Вернемся теперь к задаче о кенигсбергских мостах.

Обсуждение задачи. Обозначим различные части города буквами А, В, С, Д, а мосты - буквами а, b, c, d, e, f, g - мосты, соединяющие соответствующие части города. В этой задаче существуют лишь переходы через мосты: переходя через любой мост, мы всегда из одной части города попадаем в другую, И, наоборот, переходя из одной части города в другую, мы непременно пройдем по мосту. Поэтому, изобразим план города в виде графа, вершины которого А, В, С, Д (рис.8) изображают отдельные части города, а ребра a, b, c, d, e, f, g - мосты, соединяющие соответствующие части города. Ребра зачастую оказываются удобнее изображать удобнее не прямолинейными отрезками, а криволинейными - «дугами».

Если бы существовал маршрут, удовлетворяющий условию задачи, то существовал бы замкнутый непрерывный обход этого графа, проходящий один раз по каждому ребру. Иными словами этот граф должен вычерчиваться одним росчерком. Но это невозможно - какую бы вершину мы ни выбрали за исходную, нам придется проходить через остальные вершины, и при этом каждому «входящему» ребру (мосту, по которому мы вошли в эту часть города) будет соответствовать «выходящее» ребро мост, которым мы и воспользуемся затем, чтобы покинуть эту часть города): число ребер, входящих в каждую вершину, будет равно числу ребер, выходящих из нее, т. е. общее число ребер, сходящихся в каждой вершине, должен быть четным. Наш граф этому условию не удовлетворяет, и поэтому требуемого маршрута не существует.

Задача №3 Имеется группа островов, соединенных мостами так, что от каждого острова можно добраться до любого другого. Турист обошел все острова, пройдя по каждому мосту розно 1 раз. На острове Троекратном он побывал трижды. Сколько мостов ведет с Троекратного, если турист

а) не с него начал и не на нем закончил?
б) с него начал, но не на нем закончил?
в) с него начал и на нем закончил?

Задача №4. На рисунке изображен парк, разделенный на несколько частей заборами. Можно ли прогуляться по парку и его окрестностям так, чтобы перелезть через каждый забор розно 1 раз?

Задача №5. Попробуйте, не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии, вычертить следующие фигуры.

Биография Л. Эйлера

Леонард Эйлер (1707-1783) родился в Базеле, в Швейцарии. Его отец, Пауль Эйлер, был сельским пастором. Первые уроки Леонард получил от отца, а учась в последних классах гимназии, он посещал лекции по математике в Базельском университете, которые читал Иоганн Бернулли. Вскоре Эйлер самостоятельно изучает первоисточники, а по субботам Бернулли беседует с талантливым студентом - обсуждает неясные места. Леонард дружит с его сыновьями, особенно с Даниилом.

В 1723г. Эйлер получил степень магистра искусств. В 1727 г. он предпринял попытку занять кафедру физики в родном университете, но ему это не удалось. Отказ способствовал принятию решения ехать в Петербург, куда его звали уже работающие там Даниил и Николай Бернулли.

Именно в Петербурге Эйлер сложился как великий ученый. Критически переосмыслив работы Ферма по теории чисел и труды Лейбница и Ньютона по математическому анализу и механике, он нашел свой собственный путь в науке. Почти все его книги и статьи были опубликованы позднее, но главное в научной судьбе Эйлера решилось в его первое петербургское десятилетие.

К 35 годам, из-за постоянных перегрузок, Эйлер успел основательно подорвать свое здоровье. Достаточно сказать, что он во время долгих вычислении перенапряг зрение и ослеп на один глаз. Правда, сам Эйлер отнесся к этому событию философски: «Теперь я меньше буду отвлекаться от занятий математикой». В 1740г. он оказался в тяжелой депрессии, что было связано не только со здоровьем, но и с постоянным напряжением из-за неустойчивости политической жизни в России. К тому времени появляется возможность переехать в Берлин, куда его приглашает король Фридрих II, и Эйлер подает заявление об отставке.

В берлинский период Эйлер написал множество работ. Это были не просто трубы по математике, но и по физике и астрономии: «Введение в анализ бесконечных» (1748), «Морская наука» (1749), «Теория движения Луны» (1753)и др. Эйлер также подготовил к изданию трехтомное «Интегральное исчисление». Ученый проявил себя и как популяризатор науки: им были написаны знаменитые «Письма к немецкой принцессе», в которых в популярной форме Эйлер изложил всю современную физику.

Со временем ситуация в России изменилась, на трон взошла Екатерина II, которой очень хотелось вернуть великого ученого. После переговоров Эйлер в 1766г. возвращается в Россию.

Вскоре после приезда ученый полностью лишается зрения, но не прекращает работать. Приглашенный императрицей окулист удалил катаракту на одном глазу, но предупредил, что перегрузка неминуемо приведет к возвращению слепоты. Но разве мог Эйлер «не вычислять»? Уже через несколько дней после операции он снял повязку. И вскоре потерял зрение снова. На этот раз - окончательно. Впрочем, Эйлер мог вполне разборчиво писать на черной доске мелом. Несмотря на потерю зрения, работоспособность Эйлера не снизилось, даже, наоборот: во второй петербургский период им написано половина всех его трудов. Умер Эйлер в 1783 г., оставив огромное научное наследие, которое до сих пор издается в Швейцарии. Похоронен в Петербурге.

У Эйлера было пятеро детей: три сына и две дочери. После смерти Эйлера все его потомки остались в России.

Эйлер внес огромный вклад в развитие математики. Его именем названо большое количество математических объектов: постоянная Эйлера, уравнения Эйлера, числа Эйлера, подстановки Эйлера, метод ломанных Эйлера, круги Эйлера, функции Эйлера, прямая Эйлера, формула Эйлера, эйлеровы интегралы, эйлеровы характеристики, графы Эйлера.

Задачи для самостоятельного изучения:

1. На рисунке схематически изображена речная сеть Москвы: река Москва, реки Яуза и Сходня, Химкинском водохранилище, острова. Через реки переброшены мосты, связывающие различные участки суши. Можно ли обойти за один раз все мосты на рисунке, проходя через каждый не более одного раза?

2. Контрабандист решил побывать во всех странах Европы, пересекая границу каждой только однажды. Возможно ли такое путешествие?

Тема 3. История лабиринтов.

Происхождение задач о лабиринтах относится к глубокой древности и теряется во мраке времен.

Слово «лабиринт» (греческое) означает «ходы в подземельях».

Решению задачи о лабиринтах предпосылаются исторические справки - чтобы показать интерес к этой задаче и дать наглядное представление о существовавших и существующих лабиринтах.

Возможен ли безвыходный лабиринт?

Задача о прохождении лабиринта приобретает практический интерес, поскольку устройство линий электропередач, канализации, сетей дорог, каналов и т.д. - все это более или менее сложные лабиринты.

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

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

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

Решение (т.е. маршрут, ведущий к цели) каждого лабиринта может быть найдено одним их трех сравнительно простых методов.

• Первый метод - МЕТОД ПРОБ И ОШИБОК. Выбирайте любой путь, а если он заведет вас в тупик, то возвращайтесь назад и начинайте все сначала.

• Второй метод - МЕТОД ЗАЧЕРКИВАНИЯ ТУПИКОВ. Начнем последовательно зачеркивать тупики, т.е. маршруты, не имеющие ответвлений и заканчивающиеся перегородкой. Незачеркнутая часть коридоров будет выходом или маршрутом от входа к выходу или к центру.

• Третий метод - ПРАВИЛО ОДНОЙ РУКИ. Оно состоит в том, что по лабиринту надо двигаться, не отрывая одной руки (правой или левой) от стены.

Задача №1

1. Убедитесь в том, что, войдя в лабиринт, изображенный на рисунке, можно, касаясь правой рукой стены, дойти до центра и вернуться.

2. Убедитесь, что из любой точки лабиринта в его центр можно попасть, пользуясь правилом одной руки.

3. Как можно достать из муравейника зернышко.

Задача №2

Это лабиринт английского короля Вильгельма III, состоит из аллей и изгородей. Нужно пройти в центр к деревьям и скамейкам под ними.

Задача №3

Найдите путь к беседке,

расположенной в парке.

Тема 4. Понятие дерева в теории графов.

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

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

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

Данная тема предполагает задания поискового и исследовательского характера.

Задача №1. Для отправки поздравления есть конверты трех видов, на которые клеится одна из двух марок и в которые вкладывается одна из четырех открыток. Сколько существует способов сделать поздравления по почте?

Решение. Занумеруем конверты, марки и открытки. Выбор одного конверта из трех можно изобразить следующим графом 6:

Выбор одного конверта Наклеивание марок

На каждый из выбранных конвертов можно наклеить одну из двух марок. Это изображается следующим граф 7.

Получилось 6 вариантов выбора конверта с маркой. В каждый из таких конвертов с маркой можно вложить одну из 4 открыток:

Нижние вершины графа задают варианты рассылки поздравлений.

Ответ: 24.

Задача №2. Меню

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

Решение.

1 2 3 4 5 6 7 8 9 10 11 12

Морс чай морс чай морс чай морс чай морс чай морс чай

Рыба котлета рыба котлета рыба котлета

Борщ гор.суп щи

Ответ: 12 вариантов.

Задача №3. Сколькими способами можно рассадить в ряд на три стула трех учеников? Выписать все возможные случаи.

Решение этой задачи удобнее всего представить в виде дерева. За его корневую вершину возьмем произвольную точку плоскости О.

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

Посадив на первый стул ученика А, на второй стул можно посадить ученика В или С. Если же на первый стул сядет ученик В, то на второй можно посадить А или С. А если на первый стул сядет С, то на второй можно будет посадить А или В. Это соответствует на схеме двум вет­вям, исходящим из каждой вершины первого уровня:

Очевидно, что третий стул в каждом случае займет оставшийся ученик. Это соответствует одной ветви дерева, которая «вырастает» на каждой из предыдущих ветвей.

Выпишем все пути от вершин первого уровня к верши­нам третьего уровня: А-В-С, А-С-В, ВАС, В-С-А, С-А-В, С-В-А. Каждый из выписанных путей определяет один из вариантов рассаживания учеников на стулья. Так как других путей нет, то искомое число способов - 6.

Дерево можно не строить, если не требуется выписывать все возможные варианты, а нужно просто указать их число. В этом случае рассуждать нужно так: на первый стул можно усадить одного из трех человек, на второй - одного из двух оставшихся, на третий - одного оставшегося: 3-21 = 6.

Задача №4. Чтобы принести Царю-батюшке молодильные яблоки, должен Иван-царевич найти единственный верный путь к волшебному саду. Встретил Иван-царевич на развилке трех дорог старого ворона и вот какие советы от него услышал:

1) иди сейчас по правой тропинке;

2) на следующей развилке не выбирай правую тропинку;

3) на третьей развилке не ходи по левой тропинке.

Пролетавший мимо голубь шепнул Ивану-царевичу, что только один совет ворона верный и что обязательно надо пройти по тропинкам разных направлений. Наш герой выполнил задание и попал в волшебный сад. Каким маршрутом он воспользовался?

Обозначим левую, среднюю и правую тропинки соответственно Л, С и П. Возможные маршруты представим в виде графа. При этом подсказки ворона отметим более «жирными» ребрами. Так как только один совет ворона верен, то на графе ему будет соответствовать маршрут, имеющий одно «жирное» ребро. Этот маршрут обозначен дополнительной пунктирной линией.

Задача №5. Квартет.

« Проказница мартышка, осел, козел да косолапый мишка затеяли сыграть в квартет». Мартышка расположилась напротив медведя, а слева и справа от нее - осел и козел. «Ударили в смычки, дерут, а толку нет». Тогда осел и козел поменялись местам. «Расселись, начали квартет. Он все-таки на лад нейдет». Таким образом, они перепробовали все возможные вариант. Медведь всегда оставался на одном месте. Сколько всего было вариантов расположения незадачливых музыкантов?

Решение.

1 2 3 4 5 6

Мартышка козел осел козел мартышка осел

Козел мартышка козел осел осел мартышка

Осел мартышка козел

мишка

Варианты расположения музыкантов в квартете.

Задача 6. (задача ЕГЭ, в которой можно использовать теорию графов)

На первом месте в цепочке стоит одна из бусин А, Б, В. На втором одна из бусин Б, В, Г. На третьем месте - одна из бусин А, В, Г, не стоящая в цепочке на первом или втором месте. Задание: выписать все такие цепочки.

Решение.

Решение задачи облегчается, если использовать теорию графа (дерево)

Ответ : Всего 16.

Задачи для самостоятельного решения:

1. Сколько различных трехзначных чисел можно записать с помощью цифр 0, 1, 2, если цифры в числе могут повторяться?

2. Составьте схему проведения розыгрыша кубка по олимпийской системе, в которой участвуют 19 команд.

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

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

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

6. Составьте генеалогическое древо династии Романовых.

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

8. Изобразите дерево возможных исходов при троекратном бросании монеты.

9. Постройте дерево игры, показывающее ходы партнеров, приводящие к победе «крестиков», если игра начата ходами: а) (х1) и (о2), б) (х1) и (о9); в) (х5) и (о8).

10. Рассади участников «Большой восьмерки» за круглым столом всеми возможными способами.

Тема 5. Графы и логические задачи .

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

1. Беседуют трое друзей - Белокуров, Рыжов и Чернов. Брюнет сказал Белокурову: «Любопытно, что один из нас - блондин, другой - брюнет, третий - рыжий, но ни у кого цвет волос не соответствует фамилии». Какой цвет волос у каждого из друзей?

2. В Артеке за круглым столом оказалось пятеро ребят из Москвы, Санкт-Петербурга, Новгорода, Перми и Томска: Юра, Толя, Алеша, Коля и Витя. Москвич сидел между Томичем и Витей, санкт-петербуржец - между Юрой и Толей, а напротив него сидел пермяк и Алеша. Коля никогда не был в Санкт-Петербурге, Юра не бывал в Москве и Томске, а Томич с Толей регулярно переписываются. Определите, кто в каком городе живет.

3. В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что:

• Вода и молоко не в бутылке.

• Сосуд с лимонадом стоит между кувшином и сосудом с квасом.

• В банке не лимонад и не вода.

• Стакан стоит между банкой и сосудом с молоком.

В каком сосуде находится, какая из жидкостей?

4. Три подруги вышли в белом, зеленом и синем платьях и туфлях. Известно, что только у Ани цвета платья и туфель совпадали. Ни туфли ни платье Вали не были белыми. Наташа была в зеленых туфлях.

5. На улице, встав в кружок, беседуют Аня, Валя, Галя и Надя.

• Девочка в зеленом платье - не Аня и не Валя - стоит между девочкой в голубом платье и Надей.

• Девочка в белом платье стоит между девочкой в розовом и Валей. Какого цвета платье у каждой из девочек?

6. В семье четверо детей. Им 5, 8, 13 и 15 лет. Зовут их Аня, Боря, Вера и Галя. Сколько лет каждому ребенку, если одна девочка ходит в детский сад, Аня старше Бори, а сумма лет Ани и Веры делится на три?

7. Какое наименьшее число переливаний необходимо для того, чтобы с помощью 7-и 11-литровых сосудов и крана с водой отмерить 2 литра?

8. Сколько существует различных трехзначных чисел, в записи которых участвуют лишь цифры 1, 2, 3 и 4?

9. Среди чисел, о которых говорится в задаче 8, сколько существует таких, в записи которых цифры не повторяются?

Тестовые задания

1. Укажите область, в которой не применяются графы:

а) экономика;

б) физика;

в) архитектура;

г) нет вариантов.

2. Укажите полный граф.

3.Если полный граф имеет n вершин, то количество его ребер равно:

а) (n-1)/2 б) n(n-2)/2 в) n(n-1)/2

4. Какой граф является «эйлеровым графом»

5. Начерти линию одним росчерком (укажи направление).

6. Придумай свой способ записи букв Ф и К, при котором их можно начертить одним росчерком.

Ответ:

7. Решению, какой из следующих задач, соответствует граф

а) В пяти корзинах (А, Б, В, Г, Д) лежат яблоки пяти разных сортов. Яблоки первого сорта лежат в корзинах Г и Д; яблоки второго сорта - в корзинах А, Б и Г; в корзинах А, Б и В имеются яблоки пятого сорта, в корзине В имеются к тому же яблоки четвертого сорта, а в корзине Д - третьего. Требуется дать каждой корзине номер, но так, чтобы в корзине №1 были яблоки первого сорта (хотя бы одно), в корзине №2 - второго и т.д.

б) Трое господ при входе в ресторан отдали швейцару свои шляпы, а при выходе получили их обратно. Сколько существует вариантов, при которых каждый из них получил чужую шляпу?

в) Каждая вершина правильного шестиугольника соединяется с каждой из остальных вершин красным или синим отрезком. Докажите, что всегда найдется треугольник со сторонами одного цвета.

8. Начерчен плоский граф, имеющий шесть вершин, степень каждого из которых равна 4. Этот граф под номером:

9.Начерти плоский граф, имеющий шесть вершин, степень каждой из которых равен 3.

Ответ:

10. Реши задачу, использовав графы.

Аркадий, Борис, Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями, каждый пожал руку каждому по одному разу. Сколько всего рукопожатий было сделано?

а) 5 б)10 в)9

Литература:

1. 1. Концепция модернизации российского образования на период до 2010 года. Нормативные документы в образовании.

2. Оре О. "Графы и их применения", М. "Мир", 1965;

3. Березина Л.Ю. Графы и их применение. - М. «Просвещение», 1979.

4. В.А.Гусев, А.И. Орлов, А.Л.Розенталь. Внеклассная работа по математике. -Москва «Просвещение» 1984г.

5. Научно - методическая газета «Математика» - Приложение к газете 1 сентября -

№6, 2007г.

6. Проектная деятельность учащихся по математике. Автор - составитель М.В.Величко. - Волгоград: Учитель, 2007г.

7. Мельников О.И. Занимательные задачи по теории графов. Учебно-методическое пособие. - НТООО «ТетраСистемс». - 2001.

8. Литвинова С.А, Куликова Л.В, и др. За страницами учебника математики. Волгоград: Панорама, 2006.