Факультативный курс "Теория графов"

Муниципальное бюджетное общеобразовательное учреждение г.Кургана «Средняя общеобразовательная школа №9»

Факультативный курс

«Теория Графов»

Автор: Бухтоярова Юлия Сергеевна,

учитель математики

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

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Нет ничего дороже для человека того,

чтобы хорошо мыслить.

Л.Н. Толстой

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

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

Данный курс рассчитан на обучающихся 8 классов общеобразовательных школ и имеет предметно-ориентированный характер. Курс состоит из 34 часов, из которых 10 часов лекций и 24 часа практических занятий.

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

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

• сформировать систему знаний и умений у обучающихся по теме: «Теория графов. Эйлеровы и гамильтоновы графы»;

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

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

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

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

В результате изучения курса обучающиеся должны знать:

• основные определения и понятия: граф, вершина графа, полный граф, степень вершины, маршрут и путь в графе, цикл, длина пути и цикла в графе;

• определение эйлерова и гамильтонового графов и их элементов;

• способы построения полных, эйлеровых и гамильтоновых графов;

• способы дополнения до полных графов;

Должны уметь:

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

• дополнять любой граф до полного;

• находить путь, маршрут, длину маршрута, цикл, длину цикла в графах;

• определять эйлеровы и гамильтоновы графы;

• приводить примеры графов из жизни;

• по построению графа определить его свойства.

УЧЕБНО – ТЕМАТИЧЕСКИЙ ПЛАН

СОДЕРЖАНИЕ

Вводное занятие (2ч)

1. Примеры графов в жизни: маршрут метрополитена, выставки, генеалогическое древо и другое. (1 ч)

2. Составление генеалогического древа, как примера графа. (1 ч)

1. Основные понятия теории графов (15 ч)

1.1 Понятие графа, вершины, чётные нечётные вершины, изолированной вершины, ребра графов. Изображение графов. Условие соответствия двух рисунков одному и тому же графу. (1 ч)

Практикум: решение задач на определение числа вершин, рёбер по графу; построение графа по числу вершин, рёбер; соответствие двух рисунков одному графу; построение графов по реальным ситуациям. (2 ч)

1.2 Определение полного графа. Построение полных графов. Дополнение до полных графов. (2ч)

Практикум1: решение задач на определение полного графа, числа его вершин, рёбер; построение полных графов. (1ч)

Практикум 2: решение задач на построение дополнения графа до полного. Выполнение графической работы. (1ч)

Практикум 3 Игра «Знатоки»- обобщающая игра по пройденному материалу. (1ч)

1.3 Степень вершины графа. Маршрут и путь графа. Длина маршрута и пути графа. Цикл, длина цикла графа. (2ч)

Практикум1: решение задач на определение степени вершин графа, маршрута, пути. Построение графов по данным степеням графа, пути и маршруту графа. (1ч)

Практикум 2: решение задач на определение длины маршрута, пути, цикла графа. Построение графов. (3ч)

Практикум 3: Игра «Графо любители»- обобщающая игра по пройденному материалу. (1ч)

2. Эйлеровы графы (8 ч)

2.1 Формула Эйлера. Эйлеровый путь, цикл, граф. Уникурсальная линия. Полуэйлеровый граф. Основные теоремы: о эйлеровом цикле, эйлеровом пути. (1,5ч)

Практикум1: решение задач на применение формулы Эйлера. (1,5ч)

Практикум 2: решение задач на нахождение эйлерова пути, цикла; на определения эйлерова графа; построения эйлерова графа. (2ч)

1. Алгоритм построения эйлерова цикла. (0,5ч)

Практикум: решение задач на применение алгоритма построения эйлерова цикла. (1,5ч)

Семинар: Задачи Эйлера об обладании графа эйлеровым циклом. Задача о городе Кенигсберге. (1ч)

3. Гамильтоновы графы (6 ч)

3.1 Гамильтоновый цикл, путь, граф. Задачи о коммивояжере. Примеры гамильтоновых графов в жизни. (1ч)

Практикум: решение задач на нахождение гамильтонового пути, гамильтонового цикла; на определения гамильтонового графа; построения гамильтонового графа. (2,5ч)

3.2 Несколько достаточных условий существования гамильтоновых циклов в графах. (1ч)

Практикум: решение задач на применение условий существования гамильтоновых циклов в графах. (1,5ч)

Обобщающее занятие (1ч)

Решение задач по всему материалу курса.

Итоговое занятие (2ч)

Защита творческих отчётов учащимися с использованием мультимедийных и технических средств обучения.

СПИСОК ЛИТЕРАТУРЫ ДЛЯ ОБУЧАЮЩИХСЯ

1. Асарина Е.Ю., Фридман М.Е. Математика выводит из лабиринта: Математическая книжка-раскраска.- Ярославль: Контекст, 1995.- 40 с

2. Головоломки и графы. М. Барболин.// Квант.- 1975., № 2.

3. Задачи о графах, или Сказка " Иван Царевич и Серый Волк".// Квант.- 1976., № 10.

4. Как нарисовать пятиконечную звезду. А. Савин.// Квант.- 1976., № 1.

5. Лиман М.М. Школьникам о математике и математиках: Пособие для учащихся 4-8 кл.- М.: Просвещение, 1981.- 80 с.

6. Олехник С. Н., Нестеренко Ю.В. и др. Старинные занимательные задачи.- М.: Наука, 1985.- 160 с.

7. Приятель А. Решение логических задач при помощи графов с цветными вершинами.// Квант.- 1974., № 12.

8. Рамсеевская теория графов.// Квант.- 1976., № 8.

9. Саркисян А.А., Колягин Ю.М. Познакомьтесь с топологией: Книга для внеклассного чтения 8-9 класс.- М.: Просвещение, 1976.- 80 с.

10. Шарыгин И.Ф., Ерганжиева Л.Н. Наглядная геометрия 5-6 кл.: Пособие для общеобразовательных учебных заведений.- М.: Дрофа, 1999.- 192 с.

11. Энциклопедия для детей. Т 11. Математика./ М.: Аванта Плюс, 1998.

12. Энциклопедия. Словарь юного математика./ М.: Педагогика, 1989.

СПИСОК ЛИТЕРАТУРЫ ДЛЯ УЧИТЕЛЯ

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

2. Белов В.В. и др. Теория графов: Учебное пособие для вузов.- М.: Высшая школа, 1976.- 392 с.

3. Березина Л. Ю. Графы и их применение: Пособие для учителя.- М.: Просвещение, 1979.- 143 с.

4. Берж К. Теория графов и её применение.- М.: Иностранная литература, 1962.- 320 с.

5. Внеклассная работа по математике: Учебное пособие.- Пермь, 1976.

6. Головоломки и графы. М. Барболин.// Квант.- 1975., № 2.

7. Зверева А.Т., Усынина Н.Ф. Технологии вариативного развивающего обучения математике: Учебное пособие.- Курган: Издательство КГУ, 2002.- 70 с.

8. Зыков А.А. Теория конечных графов.- Новосибирск: Наука, 1969.-

544 с.

1. Никитина Г.Н. Некоторые приёмы развития пространственного мышления учащихся.// Математика в школе.- 1993., № 5.

2. Никольская И.Л. О факультативном курсе "Элементы логики". // Математика в школе.- 1972., № 1.

3. Олехник С. Н., Нестеренко Ю.В. и др. Старинные занимательные задачи.- М.: Наука, 1985.- 160 с.

4. Оре О. Теория графов.- М.: Наука, 1980.- 336 с.

5. Саркисян А.А., Колягин Ю.М. Познакомьтесь с топологией: Книга для внеклассного чтения 8-9 класс.- М.: Просвещение, 1976.- 80 с.

6. Уилсон Р. Введение в теорию графов.- М.: Мир, 1974. 88 с.

7. Энциклопедия для детей. Т 11. Математика./ М.: Аванта Плюс, 1998.

8. Энциклопедия. Словарь юного математика./ М.: Педагогика, 1989

Приложение 1

ТЕМЫ ТВОРЧЕСКИХ РАБОТ

1. Составить мультимедийную презентацию на тему: «Примеры графов в реальной жизни»

2. Составить мультимедийную презентацию на тему: «Основные понятия теории графов»

3. Составить мультимедийную презентацию на тему: «Эйлеровы графы»

4. Составить мультимедийную презентацию на тему: «Гамильтоновы графы»

5. Решение задач по теме: «Основные понятия теории графов»

6. Решение задач по теме: «Длина маршрута, пути графа»

7. Решение задач по теме: «Цикл. Длина цикла графа»

8. Решение задач по теме: «Эйлеровы графы»

9. Решение задач по теме: «Способы построения различных видов графа»

10. Решение задач по теме: «Гамильтоновы графы»

11. Конспект сообщение с мультимедийным обеспечением по теме: «Виды графов»

12. Конспект сообщение «Рамсеевская теория графов»

13. Опорный сигнал: «Основные понятия теории графов»

14. Опорный сигнал: «Основные понятия по теме: «Эйлеровы графы и их примеры»»

15. Опорный сигнал: «Основные понятия по теме: «Гамильтоновы графы и их примеры»»

16. Написание сказки «Математические графы»

17. Анализ использования элементов теории графов при обучении математике в школьном курсе по учебнику Шарыгин И. Ф., Ерганжиева Л. Н. Наглядная геометрия 5-6 класс, и решение задач, представленных в данном учебнике.

18. Анализ использования элементов теории графов при обучении математике в школьном курсе по учебному пособию Асарина Е.Ю., Фрид М. Е. Математика выводит из лабиринта, и решение задач, представленных в данном учебном пособии.

19. Анализ использования элементов теории графов при обучении математике в школьном курсе по учебнику Дорофеев Г. В. и др. Математика 6 класс, и решение задач, представленных в данном учебнике.

20. Анализ использования элементов теории графов при обучении математике в школьном курсе по учебнику Виленкина Н.Я. Математика 6 класс, и решение задач, представленных в данном учебнике.

Приложение 2

ДИДАКТИЧЕСКАЯ ИГРА «РАСШИФРУЙ СЛОВО»

Условия игры: необходимо собрать код из 6 цифр. Затем с помощью "ключа" узнать название одного из видов графа. Отвечая на вопросы и выполняя задание, получают нужную цифру. Класс делится на две три команды.

1 Цифра 8. Назовите вершины данного графа

В

А Д С

Е Ответ: А, В, С, Д, Е.

2 Цифра 1. Какая из вершин изолированная?

Ответ: Д.

3 Цифра 4. Назовите ребра графа

Ответ: (А, В), (В, С), (А, Е).

4 Цифра 9. Сколько ребер у изображенного графа?

Ответ: 5

5 Цифра 3. Сколько вершин у графа (рисунок из 4 задания)?

Ответ: 6

6 Цифра 6. Назовите изолированные вершины.

Ответ: их нет

Ключ к разгадке: 1 3 4 6 8 9

О Ы Л Й П Н

Ответ: полный

Приложение 3

ИГРА «ГРАФО-ЛЮБИТЕЛИ»

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

1 конкурс: Теоретики

С помощью опорного сигнала рисунок вспомнить все определения и понятия. По истечении 5 минут - блиц опрос. По готовности ответа команда поднимает сигнальную карточку.

ОПОРНЫЙ СИГНАЛ.

-------------------------------------------------------------------------------------------------

2 степ.1=1

степ.2=2

1 3 степ.3=1

-------------------------------------------------------------------------------------------------

(1;2), (2;4), (4;3), (3;1), (1;4), (4;5)- 1 2

маршрут

длина маршрута равна 6

3 5

4

-------------------------------------------------------------------------------------------------

2 (1,2,4,1,3,4,5)- путь

длина пути равна 6

(1,2,4,3,1)- цикл

1 длина цикла равна 4

4 5 (1,2,4,3,1)- простой цикл.

3

-------------------------------------------------------------------------------------------------

2 конкурс: Решебников

1. Назовите пути в графе рисунок от 1 до 2 вершины, длины 1, длины 9.

3 6

1 8

2 7

4

5

Ответ: 1) (1;2)

2) (1;2), (2;3), (3;6), (6;7), (7;4), (4;2), (2;7), (7;5), (5;2).

2. В этом же графе найдите путь от 1 до 7, длины 2, длины 8.

3. Найдите циклы длины 4, длины 5, длины 8. Какие из них простые?

4. Назовите степень каждой вершины.

(Назвать счёт после двух конкурсов).

3 конкурс: Отгадайка

Чем является последовательность для графа на рисунке

1 2

3

4

6

5

7

а) (1,4,6,2,3,5,1,4,6,5,7) д) (7,5,6)

б) (1,4,6,2) е) (1,4,6,2,3,5,7,1)

в) (2,6,5,2) ж) (4,6,2,3,5,2,6,4,1)

г) (1,5,7,1) з) (1,7,5,1)

Ответ: а) маршрут, б) маршрут, в) простой цикл, г) простой цикл, д) путь, е) простой цикл, ж) маршрут, з) простой цикл.

Все ответы с объяснением.

4 конкурс: Строителей

Постройте граф с 9 вершинами, пять из которых имеют степень равную 3, две со степенью 1, одна со степенью 2, одна со степенью 5.

ПОДВЕСТИ ИТОГИ.

Приложение 4

ИГРА «СЧАСТЛИВЫЙ СЛУЧАЙ»

Конкурсы игры:

1. Заморочки из бочки.

2. Дальше, дальше, дальше.

3. Ты мне, я тебе.

4. Гонка за лидером.

5. Тёмная лошадка.

Можно включить любые задания и задачи из всего элективного курса.