Размещено на http://www.allbest.ru/

РЕФЕРАТ

Объём работы: 56 станицы, из них … основного текста, 2 приложения и список использованных литературных источников (25 источников). В работе 60 рисунков, 1 таблица, 5 схем. Работа состоит из введения, двух глав, заключения и списка литературы.

КЛЮЧЕВЫЕ СЛОВА: ГРАФЫ, МАТЕМАТИКА, ОБУЧЕНИЕ, РЕШЕНИЕ ЗАДАЧ, ФАКУЛЬТАТИВНЫЕ ЗАНЯТИЯ, ШКОЛА.

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

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

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

Для достижения поставленной цели необходимо решить следующие задачи:

1) Изучить психолого-педагогическую и методическую литературу по проблеме обучения учащихся решению задач.

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

3) Отразить роль факультативных занятий как одной из форм внеклассной работы по математике.

4) Разработать содержание факультативных занятий по теме “Элементы теории графов” и методики их проведения.

5) Составить и подобрать задачи, решаемые с использованием теории графов.

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

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

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

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

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



СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. ВОПРОСЫ ТЕОРИИ ГРАФОВ ПРИ ОБУЧЕНИИ В СРЕДНЕЙ ШКОЛЕ

1.1 Роль и функции задач в обучении математике

1.2 Роль задач в развитии мышления учащихся

1.3 История и основные понятия теории графов

1.4 Графы как средство обучения учащихся поиску решения задач

ГЛАВА 2. МЕТОДИКА ОБУЧЕНИЯ УЧАЩИХСЯ РЕШЕНИЮ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ ГРАФОВ НА ФАКУЛЬТАТИВНЫХ ЗАНЯТИЯХ В ШКОЛЕ

2.1 Роль факультативных занятий как формы обучения математике

2.2 Содержание и программа факультативных занятий по теме “Элементы теории графов”

2.3 Методика проведения занятий по решению задач на факультативных занятиях по теме “Элементы теории графов”

2.3.1 Вводное занятие “Сфера применения теории графов”

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

2.3.3 Комбинаторика

2.3.4 Текстовые задачи

2.3.5 Задача о нахождении кратчайшего пути в графе

2.3.6 Лабиринты

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ А

ПРИЛОЖЕНИЕ Б



ВВЕДЕНИЕ

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

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

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

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

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

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

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

Для достижения поставленной цели необходимо решить следующие задачи:

Изучить психолого-педагогическую и методическую литературу по проблеме обучения учащихся решению задач.

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

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

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

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

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

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

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

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

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



ГЛАВА 1. ВОПРОСЫ ТЕОРИИ ГРАФОВ ПРИ ОБУЧЕНИИ В СРЕДНЕЙ ШКОЛЕ

1.1 Роль и функции задач в обучении математике

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

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

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

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

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

В книге М. И. Махмутов рассказывает об исследовании, проведённом группой учёных, математиков и психологов с целью выявления закономерностей активизации познавательной деятельности учащихся. Там отмечается, что напряжение интеллектуальных сил ученика вызывается главным образом постановкой проблемных вопросов, проблемных познавательных задач и учебных заданий исследовательского характера. Это напряжение рождается в столкновении с трудностью в понимании и осмыслении нового факта или понятия и характеризуется наличием проблемной ситуации, высокого интереса учащегося к теме, его эмоционального настроя и волевого усилия"[9] .

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

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

При обучении математике задачи имеют большое и многостороннее значение.

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

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

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

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

Воспитательная функция математических задач. Прежде всего, задача воспитывает своей фабулой, текстовым содержанием. Поэтому фабула многих математических задач существенно изменяется в различные периоды развития общества. Воспитывает не только фабула задачи, воспитывает весь процесс обучения решению математических задач. Правильно поставленное обучение решению математических задач воспитывает у учеников честность и правдивость, настойчивость в преодолении трудностей, интерес к предмету и заинтересованность в применении математических знаний. Ознакомление учащихся с элементами теории графов расширяет возможности раскрытия в процессе обучения сфер применимости математики и дает возможность показать учащимся ее практическую значимость, в частности, применения в некоторых областях деятельности [7,10,14,16].

1.2 Роль задач в развитии мышления учащихся

задача математика граф обучение

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

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

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

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

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

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

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

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

Эффективность учебной деятельности по развитию мышления во многом зависит от степени творческой активности учащихся при решении математических задач. Следовательно, необходимы математические задачи и упражнения, которые бы активизировали мыслительную деятельность школьников. Так, например, А. Ф. Эсаулов [21] подразделяет задачи на следующие виды: задачи, рассчитанные на воспроизведение (при их решении опираются на память и внимание); задачи, решение которых приводит к новой, неизвестной до этого мысли, идее; творческие задачи. Активизирует и развивает мышление учащихся решение задач двух последних видов.

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

1.3 История и основные понятия теории графов

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

Леонард Эйлер (1707-1783) - математик, механик, физик и астроном. Он автор более 850 трудов по механике, теории движения Луны и планет, по географии, по теории кораблестроения, теории музыки и другим наукам.

Термин «граф» впервые был введен спустя 200 лет (в 1936 г.) Д. Кенигом. Историю возникновения этой теории можно проследить по переписке великого ученого. Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года [17]:

рис. 3.1.1

"Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений было найдено правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке, на котором A обозначает остров, а B, C и D - части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a, b, c, d, e, f, g ":

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

Так можно ли обойти Кенигсбергские мосты, проходя только один раз через каждый из этих мостов (рис.1.3.1)? Чтобы найти ответ, продолжим письмо Эйлера к Маринони:

"Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, - таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре - A,B,C,D.

Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным - по три моста, т. е. Число мостов, ведущих к отдельным участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка. Если же из этих чисел два были бы нечетные, ибо только одно быть нечетным не может, то и тогда мог бы совершиться переход, как это предписано, но только начало обхода непременно должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно… если можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести еще большую пользу и им не следовало бы пренебрегать".

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

Схема графа, состоящая из «изолированных» вершин, называется нулевым графом (рис.1.3.2).

Графы, в которых не построены все возможные ребра, называются неполными графами (рис.1.3.3).

Графы, в которых построены все возможные ребра, называются полными графами (рис.1.3.4).

рис.1.3.2 рис.1.3.3

рис.1.3.4

Граф, каждая вершина которого соединена с ребром любой другой вершины, называется полным. Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2. Действительно, количество ребер в полном графе с n вершинами определяется как число неупорядоченных пар, составленных из всех n точек-ребер графа, т.е. как число сочетаний из n элементов по 2: граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 1.3.3 изображен неполный граф с пятью вершинами. На рисунке 1.3.4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа.

а) Степени вершин и подсчет числа ребер.

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

рис.1.3.5

На рисунке 1.3.5 изображен граф с пятью вершинами. Степень вершины А обозначим ст.А. На рисунке : ст.А = 1, ст.Б = 2, ст.В = 3, ст.Г = 2, ст.Д = 0.

Сформулируем некоторые закономерности, присущие определенным графам.

Закономерность 1. Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.

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

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

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

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

Попробуем граф, изображенный на рис.1.3.6, обвести одним росчерком, то есть, не отрывая карандаша от листа бумаги и не проходя по одной и той же части линии более одного раза. Фигура эта, такая простая на вид, оказывается, имеет интересную особенность. Если мы начнем движение из вершины В, то у нас это обязательно получится. А что будет, если мы начнем движение из верины А? Легко убедиться, что обвести линию в этом случае нам не удается: у нас всегда будет оставаться не пройденные ребра, добраться до которых уже невозможно.

рис.1.3.6 рис.1.3.7



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

Графы, начерченные на рис.1.3.8(а,б) и также можно начертить одним росчерком пера.

рис. 1.3.8а рис. 1.3.8б

Теперь попробуем вычертить одним росчерком граф, изображенный на рис.1.3.9. Вам это сделать не удалось! Почему? Вы не можете найти нужную вершину? Нет! Дело не в этом. Этот граф вообще нельзя вычертить одним росчерком пера.

рис.1.3.9

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

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

Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым графом (рис.1.3.8). Такими графы названы в честь учёного Леонарда Эйлера.

Закономерность 1. (вытекает из рассмотренной нами теоремы). Невозможно начертить граф с нечетным числом нечетных вершин.

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

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

Закономерность 4. Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».

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

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

рис.1.3.10 рис.1.3.11

На рисунке 1.3.10, очевидно, изображен несвязный граф. Если, например, на рисунке между вершинами Д и Е провести ребро, то граф станет связным (рис.1.3.11).Такое ребро в теории графов (после удаления которого граф из связного превращается в несвязный) называется мостом.

Примерами мостов на рисунке 1.3.10 могли бы служить ребра ДЕ, A3, ВЖ и др., каждое из которых соединяло бы вершины «изолированных» частей графа (рис.1.3.11).

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

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

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

в) Деревья.

Деревом называется любой связный граф, не имеющий циклов.
Договорились считать «деревом» и всякий граф, состоящий из одной (изолированной) вершины.

Циклом называется путь, в котором совпадают начало с концом. Если все вершины цикла разные, то такой цикл называется элементарным (или простым) циклом. Если же цикл включает в себя все ребра графа по одному разу, то такой цикл называется Эйлеровой линией (рис.1.3.12(а)). В графе на рис.1.3.13(б) два цикла: 1-2-3-4-1 и 5-6-7-5.

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

Висячей вершиной называется вершина, из которой выходит ребро (рис.1.3.14).

рис.1.3.12а рис.1.3.13б

Свойство 1. Для каждой пары вершин дерева существует единственный путь, их соединяющий.

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

Свойство 2. Всякое ребро в дереве является мостом.

Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева.



рис.1.3.14 (кружком обведены висячие вершины)

Теорема. Граф, в котором две любые вершины соединены ровно одним простым путём, является деревом.

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

Дерево - это граф, в котором две любые вершины соединены ровно одним простым путём.

Теорема. В дереве число вершин на одну больше числа ребер.

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

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

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

Рассмотрим граф с пятью вершинами, попарно соединенными друг с другом (рис.1.3.15). Здесь ребра графа пересекаются. Невозможно его изобразить так, чтобы пересечений не было, как невозможно выполнить намерения трех человек, описанных Льюсом Кэрроллом в одной из задач.

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

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

рис.1.3.15

Теорема Понтрягина - Куратовского: Граф является плоским тогда и только тогда, когда он не содержит (в топологическом смысле) графа с шестью вершинами типа «домики-колодцы» и полного графа с пятью вершинами (рис.1.3.15) [22]. (В основном используется старинных задач о домах и колодцах, суть которой сводится к выяснению вопроса -- является ли рассматриваемый граф плоским или нет (рис.1.3.16).

рис.1.3.16

д) Ориентированные графы.

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

Граф, на рёбрах которого расставлены стрелки, называется ориентированным.

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

рис.1.3.17

Так, на рисунке 1.3.17 изображен ориентированный граф АБВГД. Степени входа и выхода некоторых его вершин такие:

ст. вх. А =2, ст. вых. А=1

ст. вх. В=2, ст. вых. В=0

ст. вх. Д=1, ст. вых. Д=3

Путем, в ориентированном графе от вершины А1 к вершине An называется последовательность ориентированных ребер , , … в которой конец каждого предыдущего ребра совпадает с началом следующего и каждое ребро встречается в этой последовательности только один раз. На ниже приведенном рисунке показаны примеры путей в ориентированном графе. Причем, первые два пути-- простые -- ни одна из вершин не содержится в нем более одного раза. Третий путь не является простым, т. к. через вершину Г путь «проходил» дважды (рис.1.3.18).

рис.1.3.18

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

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

рис.1.3.19

Так, на рисунке 1.3.19 пути от А к Д могут быть различны и иметь различную длину. Первый путь имеет длину 2, второй - 3, а третий -- 4. Длина «кратчайшего пути» между двумя вершинами называется расстоянием между ними. Так расстояние между вершинами А и Д на графе рисунка 1.3.19 равно 2; записывают так: S(АД)=2.

рис.1.3.20

Если в ориентированном графе нельзя «пройти» от одной вершины до другой, то расстояние между ними называют бесконечным (обозначают значком бесконечности). Так, расстояние между вершинами Б и Д графа, представленного на рисунке 1.3.20 бесконечно:

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

Возникает вопрос: так ли нужны были графы в разобранных задачах? Разве нельзя прийти к решению чисто логическим путем? Да, можно. Но графы придали условиям наглядность, упростили решение и выявили сходство задач, превратив две задачи в одну, а это уже не так уж мало. А теперь представьте себе задачи, графы которых имеют 100 или более вершин. А ведь именно такие задачи приходиться решать современным инженерам и экономистам. Тут без графов не обойтись.

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

Классификация геометрических объектов

1.4 Графы как средство обучения учащихся поиску решения задач

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

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

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

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

Рассмотрим некоторые средства наглядности для обучения поиску решения задач по теме “Элементы теории графов” [11,12,13].

Задача 1. В деревне 9 домов. Известно, что у Петра соседи Иван и Антон, Максим сосед Ивану и Сергею, Виктор - Диме и Никите, Евгений - сосед Никиты, а больше соседей в этой деревне нет (соседними считаются дворы, у которых есть общий участок забора). Может ли Пётр огородами пробраться к Никите за яблоками?

Решение. Нарисуем схему: точками обозначим дома и соединим непересекающимися между собой линиями только те из них, которые являются соседними (рис. 1.4.1). Теперь видно, что пробраться огородами из дома Петра к дому Никиты нельзя.

рис.1.4.1

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

рис.1.4.2a рис.1.4.2б

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



рис.1.4.2в

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

Задача 3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединён с пятью другими?

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

Замечание. Каждое ребро соединяет ровно две вершины.

Задача 4. На концерте каждую песню исполняли двое артистов, и никакая пара не выступала вместе более одного раза. Всего было 12 артистов, каждый выступил по 5 раз. Сколько было песен?

Решение. Рассмотрим граф, вершинами которого являются выступавшие артисты. Соединим пару артистов ребром, если они вместе пели. Получим граф с 12 вершинами степени 5, каждой песне соответствует ребро. Аналогично предыдущему примеру, в графе рёбер, то есть было 30 песен.

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

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

рис. 1.4.3а рис.1.4.3б

Решение. а) Можно. Например, последовательность вершин может быть такой: 1-2-3-1-4-2-5-3-4. б) Поскольку из каждой вершины (кроме первой и последней) мы выходим столько же раз, сколько входим, степени этих вершин должны быть чётными. В графе на рис. 1.4.3б все четыре вершины имеют степень 3, поэтому его нельзя нарисовать, не отрывая карандаша от бумаги.

Возможно, вам знакома аналогичная задача про открытый конверт (или домик). (рис.1.4.4)



рис.1.4.4

Задача 6. Схема мостов Кёнигсберга изображена на рис. 1.4.5. Можно ли совершить прогулку, пройдя по каждому мосту ровно один раз?

рис.1.4.5

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

Задачa 7. В углах шахматной доски 33 стоят 4 коня: 2 белых (в соседних углах) и два чёрных (рис.1.4.6а). Можно ли за несколько ходов (по шахматным правилам) поставить коней так, чтобы во всех соседних углах стояли кони разного цвета?



рис.1.4.6а рис.1.4.6б рис.1.4.6в

Решение. Отметим центры клеток доски и соединим отрезками пары отмеченных точек, если из одной в другую можно перейти шагом коня (конь ходит буквой Г). Мы получили граф (рис. 1.4.6б). В нём есть изолированная вершина (замечание 1), это вершина 5. Попробуйте обойти все остальные вершины графа и вернуться в исходную вершину. У вас должно получиться, ведь рёбра и все вершины, кроме вершины 5, образуют эйлеров граф, содержащий цикл. Перемещение коней по доске соответствует движению по рёбрам этого цикла. Для графа на рис.1.4.6(б) изображен изоморфный граф (рис.1.4.6 в и замечание 2). Ясно, что при движении по циклу нельзя изменить порядок следования коней.

Замечания.

1. Вершины, из которых не исходит ни одного ребра, называются изолированными.

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

Задача 8. Четыре ученицы: Мария, Нина, Оля и Юля участвовали в лыжных соревнованиях и заняли 4 первых места. На вопрос, кто какое место занял, они дали три разных ответа:

Первый: Ольга заняла первое место, Ника - второе.

Второй: Ольга заняла второе место, Юля - третье.

Третий: Мария заняла второе место, Юля - четвертое.

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

Решение.

	1	2	3	4		1	2	3	4
Мария	-	+	-		Мария	-	+	-	-
Нина	-	+	-	-	Нина	-	-	-	+
Оля	-	-	-		Оля	+	-	-	-
Юля	-	-	+	-	Юля	-	-	+	-
Предположим, что Оля заняла не первое место и получим, что Мария и Нина заняли второе место, что невозможно по условию задачи.	Пусть Оля заняла первое место, следовательно, Нина не заняла второе и т.д. Получаем верное решение.

Задача 9. На рисунке 1.4.7 изображены расстояния между пунктами A, B, C, D, E и F. Двигаться по дорогам можно только в направлениях, указанных стрелочками. Водитель едет из пункта А в пункт Е. Как он должен ехать, чтобы добраться по самому короткому пути?

D C

E A

F B

рис.1.4.7

Решение. Рассмотрим последовательно возможные пути поездки и сравним их длину. ABFE = 14, ABFCDE = 15, ABFDE = 13, ACDE = 16.Выберем наименьшее расстояние. Оно равно 13, значит нужно ехать по маршруту ABFDE.

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

Решение. Листки бумаги обозначим на рисунке кружками. Кружки, соответствующие листам, которые разрезаются, закрасим целиком; остальные кружки оставим не закрашенными. На рисунке 1.4.9 видно, что при разрезании одного листа на 3 части число листков увеличивается на два. Если же разрезано k листков, то образовалось 1+ 2k листов.

рис. 1.4.9

Рассмотрев основные положения теории графов, покажем далее, как можно реализовать эту теории при решении задач на факультативных занятиях в школе [12].



ГЛАВА 2. МЕТОДИКА ОБУЧЕНИЯ УЧАЩИХСЯ РЕШЕНИЮ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ ГРАФОВ НА ФАКУЛЬТАТИВНЫХ ЗАНЯТИЯХ В ШКОЛЕ

2.1 Роль факультативных занятий как формы обучения математике

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

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

Такие занятия должны были, прежде всего, учитывать «местные условия», а именно: реальные и потенциальные запросы и интересы конкретного количества учащихся данного класса, реальные возможности конкретного учителя вызвать и развить интерес учащихся к важным аспектам данного предмета, не охваченным обязательной программой. Так возникла идея факультативных занятий в школе. Из толкового словаря Д.И.Ушакова: факультативный - необязательный, предоставленный собственному выбору [19]. Учителя стали создавать для учащихся факультативные предметные семинары, они получили название, заимствованное из общественной жизни: кружки. Школьные кружки были созданы также при университетах и других вузах. Опыт многих педагогов показал, что именно в предметном кружке возникает особенно благоприятная атмосфера для воспитания у школьников увлеченности предметом, энтузиазма, инициативы.

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

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

Значение факультативных занятий состоит в том, что они позволяют:

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

- удовлетворять интересы учащихся;

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

- развивать творческие способности учащихся, их самостоятельность;

- знакомить учащихся с современными достижениями науки и техники;

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

- способствовать профессиональной ориентации учащихся.

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

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

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

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

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