Методика изучения Эйлеровых графов на занятиях по математике в 8-9 классах

Методика изучения Эйлеровых графов на занятиях по математике в 8-9 классах

МЕТОДИКА ИЗУЧЕНИЯ ЭЙЛЕРОВЫХ ГРАФОВ НА ЗАНЯТИЯХ ПО МАТЕМАТИКЕ В 8-9 КЛАССАХ

Оглавление

Введение

Глава I. Психолого-педагогические основы изучения теории графов на занятиях по математике для учащихся основной школы

.1 Проблемы повышения эффективности современного школьного образования

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

.3 Психологические особенности учащихся 8 - 9 классов

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

Глава II. Методическое обеспечение факультативного курса «Эйлеровы графы» для учащихся 8 - 9 классов

.1 Основные характеристики факультативного курса

.2 Математическое содержание факультативного курса

.3 Методические рекомендации для учителя

.4 Опытно-экспериментальная проверка разработанного курса

Заключение

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

Введение

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

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

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

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

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

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

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

Все вышесказанное определило актуальность нашего исследования.

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

Предмет исследования: процесс обучения учащихся 8 - 9 классов элементам теории эйлеровых графов на факультативном курсе.

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

Проблема исследования состоит в поиске теоретических основ изучения теории графов на факультативных занятиях для учащихся основной школы, выявлении психолого-педагогических и методических особенностей преподавания факультативного курса «Эйлеровы графы» для учащихся 8 - 9 классов.

Целью исследования является разработка факультативного курса «Эйлеровы графы» и методики его преподавания для учащихся 8 - 9 классов.

Реализация поставленной цели потребовала решения ряда конкретных задач, а именно:

составить психолого-педагогическую характеристику учащихся 8 - 9 классов основной школы;

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

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

отобрать содержание факультативного курса «Эйлеровы графы» и разработать методику преподавания курса;

определить роль и место факультативного курса в процессе обучения математике в школе;

провести опытно-экспериментальную проверку эффективности предложенной методики.

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

Теоретические:

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

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

Практические:

беседы с учащимися;

проведение диагностических контрольных работ для проверки качества усвоения и доступности предлагаемого материала;

проведение опытной проверки основных положений исследования.

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

теоретический материал для преподавания факультативного курса «Эйлеровы графы» для 8 - 9 классов;

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

методические рекомендации для учителя по проведению факультативного курса «Эйлеровы графы».

Структура работы

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

Во введении обоснована актуальность исследования, даны его основные характеристики.

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

В главе II рассмотрены вопросы методики изучения темы «Эйлеровы графы» в 8 - 9 классах, его математическое содержание. Приводятся результаты опытной проверки.

В заключении приведены основные выводы и результаты проведенного исследования.

Список литературы содержит 52 наименование.

Глава I. Психолого-педагогические основы изучения теории графов на занятиях по математике для учащихся основной школы

.1 Проблемы повышения эффективности современного школьного образования

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

«Образование - единый целенаправленный процесс воспитания и обучения, являющийся общественно значимым благом и осуществляемый в интересах человека, семьи, общества и государства, а также совокупность приобретаемых знаний, умений, навыков, ценностных установок, опыта деятельности и компетенции определенных объема и сложности в целях интеллектуального, духовно - нравственного, творческого, физического и (или) профессионального развития человека, удовлетворения его образовательных потребностей и интересов» [47].

«Гражданам Российской Федерации на ее территории гарантируется возможность получения образования независимо от расы, национальности, языка, пола, возраста, состояния здоровья, социального, имущественного и должностного положения, социального происхождения, места жительства, отношения к религии, убеждений, партийной принадлежности, наличия судимости» [24].

«Государство, согласно части второй статьи 43, гарантирует гражданам Российской Федерации получение бесплатного основного общего образования и среднего профессионального образования в государственных или муниципальных образовательных учреждениях и на предприятиях. Основное общее образование - это образование в объеме 9 классов общеобразовательной школы. А в 10 и 11 классы предполагается прием учащихся по их желанию» [24].

«Содержание образования определенного уровня и направленности обусловлено соответствующими программами: дошкольного образования, начального общего, основного общего, среднего (полного) общего образования и так далее. Эти программы должны соответствовать государственным образовательным стандартам» [24].

Следует отметить, что «наряду с государственными и муниципальными образовательными учреждениями допустима организация и деятельность негосударственных учреждений - частных школ, а также учреждений образования, создаваемых общественными и религиозными объединениями» [24].

«С точки зрения конституционных обязанностей граждан Российской Федерации обязательным для каждого является основное общее образование; в настоящее время это девять классов общеобразовательной школы или приравненного к ней другого образовательного учреждения. При завершении основного общего образования осуществляется государственная аттестация учащегося (Единый государственный экзамена), при успешном окончании обучения выдается аттестат государственного образца, что и дает право продолжать обучение для получения среднего (полного) образования либо среднего профессионально-технического образования» [24].

«Законом предусмотрено, что требование обязательности основного общего образования применительно к конкретному обучающемуся сохраняет силу до достижения им 15-летнего возраста» [24].

«В связи с обязательностью основного общего образования родителям или лицам, их заменяющим вменяется в обязанность обеспечить получение детьми такого образования. При этом названный Закон допускает возможность семейного образования, то есть обучения ребенка вне образовательного учреждения, но с обязательной сдачей экзаменов аттестационной комиссии в установленном порядке» [24].

«Чтобы обеспечить высокий уровень образования, в Российской Федерации законодательно закреплено введение государственных образовательных стандартов, включающих федеральный и национально- региональный компоненты. Государственный стандарт определяет обязательный минимум содержания основных образовательных программ (применительно к общеобразовательным и профессиональным программам), максимальный объем учебной нагрузки обучающихся, требования к уровню подготовки выпускников. Указанные стандарты и их компоненты утверждаются на федеральном уровне соответствующими центральными органами исполнительной власти. И Конституция России, и Федеральный Закон «Об образовании» в целом определяют государственную политику в сфере образования» [48].

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

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

Вторая проблема созвучна с первой - это техническое оснащение, компьютеризация и умение учителя всем этим пользоваться.

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

«Необходимыми условиями создания образовательного пространства, способствующего самоопределению учащегося основной ступени, является введение предпрофильной подготовки. Проект предпрофильной подготовки требует изменения характера работы учителей, который заключается в постановке различных задач целевого назначения, задач, связанных с подготовкой молодого поколения к жизни. В связи с тем, без точного знания индивидуальности каждого ученика и всего класса в целом, ученикам предлагается с помощью активизирующих методик сопоставить их потенциальное профессиональное “хочу” и “могу”» [40].

«До предпрофильной подготовки у многих учащихся вообще может отсутствовать понятие «хочу», поэтому задача предпрофиля - сформировать у них интерес к какому-либо профилю. Предпрофильная подготовка достигнет своей цели, если девятиклассники осознанно сделают свой выбор, если не произойдет такого: «Я хочу в 10-й класс, но не знаю, почему». Предпрофильная подготовка и профильное обучение не только для сильных и способных, а для всех детей» [41].

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

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

необходима разработка программно -дидактического материала,

авторское решение в составлении учебно - тематического плана;

выбор альтернативных учебно-тематических комплексов, рекомендованных МО РФ;

применение современных методов, форм, приемов обучения» [40],[41]. К числу таких методов внеурочной деятельности относятся: введение факультативных курсов и курсов по выбору в рамках предпрофильной подготовки.

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

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

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

«Рабочие программы учебных предметов, курсов, в том числе внеурочной деятельности, разрабатываются на основе требований к результатам освоения основной образовательной программы основного общего образования с учетом программ, включенных в ее структуру» [48].

Рабочие программы курсов внеурочной деятельности должны содержать:

результаты освоения курса внеурочной деятельности;

содержание курса внеурочной деятельности с указанием форм организации и видов деятельности;

тематическое планирование.

План внеурочной деятельности обеспечивает учет индивидуальных особенностей и потребностей обучающихся через организацию внеурочной деятельности.

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

«План внеурочной деятельности определяет состав и структуру направлений, формы организации, объем внеурочной деятельности на уровне основного общего образования (до 1750 часов за пять лет обучения) с учетом интересов обучающихся и возможностей организации, осуществляющей образовательную деятельность» [47].

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

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

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

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

Факультативные занятия.

Значение факультативных занятий.

«В учебные планы общеобразовательных школ включены факультативные занятия по предметам, которые изучаются по выбору самих учащихся. Факультативные занятия как форма обучения введены в конце 60-х начале 70-х гг., когда проводилась одна из очередных перестроек содержания школьного образования. Свое название они получили от латинского слова facultatis, что означает возможный, необязательный, предоставляемый на выбор» [3].

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

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

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

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

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

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

«Современные факультативы - особая организационная форма учебно- воспитательной работы, отличающаяся и от урока, и от внеклассной работы. В то же время подчёркивается, что факультативы имеют много общего с уроками и внеклассными занятиями. Как и уроки, факультативные занятия проводятся по утверждённым программам, на этих занятиях применяют общие с уроком методы обучения и формы организации самостоятельной познавательной деятельности учащихся. Сходство с предметными кружками состоит в том, что факультатив, как и кружок, объединяет группу учащихся на основе общих интересов, добровольности выбора этой формы обучения. На факультативных занятиях применяются некоторые формы и методы, характерные для внеклассных занятий. Тем не менее учитель должен помнить, что факультативы не заменяют внеклассную работу по предмету. Являясь самостоятельной частью учебно - воспитательной работы в школе, факультативы могут дополняться внеклассными (кружковыми) занятиями, на которых учащиеся в ещё большей степени углубляют и расширяют свои знания и умения. Отмечено, что факультативные курсы организуются по новейшим проблемам науки, техники и культуры. Обращается особое внимание на то, что факультативные занятия являются одной из гибких форм более полного отражения в школьном образовании современных достижений науки, техники, культуры и учёта местных особенностей каждой школы, поэтому они позволяют вносить существенные дополнения в содержание образования, трудовой и политехнической подготовки учащихся без изменения учебного плана, программ и учебников основного курса средней школы. При этом считается, что изучение факультативных учебных предметов в соответствии с желаниями и способностями школьников повышает эффективность их учебных занятий, является важным средством развития у них интереса к науке и искусству, углубляет, делает более устойчивыми и целенаправленными их интересы к определённым видам практической деятельности, готовит учащихся к самообразованию по окончании школы» [49].

Содержание и организация факультативных занятий.

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

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

«К сожалению, в школах они нередко используются не для углубления знаний и развития способностей учащихся, а для преодоления их отставания в овладении программным материалом, что, естественно, искажает их смысл и дидактическое назначение» [17].

Курсы по выбору и элективные курсы

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

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

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

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

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

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

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

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

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

Предметные кружки и научные общества.

Если учебная работа в школе поставлена хорошо, то на занятиях по каждому предмету появляются учащиеся, которые стремятся к расширению и обогащению своих знаний, к техническому творчеству, к проведению опытной работы по биологии и т.д. Это обусловливает необходимость организации работы предметных кружков и научных обществ школьников. Кружки создаются на добровольных началах отдельно из учащихся параллельных классов или же, если параллельных классов нет, из учащихся 5 - 6, 7 - 8 и т.д. классов. Руководство работой кружков осуществляют учителя-предметники.

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

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

Олимпиады, конкурсы, выставки ученического технического творчества.

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

.3 Психологические особенности учащихся 8 - 9 классов

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

Можно сделать вывод о том, что для каждого возраста существуют «ведущие психологические функции» по Л. С. Выгодскому и специфическая «социальная ситуация» и своя ведущая деятельность по А. Н. Леонтьеву.

«Для нашего исследования необходимо проанализировать психологические особенности учащихся основной школы» [11].

класс (13,14 лет ).

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

«У восьмиклассника становление теоретического рефлексивного мышления тесно связано с развитием воображения, что дает импульс к творчеству: подростки начинают писать стихи, серьезно заниматься разными видами конструирования и т. п. Существует и другая линия развития воображения, когда все чувства и потребности, переполняющие подростка, выплескиваются в воображаемой ситуации. Неудовлетворенные в реальной жизни желания легко исполняются в мире фантазий: замкнутый подросток, которому трудно общаться сo сверстниками, станoвится герoем, и ему рукоплещет толпа. Игра воображения не только доставляет удовольствие, но и приносит успокоение. В своих фантазиях подросток лучше осознает собственные влечения и эмоции, впервые начинает представлять свой будущий жизненный путь» [52].

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

Социальная ситуация развития. «В 8-ом классе дети намного больше общаются со сверстниками, чем со взрослыми. Круг общения подростка со сверстниками не ограничивается близкими друзьями, напротив он становится гораздо шире, чем в предыдущих возрастах. У детей в это время появляется много знакомых и, что еще более важно, образуются неформальные группы или компании. Подростков может объединять в группу общие интересы, занятия, способы развлечений, место проведения свободного времени. То, что получает от группы подросток и что он может дать ей, зависит от уровня развития группы, в которую он входит» [43].

Мотивация. «Главная мотивационная линия 7 - 8-х классов связана с активным стремлением к личностному самосовершенствованию. Подростки начинают систематически заниматься самовоспитанием. Они задумываются над возможностями интеллектуального и личностного общения, самосовершенствования и предпринимают для этой цели сознательные, целенаправленные усилия. Типичной целью восьмиклассника является волевое и физическое самосовершенствование, а задачами - улучшение волевых качеств личности, таких, как уверенность в себе и др., через применение специальных средств и упражнений, физическое развитие» [42].

Новообразование. Центральным новообразованием младшего подросткового возраста (11-13 лет) считается чувство взрослости - отношение подростка к себе как к взрослому, ощущение и осознание себя в какой-то мере взрослым человеком. Чувство взрослости восьмиклассника проявляется:

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

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

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

класс (14-15 лет ).

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

«При переходе из 8-го в 9-тый класс у подростков наблюдается скачок в овладении такими операциями, как классификация, аналогия, обобщение и др., устойчиво проявляется рефлексивный характер мышления: дети анализируют операции, которые они производят, способы решения задач. Эти умения развиваются в процессе школьного обучения, при овладении знаковыми системами, принятыми в математике, физике и химии» [38].

Ведущий вид деятельности. «В 9-ом классе ведущим видом деятельности является интимно-личностное общение. Оно пронизывает всю жизнь подростков, накладывая отпечаток и на учение, и на учебные занятия, и на отношения с родителями. Если потребность в полноценном общении со значимыми взрослыми и сверстниками не удовлетворяется, у детей появляются тяжелые переживания» [34].

Социальная ситуация развития. «В 9-ом классе детей тянет друг к другу, их общение настолько интенсивно, что говорят о подростковой «реакции группирования». Подросток может входить одновременно в несколько групп, например, в одну из групп класса, в компанию своего двора и группу, сложившуюся на занятиях в спорткомплексе. Иногда значительное влияние на личность оказывают подростковые группы, образующиеся в летних лагерях. То, что получает от группы подросток и что он может дать ей, зависит от уровня развития группы, в которую он входит» [18].

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

Новообразование. «В 14 лет начинается переходный период между подростковым и юношеским возрастом. В 9-том классе решается вопрос о дальнейшей жизни: что делать - продолжить обучение в школе, пойти в училище или работать? По существу, от старшего подростка общество требует профессионального самоопределения, хотя и первоначального. При этом он должен разобраться в собственных способностях и склонностях, иметь представление о будущей профессии и о конкретных способах достижения профессионального мастерства в избранной области. Это сама по себе сложная задача. Еще более она усложняется в наше время - переломный исторический период. Девятиклассникам не вполне ясно, что их ждет впереди, и это неопределенное будущее вызывает у них опасения, страхи и повышенный уровень тревожности» [22].

Общение. «Личностная нестабильность порождает противоречивые желания и поступки: подростки стремятся во всем походить на сверстников и пытаются выделиться в группе, хотят заслужить уважение, требуют верности и меняют друзей. В 14 лет, переходный период к ранней юности, у подростка притупляется острота восприятия сверстников. Больший интерес начинают вызывать взрослые, чей опыт, знания помогают ориентироваться в вопросах, связанных с будущей жизнью» [6],[39].

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

«Графовые задачи обладают рядом достоинств, позволяющих использовать их для развития воображения и улучшения логического мышления детей, начиная начальной и заканчивая старшей школой. Таким образом, графы, используемые при решении задач, в которых наглядно представляются соотношения между искомыми величинами, помогают ученикам осмыслить проблемную ситуацию и найти возможный путь ее решения. Математические связи приобретают для учеников наглядный смысл, а при их использовании происходит закрепление и углубление материала, а также развитие математических способностей учеников» [14].

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

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

Графы в школьных учебниках по математике

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

В учебнике «Математика 6 класс» Н. Я. Виленкина на странице 95 представлена задача № 585: «На озере находятся 7 островов, которые соединены между собой мостами так, как показано на рисунке. На какой остров должен доставить катер путешественников, чтобы они могли пройти по каждому мосту и только один раз? С какого острова катер должен снять этих людей? Почему нельзя доставить путешественников на остров А?» [8].

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

Задача № 23 на странице 140: «На поверхности куба найдите кратчайший путь:

а) из точки А в точку С через точку В;

б) из точки А в точку С, который пересекал бы все боковые ребра куба, кроме ребра АС.»

В виде графов даны некоторые задания, например, задачи № 254 и №347 на страницах 41 и 57: «Найдите пропущенные числа».

Кроме того, в учебнике есть задачи на лабиринты. Задача № 512 на странице 83: «Нужно срочно доставить 9 пакетов в пункты, указанные на плане звездочкой. Посыльный, посмотрев на план, быстро сообразил, как ему ехать. Он вручил пакеты, объехав пункты, ни разу не проезжая дважды одним и тем же путем. Какой маршрут выбрал посыльный?»

Автор использует графы и для объяснения нового материала, например, изучая тему «Разложение на простые множители», в начале параграфа он изображает граф - дерево, при помощи которого он показывает на какие множители можно разложить число.

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

«В учебнике «Геометрия 7 - 9 классы». И. М. Смирнова, В. А. Смирнов на теорию графов выделено 3 параграфа: 24. Графы. 25. Теорема Эйлера. 26. Проблема четырех красок. В главе «Кривые и графы», содержащей данные параграфы, представлено большое количество задач и вопросов по разным темам теории графов, например, нарисовать одним росчерком фигуры, изображенные на рисунке, изобразить графы по заданным параметрам, что-то доказать, привести примеры графов» [44].

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

Графы в сборниках занимательных задач

«В сборнике «Математические головоломки и развлечения» М. Гарднера много задач решено с использованием графов, кроме того рассмотрены разделы теории графов, такие как лабиринты и проблема четырех красок» [12].

«В пособии «Подумай и ответь. Логические задачи (выпуск 2)» Заесёнка В.П. теория графов изучается при помощи занимательных задач, более подробно в ней рассматриваются эйлеровы графы» [19].

«Пособие «Теория графов в занимательных задачах» О.И. Мельникова полностью посвящено решению задач при помощи теории графов, кроме того в нем даются определения, теоремы, следствия теории графов. Некоторые примеры задач» [28].

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

Задача №128. «Шесть островов на реке в парке «Лотос» соединены мостами. Можно ли, начав прогулку на одном из островов, пройти по каждому из мостиков ровно один раз и вернуться на тот же остров? В случае отрицательного ответа определите, сколько мостиков и между какими островами нужно построить, чтобы такая прогулка стала возможной» [9].

Задача №48. «Докажите, что число людей, когда - либо живших на Земле и сделавших нечетное число рукопожатий, четно» [9].

Задача № 131. «Экспозиция картинной галереи представляет собой систему коридоров, на обеих стенах которых развешаны картины. Можно ли предложить такой маршрут осмотра экспозиции, при котором посетитель проходит вдоль каждой стены ровно один раз?» [9].

«Занимательные задачи по теории графов» Мельников О.И. В данном пособии описаны основы теории графов в занимательной форме. «Книга предназначена именно для школьников, ее изучение на кружках и факультативах в средней школе способствовало бы развитию дискретного мышления учеников. Пособие может использоваться как школьниками, так и учителями» [29].

Задача №25. «В шахматном турнире по круговой системе участвуют семь школьников. Известие что Ваня сыграл шесть партий. Толя - пять. Леша и Дима - по три, Семен и Илья - по две. Женя - одну. С кем сыграл Леша?» Задача №29. «Спортивное соревнование проводится по круговой системе. Это означает, что каждая пара игроков встречается между собой ровно один раз. Докажите, что в любой момент времени найдутся хотя бы два игрока, проведшие одинаковое число встреч» [9].

Задача №56. «Чемпионат лагеря по футболу проводился по круговой системе. За победу в матче давалось 2 очка, за ничью - 1, за поражение - 0. Если две команды набирали одинаковое количество очков, то место определялось по разности забитых и пропущенных мячей. Чемпион набрал семь очков, второй призер - пять, третий - три. Сколько очков набрала команда, занявшая последнее место» [9].

Задача №130. «В городе на каждом перекрестке сходится четное число улиц, а тупиков в городе нет. Докажите, что улицы города можно так разбить на маршруты патрулирования полицейскими машинами, что любой маршрут начинается и заканчивается на одном и том же перекрестке, содержит каждый свой промежуточный пункт ровно один раз, при этом маршруты для разных машин не будут иметь одних и тех же отрезков улиц между перекрестками» [9].

Задача №135. «Можно ли нарисовать фигуру, не отрывая карандаша от бумаги, причем каждую точку фигуры карандаш должен проходить только один раз?» [9].

Как видно из анализа учебников и занимательной литературы, материалы по изучению общей теории графов в школе уже созданы такими авторами, как Смирнов и Смирнова, Мельников, Алфимова и др., однако, как правило, в предложенных разработках рассматриваются только общие простейшие понятия теории графов. Классические типы графов (двудольные, регулярные, плоские, эйлеровы, гамильтоновы и др.) рассматриваются лишь обзорно. В то же время указанные специальные виды графов обладают интересными свойствами, связаны с множеством теоретических, прикладных и занимательных проблем, их история связана с именами многих известных ученых и отражает историю развития математической науки в целом. В этой связи методически целесообразно разрабатывать курсы, в которых помимо общих базовых положений теории графов углубленно рассматриваются свойства графов того или иного специального вида. Курс «Эйлеровы графы» представляет собой одну из таких попыток. «Он посвящен одному из самых известных классов графов, появление которых относят к 1736 году, когда Л. Эйлер решил задачу о Кенигсбергских мостах. Эта дата считается и датой рождения теории графов в целом» [1],[28],[44].

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

Глава II. Методическое обеспечение факультативного курса «Эйлеровы графы» для учащихся 8 - 9 классов

.1 Основные характеристики факультативного курса

Курс предназначен для учащихся 8 - 9 классов.

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

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

Программа факультативного курса состоит из 3 разделов. На изучение курса отводится 15 часов.

Тема 1. Основные понятия теории графов. Введение в теорию графов, исторический аспект. Решение задач без введения понятия графа. Основные понятия теории графов: определение графа, вершина графа, степень вершины графа, четность (нечетность) вершины графа. Лемма о рукопожатиях. Решение задач, связанных с основными определениями. Примеры графов. Определения пустого и полного графа. Подграфы. Маршрут, путь и цикл. Связный граф. 4 часа

Тема 2. Эйлеровы графы. История вопроса. Задача о Кёнигсбергских мостах. Определения эйлерового пути, эйлерового цикла, эйлерова графа, полуэйлеровой цепи, полуэйлерового графа. Критерий эйлеровости и следствия. Алгоритм Флёри. Применение эйлеровых графов для решения задач.8 часов.

Тема 3. Гамильтоновы графы. Определение гамильтоновой цепи, гамильтонова графа. Задача коммивояжера. Решение задачи коммивояжера методом ветвей и границ. Применение гамильтоновых графов для решения задач. 4 часа.

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

.2 Математическое содержание факультативного курса

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

. Введение в теорию графов.

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

Для начала давайте рассмотрим с вами такую задачу.

Задача 1. Изобразите молекулу такого химического элемента как октан, зная его формулу С𝟖Н𝟖. (В качестве подсказки изобразим молекулу воды, формула которой НО ).

Решение.

Молекула октана.

Задача 2. Лист бумаги Плюшкин разрезает на три части. Некоторые из полученных листов он также разрезает на три части. Несколько новых листиков он вновь разрезает на три более мелкие и т. д. Сколько Плюшкин получает листиков бумаги, если разрезает k листов?

Решение. Листы бумаги обозначим на рисунке кружками. Кружки, соответствующие листам, которые разрезаются, закрасим целиком; остальные кружки оставим не закрашенными.

На рисунке мы можем увидеть, что при разрезе одного листка на три части число листков увеличивается на два (появляются три новых вместо одного). Если же было разрезано k листов, то образовалось 1 + 2k листов.

На рисунке показано пять разрезаний. Сколько в этом случае получено листов?

Если посмотреть на схемы на рисунках 1 и 2 напоминают ветку дерева с листочками? Математики, обратив внимание на это сходство, назвали такие схемы «деревьями».

Задача 3. Утверждают, что в одной компании из пяти человек каждый знаком с двумя и только с двумя другими. Возможна ли такая компания?

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

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

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

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

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

Запишем определение на математическом языке.

Определение. Графом называется упорядоченная пара (𝑽, 𝑬), где 𝑽 ≠ ∅ - конечное множество вершин, 𝑬 - конечное множество ребер. Будем считать, что элементы из 𝑽 - вершины, а элементы 𝑬 - ребра.

Пример 1. В графе изображенном на рисунке 𝑽 - множество вершин графа, 𝑬 множество ребер графа.

Задание 1. Построить граф, у которого 6 вершин и 10 ребер. Решение. Возможные вариации графа.

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

Пример 2. На рисунке изображен граф с кратными ребрами в нем 5 вершин и 10 ребер.

Пример 3. На рисунке изображен граф с кратным ребром и петлями.

Задание 2. Построить граф, у которого 4 вершины и было хотя бы два кратных ребра.

Решение. Возможные вариации графа.

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

Пример 4. На рисунке изображен граф, у которого все вершины имеют степень 3, а, следовательно, все вершины нечетные.

Задание 3. Посчитайте степень каждой вершины графа.

Решение.

Степень вершины 1= 3;

Степень вершины 2 = 3;

Степень вершины 3 = 2;

Степень вершины 4 = 1 - является висячей вершиной;

Степень вершины 5 = 2;

Степень вершины 6 = 3;

Степень вершины 7 = 0 - является изолированной вершиной.

Лемма «о рукопожатиях». Сумма степеней вершин любого графа равна удвоенному числу его ребер.

Доказательство.

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

Задание 4. В Российской Федерации 4 автономных округа (АО), В Ненецком АО - 1 город, в Ханты - Мансийском АО - 14 городов, Чукотском АО - 1 город, и Ямало - Ненецком АО - 8 городов. Из каждого города выходит по 3 дороги, кроме административных центров, откуда выходит 7 дорог. Сколько всего дорог в автономных округах?

Решение. Сложим количество городов в АО: 1+14+1+8=24, далее находим количество всех дорог, выходящих из всех городов: 20×3+4×7=88. Это число - количество концов всех дорог. Поскольку каждая дорога имеет 2 конца, то количество дорог будет вдвое меньше, а именно 44. Другими словами, мы имеем граф на 24 вершинах, в котором 20 вершин имеют степень 3 и 4 - степень 7. По лемме о рукопожатиях, сумма степеней данного графа равна удвоенному числу его ребер, то есть 2m=88, откуда следует, что m=44.

Задания для проверки усвоения материала.

Изобразите граф, у которого 7 вершин и 9 ребер, запишите его множество вершин и множество ребер.

Изобразите граф с кратными ребрами, количество вершин произвольное.

Изобразите граф, у которого 1 вершина и 1 ребро.

) Изобразите граф, все вершины которого нечетные.

Изобразите граф с изолированной, висячей и остальными четными вершинами.

Изобразите граф с таким набором степеней вершин: {1, 4, 3, 3, 3, 4}.

. Примеры графов.

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

На рисунке изображен пустой граф с 7 вершинами.

Определение. Граф называется полным, если любые две его вершины соединены ребром. Обозначается 𝑲 ≥ .

На рисунке приведены примеры полных графов

Определение. Граф ′ =< 𝑽′, 𝑬′ > называется подграфом графа =<𝑽, 𝑬 >, если 𝑽′ - подмножество 𝑽, и 𝑬′ - подмножество 𝑬.

Определение. Пусть - граф. Маршрутoм в называется такая кoнечная или бесконечная последoвательность ребер 𝑺 = (… , 𝑬, 𝑬, 𝑬, … , 𝑬, … ), (1) что каждые два сoседних ребра имеют oбщую кoнцевую точку. Таким образом, мoжнo написать

Если в (1) нет ребер, предшествующих 𝑬, то называется начальной вершиной 𝑺, а если нет ребер, следующих за 𝑬, то называется конечной вершиной �〱.

Если маршрут 𝑺 имеет как начальную вершину, так и кoнечную вершину, тo мoжнo написать 𝑺 = 𝑺 (3) и назвать и концевыми точками, или концами маршрута 𝑺. Будем говорить также, что 𝑺 есть маршрут длины, соединяющий, то маршрут называется циклическим.

Определение. Маршрут называется цепью, а циклический маршрут - циклом, если каждое егo ребрo встречается в нем не более oдногo раза; вершины в цепи мoгут повторятся и нескoлько раз. Цепь называется oткрытoй, если ее концевые вершины различны, в противном случае она называется замкнутой. Нециклическая цепь называется простой цепью, если в ней никакая вершина не пoвтoряется.

Определение. Дан граф. Две вершины называются связными, если существует маршрут вида (1) с концами. Граф называется связным, если любая пара вершин связна.

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

. Введение

Задача о кёнигсбергских мостах.

Отцoм теoрии графов является Леoнард Эйлер (1707-1782) решивший в 1736 г. ширoко известную в то время задачу называвшуюся проблемой кёнигсбергских мостов. В горoде Кёнигсберге былo два oстрова, соединенных семью мостами с берегами реки Прегoля и друг с другoм так, как показано на рис. 1.

Рисунок 1. Парк в городе Кёнигсберге 1736г.

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

Для доказательства тoго, что задача не имеет решения, Эйлер обозначил каждую часть суши тoчкой (вершиной), а каждый мост - линией (ребром), соединяющие соответствующие тoчки. Получился «граф». Этот граф показан на рис.2, где тoчки отмечены теми же буквами, что и четыре части суши на рис.1.

Рисунок 2. Граф к задаче о кёнигсбергских мостах.

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

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

Понятия эйлеровых графов.

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

Определение. Замкнутая эйлерoва цепь в графе называется эйлерoвым циклoм.

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

Определение. Граф, имеющий эйлерoв цикл, называется эйлерoвым графoм.

Определение. Граф называется пoлуэйлеровым, если oн сoдержит полуэйлерову цепь.

Теорема 1 (критерий Эйлера). Граф является эйлеровым графом тогда и только тогда, когда связен;

Все егo степени четны.

Доказательство: очевидно, чтo 1) условие неoбхoдимo. Далее, каждый раз, когда эйлерoв цикл проходит через какую-то вершину, он должен войти в нее по одному ребру и выйти по другому, поэтому условие 2) также необходимо.

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

Графы имеют четные степени, тоже должно быть справедливо и для остающегося графа. Так как граф связен, в должна найтись вершина, соединяющаяся также ребрам из. Из можно построить новую цепь′, содержащую ребра только из. Снова такая цепь может закончится только при возвращении в. Но тогда из можно сoставить нoвый цикл, кoтoрый возвращается и сoдержит больше ребер, чем. Если не является эйлеровым циклом, тo этo построение повторяется.

Когда процесс закончится, эйлеров цикл будет построен.

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

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

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

Тео р ема . Если граф обладает эйлеровым путём с концами не совпадает с, то граф связный - единственные нечётные его вершины.

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

Теорема (обратная). Если граф связный и единственные нечётные вершины его, то граф обладает эйлеровым путём с концами.

Доказательство: Вершины могут быть соединены ребром в графе, а могут быть соединены.

Если  не соединены ребром, то к графу добавим новое ребро, тогда все вершины его станут чётными. Новый граф (по теореме 1) обладает эйлеровым циклом. Начнём его из вершины по ребру. Заканчивается путь тоже в вершине. Если удалить теперь из полученного цикла ребро, то останется эйлеров путь с началом и концом или началом и концом.

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

Дадим алгоритм построения эйлеровой цепи в данном эйлеровом графе. Этот метод известен под названием алгоритма Флёри.

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

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

на каждом этапе идём по мосту только тогда, когда нет других возможностей.

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

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

Пример нахождения эйлерова цикла с помощью алгоритма Флёри.

Задача .

Найти эйлеров цикл с помощью алгоритма Флёри в данном графе и сделать вывод, является ли данный граф эйлеровым.

Решение. Для начала необходимо обозначить вершины графа.

Выбираем произвольную вершину, например, идем по ребру к вершине. Стираем это ребро. Вершина остается, так как она не изолирована.

Получили следующий граф

Далее повторяем 1, соблюдая правила алгоритма Флёри, до тех пор, пока не найдем эйлеров цикл.

Из вершины идем по ребру к вершине. Стираем это ребро. Получили следующий граф

Из вершины идем по ребру к вершине. Стираем это ребро. Получили следующий граф

Из вершины идем по ребру к вершине. Стираем это ребро.

Получили следующий граф

Из вершины идем по ребру к вершине. Стираем это ребро и вершину так как она станет изолированной. Получили следующий граф

Из вершины идем по ребру к вершине. Стираем это ребро. Получили следующий граф

Из вершины идем по ребру к вершине. Стираем это ребро.

Получили следующий граф

Из вершины идем по ребру к вершине. Стираем это ребро. Получили следующий граф

Из вершины e идем по ребру к вершине. Стираем это ребро. Получили следующий граф

Из вершины идем по ребру к вершине. Стираем это ребро.

Получили следующий граф

Из вершины идем по ребру к вершине. Стираем это ребро. Получили следующий граф

Из вершины идем по ребру к вершине. Стираем это ребро. Получаем изолированную вершину.

Следовательно, мы нашли эйлеров цикл, так как он содержит все вершины и ребра.

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

Применение эйлеровых графов для решения задач.

Задача 1.

Определить, сколько цепей необходимо для покрытия графа.

Решение.

Данный граф имеет 2 нечетные вершины, следовательно, его можно покрыть единственной цепью.

Пример цепи покрывающей граф.

Задача 2. «Муха в банке».

«Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все двенадцать ребер куба, не проходя дважды по одному ребру. Подпрыгивать и перелетать с места на место не разрешается» [28].

Решение.

Для начала необходимо определить является ли куб эйлеровым графом? Куб представляет собой граф, у которого все вершины имеют степень 3. Для того чтобы был эйлеровым нужно, чтобы все его вершины были четными, а это условие в данном случае не выполняется. Следовательно, граф не является эйлеровым. Значит, муха не сможет обойти все ребра куба, не проходя по одному ребру дважды.

Задача 3.

«Дан план подземелья в одной из комнат которого скрыты богатства рыцаря. После смерти рыцаря его наследники нашли его завещание, в котором было сказано, что для отыскания сокровищ достаточно войти в одну из крайних комнат подземелья, пройти через все двери, причем в точности по одному разу через каждую, сокровища скрыты за той дверью, которая будет пройдена последней. В какой комнате были спрятаны сокровища?» [28].

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

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

Данный граф имеет эйлеров путь, так, как только две вершины имеют нечётную степень, это вершины 6 и 18. Значит, вход и выход могут быть только в вершинах 6 и 18.

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

Задача 4.

«На озере семь островов, которые соединены собой мостами так, как показано на рисунке. На какой остров должен доставить катер путешественников, чтобы они могли пройти по каждому мосту и только один раз? С какого острова катер должен снять этих людей?» [28].

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

Данный граф имеет эйлеров путь, так, как только две вершины B и D имеют нечётную степень. Следовательно, катер может привести путешественников на один из них, а забрать с другого.

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

Задача 5.

«В небольшой роще находится заяц. Выскочив из норы и бегая от дерева к дереву, он оставлял следы и, наконец, спрятался под деревом. Опытный охотник определил, что между каждыми двумя деревьями заяц пробегал не более раза. Под каким деревом находится нора зайца, и где сейчас он спрятался?» [28].

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

Задача 6.

Найдите сами маршруты.» [28].

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

Решение. Естественным образом представим Зеленый город (без набережной) в виде графа, вершины которого обозначают перекрестки города, а ребра - улицы.

В построенном графе 8 вершин нечетной степени, следовательно, граф не является эйлеровым. Соединим попарно вершины нечетных степеней, например, 2 и 7, 8 и 15, 4 и 13, 14 и 17.

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

Удалим добавленные ребра. Цикл распадется на четыре цепи, которые будут соответствовать автобусным маршрутам.

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

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

.3 Методические рекомендации для учителя

Рекомендации по проведению факультативного курса

Факультативный курс «Эйлеровы графы» рассчитан на 8 занятий, на его изучение целесообразно выделить 15 часов, следуя представленному выше примерному учебно-тематическому плану.

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

Примеры задач.

Задача 1. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля - Меркурий; Плутон - Венера; Земля - Плутон; Плутон - Меркурий; Меркурий - Венера; Уран - Нептун; Нептун - Сатурн; Сатурн - Юпитер; Юпитер - Марс и Марс - Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса?

Задача 2. При встрече каждый из одноклассников пожал руку другому (каждый пожал каждому). Сколько рукопожатий было сделано, если друзей было трое; четверо?

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

Примеры задач.

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

Задача 2. Изобразите граф со следующим набором степеней вершин:

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

Пример контрольной работы.

№1. При встрече каждый из одноклассников пожал руку другому (каждый пожал каждому). Сколько рукопожатий было сделано, если друзей было трое; четверо?

№2. Докажите, что число перекрестков любого города, в котором встречается нечетное число улиц - четно.

№3. Постройте, если это возможно, графы со следующим набором степеней вершин

№4. Найти все подграфы графов K1, K2, K3.

№5. В соревновании по круговой системе с 12 участниками провели все встречи. Сколько встреч было сыграно?

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

Примеры задач.

Задача 1. Изобразите эйлеров граф на n вершинах

Изобразите полуэйлеров граф на n вершинах

Задача 2. Какие из указанных на рисунках графов являются эйлеровыми?

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

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

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

Примеры задач.

Задача 1. Мышка грызет куб сыра с ребром 3, разбитый на 27 единичных кубиков. Когда мышка съедает какой-либо кубик, она переходит к другому кубику, имеющему общую грань с предыдущим. Может ли мышка съесть весь куб, кроме центрального кубика.

Задача 2. На пир при дворе короля Артура собралось четное количество рыцарей, которые либо дружат, либо враждуют. Оказалось, что у каждого из рыцарей друзей больше, чем врагов. Доказать, что волшебник Мерлин может так рассадить рыцарей за круглым столом, что справа и слева от каждого из них будет сидеть друг.

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

Программа факультативного курса «Эйлеровы графы» является общей для учащихся всех типов школ. В то же время учитель при проведении занятий сам выбирает объем материала, степень строгости его изложения, методы и приемы обучения в соответствии со своими склонностями и возможностями, с учетом возрастных особенностей учащихся и их подготовленности. Следует обратить особое внимание на практическую часть программы факультативного курса. Дело в том, что учащиеся успевают на занятии сравнительно мало (примерно 3-5 заданий), и для того, чтобы материал был полностью усвоен, необходимо регулярно повторять учащимся то, что им непонятно, не спешить при изложении материала. Нужно отметить также, что приведенная тематика практических занятий примерна и может изменяться с учетом имеющихся условий работы учителя, особенностей конкретной группы школьников, интересов учащихся и учителя.

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

Рекомендуемые формы и методы проведения занятий Методы: Исследовательский метод, лекционный метод, объяснительно -иллюстративный метод, проблемный метод, частично-поисковый метод обучения.

Формы: теоретическое обучение (лекционные и семинарские занятия); практическое обучение (практические занятия); интерактивные формы: игровые, дискуссионные (дебаты, дискуссии, круглый стол).

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

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

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

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

Рекомендации учителю по применению графов на других занятиях по математике

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

«Расширение «занимательной составляющей» содержания на основе использования проанализированных выше сборников занимательных задач, позволит использовать имеющиеся разработки для организации математического кружка для 6-8 классов, в то время как усиление математического фундамента (на базе книг Оре, Деза, Уилсона, Бержа и др.) приведет к созданию элективного курса для старшеклассников» [5],[16],[37],[46].

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

Элементы теории графов можно применять и на уроках математики. Прежде всего, при использовании учебника «Геометрия 7 - 9 классы»

И. М. Смирновой и В. А. Смирнова, в ходе знакомства с теорией графов (24. Графы. 25. Теорема Эйлера. 26. Проблема четырех красок) можно использовать разработанные нами задачи для обогащения имеющегося в учебнике банка заданий. Кроме того, в ряде случае целесообразно выделить (содержательно опираясь на предложенные для факультативного курса материалы) изучение эйлеровых графов в отдельное занятие. [44]

«При прохождении темы «Разложение числа на множители» можно для наглядности изобразить граф-дерево. Кроме того, деревья подойдут для объяснения решения задач с перебором всех возможных вариантов и других комбинаторных задач» [35],[36],[9],[30].

Примеры таких задач.

Запишите все трёхзначные числа, в записи которых используются цифры 2, 5 и 6 без повторения.

Сколько двузначных чисел можно записать, используя цифры 1, 2 и 3?

В правлении фирмы входят 5 человек. Из своего состава правление должно выбрать президента и вице-президента. Сколькими способами это можно сделать?

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

Примеры таких задач. Какое число получится в конце цепочки?

Вместо звездочек в записи вычислений цепочкой поставьте необходимые числа.

Восстановите цепочку вычислений:

. Опытно-экспериментальная проверка разработанного курса

Экспериментальная проверка разработанного факультативного курса «Эйлеровы графы» проводилась в школе № 1521 города Москвы в 2016 учебном году. Весь эксперимент был разбит на несколько этапов:

констатирующий эксперимент;

поисковый эксперимент;

обучающий и контролирующий эксперимент.

Целью первого, констатирующего, этапа эксперимента было изучение состояния математических факультативных курсов, проводимых в школе № 1521 города Москвы. Мы присутствовали на занятиях такого рода, изучали школьную документацию, проводили опросы, анкетирование и беседы с учителями и учениками. В частности, перед началом занятий курса «Эйлеровы графы» было проведено анкетирование 34 учащихся 9 классов, направленное на выявление их математических интересов и предпочтений.

Анкета.

Анкета №1 (выберете нужный ответ).

Ваше отношение к предмету "Математика":

Самый любимый предмет.

Интересуют только практические задания.

Обычный предмет, стоит на ровне со всеми остальными предметами.

Самый нелюбимый предмет.

Что Вам интереснее всего при изучении математики:

Теоретический материал.

Работа в коллективе при решении задач

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

Практическое применение изученного материала.

Посещаете ли Вы что-нибудь из ниже перечисленного:

. Справочная литература.

Посещаю математический кружок в школе.

Посещаю математический факультатив.

Не посещаю ничего.

Посещаю подготовительные курсы по математике в Вузе.

Если посещаете математический факультатив, укажите причину:

Углубление знаний по математике.

Расширение знаний по математике, т.е. сверх программы.

Подготовка к конкурсным экзаменам.

Другие причины.

Какую литературу Вы используете при выполнении домашней работы по математике:

Учебник, тетрадь с классными работами.

Дидактические материалы.

. Дополнительная литература.

.Выберете наиболее близкую Вам форму занятий:

Урок.

Факультатив.

Семинар

Лекция.

Сколько времени в среднем Вы тратите на выполнение домашнего задания?

Пользуетесь ли Вы знаниями по математике на других предметах?

Результаты анкетирования представлены в таблице №1, где указаны проценты всех опрошенных учащихся, давших определенный ответ на поставленный вопрос.

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

Однако есть учащиеся, для которых интересна история развития математики. Девятиклассники активно посещают математические кружок и факультатив, но целью этого посещения в основном является подготовка к выпускным и вступительным экзаменам. Анализируя ответы на 5 и 7 вопросы, мы сделали вывод, что учащиеся перегружены (см. диаграмму №1) и, чтобы посмотреть дополнительную литературу, у них просто не хватает времени. При ответе на 8 вопрос 65% учащихся сказали, что используют знания по математике на других предметах, в основном только как вычислительные навыки.

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

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

Третий этап был посвящен изучению элементов теории эйлеровых графов на 3 занятиях с учащимися 9 класса, и проверке качества усвоения изученного материала школьниками. При проведении занятий факультативного курса «Эйлеровы графы» были освещены только основные его разделы. Окончательно экспериментальная проверка включила следующие занятия: Занятие 1. - Введение в теорию графов-1час;

Занятие 2. - Основные понятия теории графов, примеры графов - 2 часа; Занятие 3. - Введение в теорию эйлеровых графов. Применение эйлеровых графов для решения задач-2 часа.

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

С целью выявления результатов обучения была проведена контрольная работа.

Пример варианта контрольной работы.

№1. При встрече каждый из одноклассников пожал руку другому (каждый пожал каждому). Сколько рукопожатий было сделано, если друзей было трое; четверо?

№2. Докажите, что число перекрестков любого города, в котором встречается нечетное число улиц - четно.

№3. Постройте, если это возможно, графы со следующим набором степеней вершин. Какие из них эйлеровы? Можно ли построить эйлеровы (полуэйлеровы) графы с указанными наборами степеней вершин?

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

Процентные результаты выполнения заданий представлены в таблице.

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

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

Заключение

Целью выпускной квалификационной работы «Методика проведения факультативного курса «Эйлеровы графы» для учащихся основной школы» являлась разработка факультативного курса «Эйлеровы графы» и методика его преподавания для учащихся 8 - 9 классов.

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

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

составлена психолого-педагогическая характеристика учащихся 8 - 9 классов;

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

разработано содержание факультативного курса «Эйлеровы графы» и методика его проведения;

проведена опытно-экспериментальная проверка эффективности предложенной методики.

Практическое значение работы заключается в том, что в ней были разработаны:

теоретический материал для преподавания факультативного курса «Эйлеровы графы»;

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

методические рекомендации для учителя.

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

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

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

1.      Алфимова А.С., Элементы теории графов. Учебное пособие для учащихся классов физико-математического профиля школ, гимназий, лицеев. - М.: МПГУ, 2009. - 70 с.

.        Бабанский Ю.К., Педагогика. - М.: Просвещение, 1988. - 479 с.

.        Балк М.Б., Балк Г.Д., Математический факультатив - вчера, сегодня, завтра, М.: Просвещение, 2007. - 176 с.

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

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

6.      Бурменская Г.В., Захарова Е.И., Карабанова О.А. и др., Возрастно- психологический подход в консультировании детей и подростков: Учеб. пособие для студентов. высших. учебных заведений. - М.: Издательский Центр «Академия», 2002. - 416 с.

.        Виленкин Н.Я., и др., Математика: Учебник для 5 класса средней школы - 2-е изд.- М.: Просвещение, 1992. - 304 с.

8.      Виленкин Н.Я., Чесноков А.С., Швацбурд С.И., Жохов А.И., Математика: Учеб. для 6 класса средней школы - 2-е изд. - М.: Просвещение, 1993. - 256 с.

.        Виленкин Н.Я., Виленкин А.Н., Сурвилло Г.С. и др., Алгебра: Учеб. пособие для учащихся 8 классов школ и классов с углубленным изучением математики/ под ред. Н.Я. Виленкина. - М.: Просвещение, 1995. - 256 с.

10.    Веленкин Н.Я., Алгебра 9 класс. - М.: Просвещение, 2008. - 271 с.

.        Выготский Л.С., Психология. - М.: ЭКСМО-Пресс, 2000. - 534 с.

.        Гарднер М., Математические головоломки и развлечения: 2-е изд., испр. и дополн./ Пер. с англ. - М.: Мир, 1999. - 447 с.

13.    Гарднер М., Математические досуги. - М.: Мир, 2010. - 268 с.

.        Гнеденко Б.В., Математическое образование сегодня. Сб. статей/ Сост. Титов В. А. - М.: Знание, 1974. - 64 с.1977. - 597с.

.        Данилов Ю.А., Избранные задачи: Сборник / под ред. Алексеева В.М. - М.: Мир, Деза Е.И., Модель Д.Л., Основы дискретной математики. - М: Либроком, 2011.- 224 с.

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

.        Еникеев М.И., Общая и социальная психология: Учебник для вузов. - М.: Изд- во гр. НОРМА-ИНФА М, 2000. - 640 с.

18.    Заесёнок В.П., Подумай и ответь (логические задачи). - М.: Инновационно- образовательный центр, 1996. - 32 с.

.        Зимняя И.А., Педагогическая психология. - Москва-Воронеж: Феникс, 2010. - 365 с.

.        Зыков А.А., Основы теории графов - М.: Наука, 1997. -272 с.

.        Кон И.С., Психология старшеклассника: пособие для учителей. - М.: Просвещение, 1980. - 192 с.

.        Коннова Л.П., Знакомьтесь, графы. - Самара: СИПКРО, 2001. - 107 с.

.        Конституция Российской Федерации. - М.: АСТ: Астрель, 2010. - 64 с.

.        Кордемский Б.А., Увлечь школьников математикой: (Материал для клас. и внеклас. занятий). - М.: Просвещение, 1981. - 112 с.

.        Кулагина И.Ю., Возрастная психология (развитие ребенка от рождения до 17 лет), учебное пособие, 4-е изд-е, - М.: «УРАО», 1998. - 175 с.

.        Макарычев Ю.Н. и др., Алгебра: Учеб. для 7 класса общеобразовательных учреждений / под ред. С.А. Теляковского. - 10-е изд. - М.: Просвещение, 2001. - 223 с.

27.    31. Мордкович А.Г., Алгебра. 8 кл.: Учеб. для общеобразоват. учреждений. -Мельников О.И., Теория графов в занимательных задачах. 3-е изд., испр. и доп.- М.: Либроком, 2009. - 232 с.

28.    Мельников О.И., Занимательные задачи по теории графов: учебно- методическое пособие. - М.: Либроком, 2001. - 162 с.

.        Мордкович А.Г., Алгебра. 7 кл.: Учеб. для общеобразоват. учреждений. - 3-е изд., доработ. - М.: Мнемозина, 2000. -160 с.

.        3-е изд., доработ. - М.: Мнемозина, 2001.-223 с.

.        Мордкович А.Г., Алгебра. 9 кл.: Учеб. для общеобразоват. учреждений. - 3-е изд., испр. - М.: Мнемозина, 2001. -192 с.

.        Мочалов Л.П., Головоломки: Книга для учащихся. - М.: Просвещение: АО«Учебная литература», 1996. - 190 с.

.        Мухина В.С., Возрастная психология: феноменология развития, детство, отрочество. - М.: «Академия», 1997. - 356 с.

.        Никольский С.М., Потапов М.К., РешетниковН.Н., Шевкин А.В., Математика. 6 класс: учеб. для общеобразоват. организаций. - 14-е изд. - М.: Просвещение, 2015. - 256 с.

.        Нурк Э.Р., Тельгмаа А.Э., Математика: Учеб. для 6 кл. средней школы. - 3-е изд. - М.: Просвещение, 1991. - 224 с.

.        Оре О., Графы и их применение. - М.: Наука, 1980. - 336 с.

.        Петровский А.В., Возрастная и педагогическая психология. Учеб. Пособие для студентов пед. ин-тов. - М.: Просвещение, 1973. - 288 с.

.        Потоцкий М.В., Психолого-педагогические основы обучения математике в средней школе. - М.: Прометей, 1992. - 112 с.

.        Распоряжение Правительства РФ от 29.12.2014 № 2765-р <Концепция Федеральной целевой программы развития образования на 2016 - 2020 годы> [Электронный ресурc]. - Режим доступа: http://government.ru/media/files/mlorxfXbbCk.pdf - (Дата обращения: 05.04.2016).

.        Распоряжение Правительства РФ от 29.12.2001 N 1756-р <О Концепции модернизации российского образования на период до 2010 года> [Электронный ресурc]. - Режим доступа: http://base.consultant.ru/cons/CGI/online.cgi?req=doc;base=EXP;n=242634 - (Дата обращения: 05.04.2016).

.        Реана А.А., Психология человека от рождения до смерти. - СПб.: «Прайм- ЕВРОЗНАК», 2002. - 656 с.

.        Рождественская Н.А., Как понять подростка: Учебное пособие для студентов факультетов психологии высших учебных заведений по специальностям 52100 и 020400 - «Психология». 2-е изд. - М.: Российское психологическое общество, 1998. - 18 с.

43.    Смирнов В.А., Смирнова И.М., Геометрия. 7 - 9 классы: учеб. для общеобразоват. Учреждений. - 2-е изд., испр. - М.: Мнемозина, 2007. - 376 с.

.        Совайленко В.К., Лебедева О.В., Математика 6 класс: Учебник для учащихся средней школы. - Ростов-на-Дону: Феникс, 1995. - 381 с.

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

.        Федеральный государственный образовательный стандарт основного общего образования (утвержден приказом Минобрнауки России от 17 декабря 2010 г.№ 1897).

.        Федеральный закон от 29.12.2012 N 273-ФЗ "Об образовании в Российской Федерации" общества [Электронный ресурc]. - Режим доступа: http://www.assessor.ru - (Дата обращения: 19.01.2016).

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

.        Фляйшнер Г., Эйлеровы графы и смежные вопросы. - М.: Мир, 2002. - 335 с.

.        Шуба М.Ю., Занимательные задания в обучении математике: Книга для учителя. -2-е изд. - М.: Просвещение, 1995. - 222 с.

.        Якиманская И.С., Столетов В.С., Каплунович И.Я. и др., Возрастные и индивидуальные особенности образного мышления учащихся / под. ред. И.С. Якиманской. - М.: Педагогика, 1989. - 221 с.