Программа кружка по математике "Его величество Граф"
методическая разработка (7, 8 класс) по теме

Кружок для 7-8 классов «Его Величество Граф»

(Сметанина Зоя Александровна, учитель математики)

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

Предлагаемый курс является предметно-ориентированным.

Цель:

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

Задачи:

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

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

Развивающие 

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

Воспитательные

• Воспитать умение работать самостоятельно и в группе.
• Воспитать ответственность, аккуратность.

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

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

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

Содержание.

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

Рассмотреть задачи, провоцирующие неправильные ответы. Задача «Кто кого учит?». Перевести рассмотренные задачи на язык схем.( терминология не вводится) Приводится историческая справка. Учащиеся выступают с докладом «Леонард Эйлер», «Кёнинг».Определение графа и подграфа. Полные графы. Рассмотреть три задачи: Кто играет Ляпкина – Тяпкина? Сварливые соседи, Корзины, полные яблок. Перевести эти задачи на язык графов. Дать основные понятия графов, вершины графа, ребро графа, нулевой граф, изолированный граф, полный граф.

2. «Лемма о рукопожатиях». Решение задач.

 Сформулировать и доказать лемму о рукопожатиях. Обсудить 1 главу книги “Незнайка в стране графов”. Оформить ситуацию описанную в книге с помощью графов. Самостоятельная проверка леммы в данной ситуации. Второе доказательство леммы: где из конкретного графа удаляются все ребра, а затем по одному возвращаются. Доказать следствие из леммы:в любом графе число вершин нечетной степени четное. Решение задач на закрепление леммы.

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

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

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

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

5. Дерево и лес. Понятие дерева в теории графов.

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

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

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

Возможные темы:

1. Графы и информация.( http://inf-bez.ru/?cat=151)
2. Графы и химия.( http://www.newchemistry.ru/glossary/glossary.php?gloss_id=1282)
3. Графы в генетике.( http://www.za4et.net.ru/referat/sus)
4. Графы в психологии. (http://www.psibook.com/06/55.html)
5. Графы в технике.( http://stunik.ru/download/category/product/12-matematika/17-primenenie-grafov-v-tehnike.html)
6. Графы в решении логических задач.( http://www.refsru.com/referat-633-1.html)

7. Поле-Чудес «Его Величество Граф»

Урок - игра, правила аналогичны одноименному телешоу. Проверка основных терминов определений.

Список литературы.

1. Абрамов А.М, Березина Л.Ю. и др. Методика факультативных занятий в 7-8 классах. – М. «Просвещение», 1981.
2. Альхова З.Н., Макеева А.В Внеклассная работа по математике. – Саратов: «Лицей», 2002.
3. Асарина Е.Ю., Фрид М.Е. Математика выводит из лабиринта. – М. «Контекст», 1995.
4. Березина Л.Ю. Графы и их применение. – М. «Просвещение», 1979.
5. Берж К. "Теория графов и ее применение", М., ИЛ, 1962;
6. Гарднер М. "Математические головоломки и развлечения", М. "Мир", 1971;
7. Гарднер М. "Математические досуги", М. "Мир", 1972(глава 35);
8. Графы и кратчайшие расстояния в них. – Математика. Приложение к газете «1 сентября». – 2001 - №15, 16.
9. Мельников О.И. Занимательные задачи по теории графов.
10. Научно-теоретический и методический журнал “Математика в школе” № 1, 4, 2004.
11. Нестеренко Ю.В., Олехник С.Н., Потапов М.К. Задачи на смекалку. М, «Дрофа», 2005.
12.  Никольская И.Л “Факультативный курс по математике 7–9”, М., “Просвещение”, 1991 г.
13. Оре О. "Графы и их применения", М. "Мир", 1965;
14. Уилсон Р. Введение в теорию графов. - М.: Мир, 1977.
15. Фирсов Е.Г. “Интеллектуальные игры для школьников”, “Академия развития”, Ярославль,1998.
16. Харари Ф. Теория графов. — М.: Мир, 1973.

Приложение.

Задачи.

1. В нашем лесу каждый занят своим делом: Одни плетут корзины, другие ловят рыбу.
   Ремеслу мы учились друг у друга. Кот учился у Выдры, Ёж – у Зайца, Лиса – у Волка, Мышь – у Ежа. Бобёр учил Волка и Выдру, Заяц – Белку, Барсук – Зайца. Бобёр учился у Медведя, Ёж – был учителем Дятла. Лучше всех плёл корзины Ёж, чем занимались Заяц, Дятел, Волк и Лиса? Кто из зверей раньше всех научился ловить рыбу, а кто плести корзины?
2. В школьном драматическом кружке решили ставить гоголевского «Ревизора». И тут разгорелся жаркий спор. Всё началось с Ляпкина-Тяпкина.

– Ляпкиным-Тяпкиным буду я! Решительно заявил Дима. С раннего детства я мечтал воплотить этот образ на сцене.
– Ну хорошо, согласен уступить эту роль, если мне дадут сыграть Хлестакова, проявил великодушие Гена.
– … А мне – Осипа, – не уступил ему в великодушии Дима.
– Хочу быть Земляникой или Городничим, – сказал Вова. 
– Нет, Городничим буду я, – хором закричали Алик и Боря. – или Хлестаковым, добавили они одновременно. Удастся ли распределить роли так, Чтобы исполнители были довольны?

3. Корзины, полные яблок. В пяти корзинах лежат яблоки пяти разных сортов.

 Яблоки первого сорта лежат в корзинах Г и Д;

яблоки второго сорта в корзинах  А, Б и Г;

 в корзинах А, Б и В имеются яблоки пятого сорта,

 в корзине В имеются к тому же яблоки четвертого сорта,

а в корзине Д — третьего.

Требуется дать каждой корзине номер, но так, чтобы в корзине №1 были яблоки первого сорта (хотя бы одно), в корзине №2 — второго и т. д.