Теория графов

Автор работы: Пользователь скрыл имя, 15 Апреля 2014 в 02:51, курсовая работа

Описание работы

Что такое граф? Когда речь заходит о графе, большинство людей представляют себе график, т.е. нечто вроде диаграммы, отражающей производственную деятельность какого-нибудь предприятия (рис. 1), или гладкую кривую (рис. 2), позволяющую наглядно представить свойства какой-нибудь математической функции.
Настоящее столетие было свидетелем неуклонного развития теории графов, которая за последние десять лет и даже двадцать вступила в новый период интенсивных разработок. В этом процессе явно заметно влияние запросов новых областей приложений: теории игр и программирования, теории передачи сообщений, электрических сетей и контактных цепей, а также проблем биологии и психологии.

Содержание работы

Введение…………………………………………………………………………..3
Глава 1. Графы и их применение………………………………………………..5
1.1. Основные понятия теории графов…………………………………………..5
1.2. Раскраска графов. Применение раскраски графов в практической деятельности человека…………………………………………………………..19
Глава 2. Элементы теории графов на факультативных занятиях в школе….22
2.1. Роль факультативных занятий……………………………………………..22
2.2. Постановка факультатива «Элементы теории графов в средней школе...26
Заключение……………………………………………………………………...34
Список использованной литературы………………………………………..35

Файлы: 1 файл

теория графов . курсов.СОДЕРЖАНИЕ.doc

— 243.00 Кб (Скачать файл)

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

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

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

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

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

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

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

 

2.2. Постановка факультатива  «Элементы теории графов в  средней школе»

 

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

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

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

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

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

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

Факультатив «Знакомьтесь, графы».

На изучение темы программой отведено 32 часа.

Цель факультатива: развивать логическое мышление через установление отношений между множествами графовым способом.

Задачи факультатива:

- сформировать  представление о графе как  совокупности двух множеств, его  составных элементов;

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

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

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

- развивать воображение, повышать культуру общения, воспитывать  интерес к математике.

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

 

Тема

Ча-сы

Цель

Оборудование, материал

Содержание

I. Первое знакомство с графами.

1. Занимательные задачи

2. План

1) центр части г.Нерчинска

2) Эвакуация из каб. мат.

 

 

 

 

 

 

 

 

3. Соответствия, отношения и их описание графами

 

 

 

4. Основные понятия теории графов

 

 

 

 

 

 

 

 

II. Плоские графы

1. Представление о плоском графе

 

 

2. Эйлеровы графы

 

 

 

 

 

 

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

 

 

III. Сфера применения теории графов

 

 

 

 

 

 

 

 

 

 

 

 

 

 

IV. Обобщение и повторение

 

 

 

 

 

 

 

 

 

 

V. Творческая мастерская

14

 

 

 

2

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

3

 

 

 

 

 

 

 

 

 

 

5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

11

 

 

1

 

 

 

 

 

 

5

 

 

 

 

 

 

 

5

 

 

 

 

 

 

5

 

 

 

 

 

 

 

 

3

 

 

 

 

 

 

 

1

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

Обобщение элементов теории множеств, владение понятием «отношения между парами элементов множества».

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

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

Провести краткий экскурс жизни и деятельности Эйлера, его формулы, задач (одним росчерком, на отыскание путей через лабиринт, о Кенигсберских мостах…)

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

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

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

Развитие творческих способностей учащихся при написании реферата или сообщения, при исследовательской работе, при составлении кроссвордов…

Иллюстрации, карточки с задачами.

Мельников О.И. Занимательные задачи по теории графов. Минск: Тетра Системс, 2001.

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

Кодоскоп, карточки, наглядность «Внеклассная работа по математике» (под ред. С.И.Шварцбурда. М., Просвещение, 1974).

Наглядности, иллюстрации

Мельников О.И. Незнайка в стране графов. – Минск: Беларусская навука, 2000.

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

Папи Ф. и Папи Ж. Дети и графы. М., Педагогика, 1974.

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

Иллюстрации.

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

Портреты, иллюстрации к задачам.

Гарднер М. Математические новеллы. М., Мир, 1973.

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

Портрету, иллюстрации к задачам.

Литературу смотри выше.

Гик Е.Я. Математика на шахматной доске. М., 1976.

Учебники, книги, иллюстрации, схемы.

Сему С., Рид М. Линейные графы и электрические цепи. М., Высшая школа, 1971.

Дмитриев И.С. Симметрия в мире молекул. М., Наука, 1976.

Березина Л.Ю. Графы и их применение. М.: 1979.

Блок-схема, карточки-задания, оборудование для игры

Портреты, работы учащихся Берези-

на Л.Ю. Графы и их применение. Пособие для учителей.М.: 1979.

Методика факуль-

тативных занятий в 7-8 классах. Избр. вопросы математики. Пособие для учителей / Сост. И.Л.Никольская, В.В.Фирсов. – М.: Просвещение, 1981.

Факультатив начинается с решения занимательных задач на соображение. Представляют интерес и задачи, в которых нужно сделать простой, но неожиданный ход, выйти за рамки стандартного решения. Соответствующие задачи можно найти у Р.Левченко. Кто хочет стать отличником // Математика в школе. Приложение к ПС. – 2004. – 23-29 февраля.

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

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

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

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

Цель соответствует подробному содержанию данных часов.

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

Эйлеров граф – имеет эйлеров цикл – содержит все ребра графа – формула В – Р + Г = 2.

Фигуры одним росчерком, задачи на отыскание путей через лабиринт, о Кенигсбергских мостах.

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

Задача о додекаэдре, шахматном коне…

Биология, география, химия. Форзац учебника зоологии VII-VI классов (классификация основных типов животных). Экономическая география СССР VIII класс-схема народного хозяйства, схема использования угля в народном хозяйстве, история VII класс – ориентированное дерево – система управления в Российском государстве XVI-XVII вв.

2 часа – провести повторение, используя блок-схему изученных понятий, варьируя коллективной работой, индивидуальной (по карточкам), работой в группах: ученик – ученик, ученик – учитель.

1 час – развлекательное мероприятие.

Отчет о проделанной работе:

- реферат или доклад (об ученом, по конкретной теме),

- исследовательская работа «Графы в играх и головоломках»,

- графы и их роль в школьных учебниках,

- составление и написание кроссвордов, сканвордов, сказок, поэтических строк…


граф маршрут теория

Рассмотрим небольшой фрагмент одного из занятий по теме «Сфера применения теории графов». Класс оформлен портерами, соответствующими газетами, рисунками, задачами.

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

Я о графах сейчас расскажу,

Расскажу, а ты тут же и вспомнишь,

Лабиринты тебе покажу,

Разгадать ты их точно уж сможешь.

Как любил ты игру про коня1

Вечерами одни разговоры.

Ты гонял его и гонял

О победе мне вторил с задором…

Помнишь, маленьким ты рисовал

Мне открытый конверт на листочке,

Безотрывно карандашик порхал,

Рисовал ты от точки до точки…

Кто-то умный все это создал

Для развития сына и дочки,

Пусть ребенок в игре создавал

Не игру, а теорию точно…

- Знакомы ли  вам действия, описанные в стихотворении, что общего они имеют с темой нашего семинара?

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

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

- Хочется задать  всем вопрос, а для чего или  зачем возникла данная теория? Дает ли она результаты в  современном, быстро меняющим свой  ритм времени?

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

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

- Подведем итоги, думаю многим из присутствующих  было интересно, а ребята, занимающиеся  на факультативе, воочию убедились  о многосторонней значимости данной теории. Ни для кого не секрет, что наряду с решенными задачами и проблемами существуют переменные задачи. Некоторые из них имеют элементарную занимательную форму, выглядят как головоломки или олимпиадные задачи. Например, известно, что на бумаге в клетку можно нарисовать 5 фигур из 4 клеток так, чтобы в каждую клетку можно было пройти из соседней через сторону2 (рис.46). Известно, далее, что таких фигур из пяти клеток 12, из 6 – 35, …, из 10 – 4271. А сколько таких фигур из 11 клеток и вообще из n клеток – неизвестно.

- Прошу еще  раз в конце семинара задуматься  о вопросах, прозвучавших в начале…

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

 

ЗАКЛЮЧЕНИЕ

 

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

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

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

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

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

 

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

 

1. Асеев Г.Г., Абрамов О.М., Ситников Д.Э. Дискретная математика: Учебное пособие. – Ростов н/Д: «Феникс», Харьков: «Торсинг», 2009. – 144 с.

2. Балк М.Б., Балк Г.Д. Математический  факультатив – вчера, сегодня, завтра // Математика в школе. – 2007. - №3. –  с.14.

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

4. Журбенко И.Г. О материалах  для факультативных занятий // Математика  в школе. – 2009. - №2. – с.53.

5. Мельников О.И., Куприянович  В.В. Обучение элементам теории  графов в IV – VI классах // Математика в школе. – 2008. - №4. – с.63.

6. Мельников О.И. Графы  в обучении математике // Математика  в школе. – 2003. - №8.

7. Методика факультативных  занятий в 7-8 классах: Избр. вопросы  математики. Пособие для учителей / Сост. И.Л.Никольская, В.В.Фирсов. – М.: Просвещение, 1981.

8. Оре О. Теория графов. М., Наука, 1968.

9. Педагогика: Учеб. пособие  для студентов пед.ин-тов. Под  ред. Ю.К.Бабанского. М.: Просвещение, 1983.

10. Рогачев С.В. Граф на  службе у географии // География  в школе. – 2005. - №29 (91).

11. Судоплатов С.В., Овчинниова Е.В. Элементы дискретной математики: Учебник. – М.: ИНФРА-М, Новосибирск. Изд-во НГТУ, 2002.

Информация о работе Теория графов