МУНИЦИПАЛЬНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

НАЧАЛЬНАЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА №71

ЭЛЕКТИВНЫЙ КУРС

«Графы»

Разработал:

учитель физики

Барабанщиков

Алексей Валентинович

г. Липецк

2010

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

За душу каждого математика борются демон абстрактной алгебры и ангел чистой топологии.

Андре Вейль.

…И не кричи мне, геометр,

что это все не топология

и речь в ней вовсе о другом.

Уймись! Тебя поймут немногие,

меня же – чуть не все кругом.

Л. Мартынов «Топология»

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

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

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

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

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

Важность математической подготовки прикладного назначения определяет следующие задачи обучения:

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

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

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

• поддержание интереса у школьников к математике;

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

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

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

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

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

В последние десятилетия теория графов находит все новые области применения (физика, химия, генетика, психология, социология, экономика, лингвистика, электроника, теория планирования и управления). Именно запросы практики способствуют интенсивному развитию теории графов.

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

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

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

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

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

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

Наряду с рефератами и докладами подразумевается подготовка научно-исследовательских работ как результата индивидуальной и групповой деятельности по итогам поисковой работы.

Цель предлагаемого курса – ознакомление на доступном уровне с применением графов в решении задач.

Задачи курса:

- развить интерес школьников к предмету;

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

- помочь учащимся отойти от математических штампов; расширить их математический и общенаучный кругозор.

- обеспечить формирование и развитие навыков самообразования через поисковую и исследовательскую работу;

- сформировать восприятие математики как единого языка познания;

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

Содержание программы.

Программа курса состоит из 10 разделов и рассчитана на учащихся 10 классов. На изучение курса отводится 16 часов (I полугодие учебного года, 1 час в неделю).

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

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

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

Тема 2. Эйлеров и Гамильтонов циклы. Задачи о мостах. Рисование фигур единым росчерком.

Учащимся дается понятие об эйлеровом и гамильтоновом циклах.

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

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

Рассматриваются задачи на «маршруты путешествий» и «осмотр достопримечательностей»

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

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

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

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

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

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

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

Тема 4. Задача четырех красок.

Учащиеся знакомятся с задачей раскраски карты. Задача известна достаточно давно, но в качестве теоремы или задачи впервые была выдвинута Мебиусом в 1840 году. Суть задачи в следующем.

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

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

Учащимися формулируются условия возможности раскраски двумя красками, тремя, условия «правильной раскраски».

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

Тема тем более актуальна, что предположение о 4-х красках никто не доказал, но никто и не опроверг.

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

Тема 5. Графы с цветными ребрами и их свойства.

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

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

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

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

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

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

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

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

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

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

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

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

Тема 8. Применение теории графов в различных областях науки и техники.

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

Занятие проводится в виде пресс-конференции или круглого стола. Организуется стендовая защита поисковых и исследовательских работ.

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

№ п/п

Тема занятия

Кол-во часов

Форма проведения занятия

Форма контроля.

1.

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

2

Лекция – беседа.

Лабораторно-графическая работа

Практическая работа.

Решение задач.

2.

Эйлеров и гамильтонов циклы. Задачи о мостах. Рисование фигур единым росчерком.

3

Лекция - беседа.

Лабораторно-графическая работа.

Практическая работа.

Решение задач. Самостоятельная работа.

3.

История лабиринтов. Геометрическая постановка задачи о лабиринте. Способы прохождения лабиринта. Лабиринты и графы.

2

Сообщения учащихся. Беседа.

Поисковые задания.

Выполнение практических работ.

Практическая работа.

4.

«Задача четырех красок». Графы и правильная раскраска карты.

2

Сообщение по теме.

Творческие задания.

Практическая работа.

Выполнение практических работ.

5.

Графы с цветными ребрами и их свойства.

1

Практикум по решению задач.

Сообщение по теме. Исследовательские задания.

6.

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

2

Лекция.

Практикум по составлению дерева решений.

Творческие и исследовательские задания.

7.

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

2

Практическое занятие.

Решение задач.

Практическое занятие.

Решение задач.

8.

Зачетная работа

1

Самостоятельная работа

Решение задач

9.

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

1

Урок-конференция.

Защита исследовательских работ.

Литература для учащихся.

1. Барр С. Россыпи головоломок.- М. «Мир». 1987.

2. Болл У, Коксетер Г. Математические эссе и развлечения. – М. «Мир», 1986.

3. Гарднер М. Математические головоломки и развлечения. – М. «Мир», 1971.

4. Гарднер М. Крестики-нолики. М., «Мир», 1988.

5. Графы // Квант. 1994. - №6.

6. Игнатьев Е.И. В царстве смекалки. Ростов-на-Дону, Ростовское книжное издательство, 1995.

7. Кордемский Б.А. Математические завлекали. – М.: Издательский дом Оникс: Альянс – В, 2000.

8. Перельман Я.И. Занимательные задачи и опыты. – М, «Детская литература», 1972.

9. Топология графов // Квант. – 2005. - №3.

10. Энциклопедия для детей. Том 11. Математика. Тема «Графы». – М.: Аванта, 1998.

Литература для учителя

1. Абрамов А.М, Березина Л.Ю. и др. Методика факультативных занятий в 7-8 классах. – М. «Просвещение», 1981.

2. Альхова З.Н., Макеева А.В Внеклассная работа по математике. – Саратов: «Лицей», 2002.

3. Асарина Е.Ю., Фрид М.Е. Математика выводит из лабиринта. – М. «Контекст», 1995.

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

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

6. Графы и кратчайшие расстояния в них. – Математика. Приложение к газете «1 сентября». – 2001 - №15, 16.

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

8. Нестеренко Ю.В., Олехник С.Н., Потапов М.К. Задачи на смекалку. М, «Дрофа», 2005.

9. Смирнов Е.С. Курс наглядной геометрии. – М. «Просвещение», 2002.

10. Шарыгин И.Ф., Ерганжиева Л.Н. Наглядная геометрия. – М. «Дрофа», 2001.