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

 

РЕФЕРАТ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

.3.1 Вводное занятие Сфера применения теории графов

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

.3.3 Комбинаторика

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

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

.3.6 Лабиринты

ЗАКЛЮЧЕНИЕ

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

ПРИЛОЖЕНИЕ А

ПРИЛОЖЕНИЕ Б

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

1. Изучить психолого-педагогическую и методическую литературу по проблеме обучения учащихся решению задач.
2. Изучить основные положения теории графов; раскрыть возможности графов как средств обучения учащихся решению задач.
3. Отразить роль факультативных занятий как одной из форм внеклассной работы по математике.
4. Разработать содержание факультативных занятий по теме Элементы теории графов и методики их проведения.
5. Составить и подобрать задачи, решаемые с использованием теории графов.

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

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

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

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

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

ГЛАВА 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). Ясно, что при движении по циклу нельзя изменить порядок следования коней.

Замечания.

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

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

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

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

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

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

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

Решение.

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

Задача 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]. Учителя стали создавать для учащихся факультативные предметные семинары, они получили название, заимствованное из общественной жизни: кружки. Школьные кружки были созданы также при университетах и других вузах. Опыт многих педагогов показал, что именно в предметном кружке возникает особенно благоприятная атмосфера для воспитания у школьников увлеченности предметом, энтузиазма, инициативы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим программу факультатива по теории графов, предложенную учителями математики школ РБ и представленную на сайте Министерства образования [24]. Школьники для начала должны привыкнуть к языку графов и затем научиться работать с графами для развития мышления необходимо решать задачи на смекалку, которые часто не требуют глубоких знаний.

Программа рассчитана на 34 часа (1 час в неделю).

Содержание программы факультатива:

класс (12 ч)

Занимательные и провоцирующие задачи. (2ч)

Соответствия и отношения. Их описание с помощью схем (графов).(2ч)

Определение графа и подграфа. Вершины, ребра, смежность. Степени вершин. Примеры применения графов.(3ч)

Полные графы. Число ребер в полном графе.(2ч)

Двудольные графы. Примеры двудольных графов. Полные двудольные графы. Теорема о сумме степеней вершин. Определение двудольности графа с помощью поиска в ширину.(3ч)

класс (13ч)

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

Следствие из леммы. Использование приема от противного при доказательстве следствия о числе вершин нечетной степени в графе.(2ч)

Связные графы. Определение компоненты графа и связного графа.(2ч)

Маршруты в графах. Определение маршрута, цепи, цикла, простой цепи, простого цикла. (2ч)

Эйлеровы графы. Необходимые и достаточные условия эйлеровости (теорема Эйлера). Алгоритм построение эйлерова цикла и эйлеровой цепи. Разбиение графа на минимальное число цепей. (3ч)

Понятие о гамильтоновых графах.(2ч)

класc (9ч)

Деревья. Свойства деревьев. Соотношение между числом вершин и ребер.(2ч)

Ориентированные графы. Свойства орграфов. Степени вершин. Аналог леммы о рукопожатиях. Обходы в орграфах.(3ч)

Корневое дерево. Перебор всех вариантов с помощью корневого дерева.(2ч)

Поиск с возвращением.(2ч)

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

Цели:

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

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

подготовка школьников к основным понятиям математики и ее методов в старших классах.

Задачи:

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

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

воспитательные: поддержание интереса у школьников к математике.

Ожидаемые результаты:

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

о возможности описания с помощью графов различных ситуаций;

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

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

с основными понятиями теории графов;

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

со способами решения графовых задач.

Изучение данного факультативного занятия предполагает:

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

ускорение математического и логического развитие школьников;

развитие познавательных способностей учащихся;

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

Рассмотрим содержание занятий и методику решения задач

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

.3.1 Вводное занятие Сфера применения теории графов

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

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

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

Давайте рассмотрим небольшой фрагмент- разработку одного из занятий по теме «Сфера применения теории графов».

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

Семинар начинается с поэтических строк.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 1. Можно ли нарисовать одним росчерком с помощью графа изображение птицы? (рис.2.3.2.1а)

рис.2.3.2.1а

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

рис. 2.3.2.1б

Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4x4 убрать угловые клетки (рис.2.3.2.2а).

рис.2.3.2.2а

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

Решение. Занумеруем последовательно клетки доски (рис.2.3.2.2б):

рис.2.3.2.2б

А теперь с помощью рисунка покажем, что такой обход таблицы, как указано в условии, возможен (рис.2.3.2.2в):

рис.2.3.2.2в

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

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

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

Учащимся сообщается, что раздел математики, рассматривающий вопросы (задачи), связанные с подсчетом числа всевозможных комбинаций из элементов данного конечного множества при сделанных исходных предположениях. Большинство задач решается по двум правилам: сложения и произведения [15].

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

Решение. Сделаем рисунок. Точки будут изображать мальчиков, а отрезки рукопожатия (рис.2.3.3.1):

) 2)

) 4)

рис.2.3.3.1

Из рисунка видно, что на вокзале встретились 5 мальчиков.

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

Задача 2. У Пети есть 2 автомобиля, 4 оловянных солдатика и 2 мяча. Он хочет подарить набор из трех разных игрушек своему другу на день рождения. Оказалось, выбрать не так уж просто, слишком много получается вариантов, тем более что все мячи, солдатики и машины такие непохожие. Сколько наборов мог составить Петя?

Решение. Обозначим автомобили, солдатиков и мячи буквами с индексами: А1, А2, С1, С2, С3, С4, М1, М2. Построим граф - дерево. Точка Н - начало, от которой выставляем один из вариантов А1 и А2. От точки А1 можно выбрать уже 4 варианта солдатиков и так далее.

рис. 2.3.3.2

Двигаясь от начала по отрезкам вниз получим 16 вариантов (рис. 2.3.3.2)

Ответ: 16 наборов.

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

Задача 1. Петя принес на базар корзину яблок. I покупателю он продал половину всех яблок и еще 1 яблоко, II - половину остатка и еще 1 яблоко, III - половину нового остатка и еще 1 яблоко и т.д. Последнему - шестому покупателю она также продал половину оставшихся яблок и еще 1 яблоко, причем оказалось, что он продал все свои яблоки. Сколько яблок принес для продажи Петя?

Решение. Составим граф (рис.2.3.4.1а)

рис.2.3.4.1а

Решая, действия делаем обратно (рис.2.3.4.1б)

рис.2.3.4.1б

Ответ: 126 яблок.

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

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

Задача 1. Дана карта дорог между городами, где указана длина каждой дороги (данные не совпадают с настоящими). Найти: а) все кратчайшие пути из Санкт-Петербурга до Омска; б) все кратчайшие пути из Санкт-Петербурга до Магнитогорска (рис.2.3.5.1).

рис.2.3.5.1

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

.3.6 Лабиринты

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

рис.2.3.6.1

Построим соответствующий ему граф (рис.2.3.6.2). Коридоры лабиринта - это ребра графа, а перекрестки, тупики, входы и выходы - это вершины.

рис.2.3.6.2

Теперь хорошо видно, что в центр лабиринта можно попасть, следуя по следующим вершинам: 1 - 4 - 7 - 10 - 9 - 11 - 12 - 13. И, соответственно, выйти из центра лабиринта по маршруту: 13 - 12 - 11 - 9 - 10 - 7 - 4 - 1.

Ответ: 13 - 12 - 11 - 9 - 10 - 7 - 4 - 1.

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

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

Нарисовав соответствующий лабиринту граф, используют способ обхода всех ребер для нахождения выхода [4, 5, 11,12,13,15].

Задачи для факультативных занятий в рамках действующей учебной программы по математике [23] можно брать в действующих учебниках математики [20].

ЗАКЛЮЧЕНИЕ

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

При выполнении дипломной работы были решены следующие задачи:

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

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

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

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

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

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

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

1.Арсеньев, A.M. Факультативные занятия в школе / А.М. Арсеньев -Советская педагогика , 1968.

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

.Белов, В.В. Теория графов / В.В. Белов, Е.М. Воробьев, В.Е. Шаталов. - М. : Высшая школа, 1976. - 2

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

.Берж К. Теория графов и ее применения / Пер. с франц. Зыкова А. А., под ред. Вайнштейна И. А. - М.: Изд-во иностр. литер., 1992.

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

.Колягин, Ю.М. Задачи в обучении математике / Ю.М. Колягин. - М.: Просвещение, 1977.

.Коннова, Л. П. Знакомьтесь, графы / Л. П. Коннова - Самара: Изд. института повышения квалификации работников образования, 2001.

.Махмутов, М.И. Проблемное обучение / М.И. Махмутов. - М. : Педагогика, 1975.

.Медведева, О.С. Психолго- педагогические основы обучения математике. Теория, методика, практика/ О.С. Медведева - М. : БИНОМ. Лаборатория знаний, 2011.

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

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

.Мельников, О. И., Использование графовых задач при самостоятельной работе для развития воображения школьников // Народная асвета. - 2002. - №10.

.Рогановский, Н.М. , Методика преподавания математики в средней школе. Часть 1: Общие основы методики преподавания математики (общая методика) / Н.М. Рогановский, Е.Н. Рогановская Е.Н. - Могилев: МГУ им. А.Л.Кулешова, 2010.

.Нагибин Ф.Ф. Применение графов для решения логических задач.// Математика в школе. - 1964. - № 3.

.Общая методика преподавания математики в средней школе / Колягин Ю.М. [и др.] - М. : Просвещение, 1975, 1977.

.Олехник, С. Н., Старинные занимательные задачи / С.Н. Олехник Ю.В., Нестеренко М.К. Потапов - 2 часть - М. : Наука , 1988.

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

19.Толковый словарь русского языка: В 4 т. /Г.О. Винокур [и др.] <#"justify">учебное пособие «Математика» / «Матэматыка» для 5 класса учреждений общего среднего образования с русским (белорусским) языком обучения .В 2 ч / Е.П. Кузнецова [ и др.]: Под. ред.-Л.Б. Шнейпермана - Минск: Нац, ин-т образования, 2009.

учебное пособие «Математика» / «Матэматыка» для 6 класса общеобразовательных учреждений с русским (белорусским) языком обучения / Е.П. Кузнецова [ и др.]: Под. ред.-Л.Б. Шнейпермана - Минск: Нац, ин-т образования, 2010.

учебное пособие «Алгебра» / «Алгебра» для 7 класса общеобразовательных учреждений с русским (белорусским) языком обучения / Е.П. Кузнецова [ и др.]: Под. ред.-Л.Б. Шнейпермана - Минск : Народная асвета, 2009.

учебное пособие «Математика» / «Матэматыка» для 5 класса учреждений общего среднего образования с русским (белорусским) языком обучения. В 2 частях / Л.А Латотин , Б.Д. Чеботареский - Минск: Адукацыя і выхаванне, 2013.

учебное пособие «Математика» / «Матэматыка» для 6 класса общеобразовательных учреждений с русским (белорусским) языком обучения / Л.А.Латотин, Б.Д.Чеботаревский - Минск: Народная асвета, 2010.

учебное пособие «Математика» / «Матэматыка» для 7 класса общеобразовательных учреждений с русским (белорусским) языком обучения авторов / Л.А.Латотин, Б.Д.Чеботаревcкий- Минск: Народная асвета, 2009.

.Эсаулов, А. Ф. Психология решения задач / А. Ф. Эсаулов - М : 1972.

.Яблонский, С.В. Введение в дискретную математику / С.В. Яблонский. - М.,1986.

23.Образовательный Интернет-портал Республики Беларусь [Электронный ресурс] / Учебная программа для учреждении общего среднего образования с русским языком обучения Математика 5-11 классы / Национальный институт образования - Минск, 2012.- Режим доступа : <#"justify">ПРИЛОЖЕНИЕ А

Тестовые задания

. Укажите область, в которой не применяются графы:

а) экономика;

б) физика;

в) архитектура;

г) нет вариантов.

. Укажите полный граф.

.Если полный граф имеет n вершин, то количество его ребер равно:

а) (n-1)/2 б) n(n-2)/2 в) n(n-1)/2

. Какой граф является «эйлеровым графом»

. Начерти линию одним росчерком (укажи направление).

6. Придумай свой способ записи букв Ф и К, при котором их можно начертить одним росчерком.

. Решению, какой из следующих задач, соответствует граф

а) В пяти корзинах (А, Б, В, Г, Д) лежат яблоки пяти разных сортов. Яблоки первого сорта лежат в корзинах Г и Д; яблоки второго сорта - в корзинах А, Б и Г; в корзинах А, Б и В имеются яблоки пятого сорта, в корзине В имеются к тому же яблоки четвертого сорта, а в корзине Д - третьего. Требуется дать каждой корзине номер, но так, чтобы в корзине №1 были яблоки первого сорта (хотя бы одно), в корзине №2 - второго и т.д.

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

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

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

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

. Реши задачу, использовав графы.

Аркадий, Борис, Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями, каждый пожал руку каждому по одному разу. Сколько всего рукопожатий было сделано?

а) 5 б)10 в)9

ПРИЛОЖЕНИЕ Б

Задачи для самостоятельной работы

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

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

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

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

. Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?

Решение. Подсчитаем число городов. Число дорог равно числу городов х, умноженному на 3 (число выходящих из каждого города дорог) и разделенному на 2. Тогда 100 = Зх/2 => Зх=200, чего не может быть при натуральном х. Значит 100 дорог в таком государстве быть не может.

. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 - по 4 друга, а 10 - по 5 друзей ?

Ответ. Нет (теорема о четности числа нечетных вершин).

. У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей ?

Ответ. Нет, не может.

.В Цветочном городе каждый коротышка знаком с 6 малышками, а каждая малышка - с 6 коротышками. Докажите, что в этом городе число малышек равно числу коротышек.

Решение. Если знакомство вида «коротышка - малышка» - это ребро графа, то n - число коротышек, m - число малышек. Тогда всех знакомств (ребер) коротышек 6n, а малышек 6m. Значит 6n= 6m, тогда в этом городе число малышек равно числу коротышек.

.Дима, приехав из Мехеево, рассказал, что там есть несколько озёр, соединенных между собой реками. Из каждого озера вытекают 3 реки, и в каждое озеро впадают 4 реки. Докажите, что он ошибается.

Решение. Если вытекают 3 реки, а впадают 4 - это невозможно, т. к. количество «втекающих», должно быть равно количеству «вытекающих». Дима не прав.

.Волейбольная сетка - прямоугольник 50x600 клеток. Какое наибольшее число веревочек можно перерезать, чтобы сетка не распалась?

Решение. Будем рассматривать волейбольную сетку как граф, вершинами которого являются узлы сетки, а ребрами - веревочки. В этом графе нужно удалить как можно больше ребер так, чтобы он остался связным. Заметим, что пока в графе есть цикл, возможно удаление любого ребра этого цикла. Связный граф, не имеющий циклов, является деревом. Поэтому, только получив дерево, мы не сможем убрать ни одного ребра. Изначально в графе было 601·50+600·51=60650 рёбер и 51·601=30651 вершин, т. е. дерево будет иметь 30650 ребер. Таким образом, разрезать можно 60650-30650=30000 веревочек.

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

Решение. Допустим, что это возможно, тогда пусть на шоссе n городов, значит дорог всего (2n-1). Поскольку дороги одной компании соединяют все города в связное множество, то этих дорог не меньше n. Тогда дорог двух компаний не меньше 2n, что нам противоречит, а значит не смогут выполнить условия.

.В городе Н от каждой площади отходит ровно 5 улиц, соединяющих площади. Докажите, что число площадей чётно, а число улиц кратно 5.

Решение. По теореме, что число нечётных вершин любого графа чётно, следует, что число площадей (вершин графа) 2n, а число улиц (рёбер графа) будет (2n·5):2, а значит, число площадей чётно, а число улиц кратно 5.

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

Больше работ по теме: