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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

5 класс (12 ч)

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

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

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

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

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

6 класс (13ч)

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

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

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

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

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

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

7 класc (9ч)

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

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

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

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

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

Цели:

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

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

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

Задачи:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.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):

1) 2)

3) 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.

2.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) Проанализирована психолого-педагогическая и методическая литература по проблеме обучения учащихся решению задач и установлено, что задачи являются основным средством обучения математике. При решении задач возможно использование различных видов наглядности, в частности, графов.

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19. Толковый словарь русского языка: В 4 т. /Г.О. Винокур [и др.] ; под ред. Д.Н. Ушакова.-- Минск : Государственный институт «Советская энциклопедия»; ОГИЗ (т. 1),1935--1940.

20. Учебники по математики для средней школы :

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

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

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

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

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

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

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

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

23. Образовательный Интернет-портал Республики Беларусь [Электронный ресурс] / Учебная программа для учреждении общего среднего образования с русским языком обучения “ Математика 5-11 классы” / Национальный институт образования - Минск, 2012.- Режим доступа : http://www.adu.by. - Дата доступа - 2014.

24. Образовательный Интернет-портал Республики Беларусь [Электронный ресурс] / Учебная программа факультативных занятий “Элементы теории графов” / Национальный институт образования - Минск, 2007.- Режим доступа : http://www.adu.by. - Дата доступа - 2014.

25. Образовательный Интернет-портал Республики Беларусь [Электронный ресурс] / Инструктивно-методическое письмо Министерства образования Республики Беларусь «О преподавании учебного предмета «Математика» в 2013/2014 учебном году» / Национальный институт образования - Минск, 2013.- Режим доступа : http://www.adu.by. - Дата доступа - 2014.



ПРИЛОЖЕНИЕ А

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

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

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

б) физика;

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

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

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

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

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

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

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



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

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

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

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

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

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



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

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

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

а) 5 б)10 в)9



ПРИЛОЖЕНИЕ Б

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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