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

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

Рубрика Математика
Вид дипломная работа
Язык русский
Дата добавления 19.07.2011
Размер файла 145,5 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

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

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

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

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

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

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

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

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

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

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

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

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

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

§ 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 час - развлекательное мероприятие.

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

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

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

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

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

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

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

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

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

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

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

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

Как любил ты игру про коня Речь идет о «шахматном коне» - задаче Гамильтона.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- Подведем итоги, думаю многим из присутствующих было интересно, а ребята, занимающиеся на факультативе, воочию убедились о многосторонней значимости данной теории. Ни для кого не секрет, что наряду с решенными задачами и проблемами существуют переменные задачи. Некоторые из них имеют элементарную занимательную форму, выглядят как головоломки или олимпиадные задачи. Например, известно, что на бумаге в клетку можно нарисовать 5 фигур из 4 клеток так, чтобы в каждую клетку можно было пройти из соседней через сторону Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М., 1966. (рис.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.

12. Теория и методика обучения физике в школе: общие вопросы: Учеб. пособие для студ. высш.пед.учеб. заведений / С.Е.Каменецкий, Н.С.Пурышева, Н.Е.Вашеевская и др. Под ред. С.Е.Каменецкого, Н.С.Пурышевой. - М.: Издательский центр «Академия», 2009.

13. Фирсов В.В. и др. Состояние и перспективы факультативных занятий по математике. Пособие для учителей. Под ред. и с предисл. М.П.Кашина. М., Просвещение, 1977.

14. Энциклопедический словарь юного математика / Сост. А.П.Савин. - М.: Педагогика, 1985.

15. Якунина М.С. Больше внимания факультативам // Математика в школе. - 2010. - №3. - с.51.

Размещено на Allbest.ru


Подобные документы

  • Основные понятия теории графов. Маршруты и связность. Задача о кёнигсбергских мостах. Эйлеровы графы. Оценка числа эйлеровых графов. Алгоритм построения эйлеровой цепи в данном эйлеровом графе. Практическое применение теории графов в науке.

    курсовая работа [1006,8 K], добавлен 23.12.2007

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

    реферат [368,2 K], добавлен 13.06.2011

  • История возникновения, основные понятия графа и их пояснение на примере. Графический или геометрический способ задания графов, понятие смежности и инцидентности. Элементы графа: висячая и изолированная вершины. Применение графов в повседневной жизни.

    курсовая работа [636,2 K], добавлен 20.12.2015

  • Основные понятия теории графов. Степень вершины. Маршруты, цепи, циклы. Связность и свойства ориентированных и плоских графов, алгоритм их распознавания, изоморфизм. Операции над ними. Обзор способов задания графов. Эйлеровый и гамильтоновый циклы.

    презентация [430,0 K], добавлен 19.11.2013

  • Спектральная теория графов. Теоремы теории матриц и их применение к исследованию спектров графов. Определение и спектр предфрактального фрактального графов с затравкой регулярной степени. Связи между спектральными и структурными свойствами графов.

    дипломная работа [272,5 K], добавлен 05.06.2014

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

    курсовая работа [713,8 K], добавлен 16.05.2016

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

    презентация [150,3 K], добавлен 16.01.2015

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

    реферат [106,0 K], добавлен 27.11.2008

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

    лабораторная работа [85,5 K], добавлен 09.01.2009

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

    курсовая работа [649,2 K], добавлен 18.01.2014

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.