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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

Решение.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Введение

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача .

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 1.

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

Решение.

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

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



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

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

Решение.

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

Задача 3.



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

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

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



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

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

Задача 4.

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

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

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

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

Задача 5.

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

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

Задача 6.

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Анкета.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Урок.

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

Семинар

Лекция.

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

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

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

Ответ Вопрос	1	2	3	4
1	11%	22%	57%	10%
2	3%	35%	15%	39%
3	13%	7%	29%	48%
4	23%	16%	57%	4%
5	64%	7%	21%	8%
6	89%	0	3%	8%

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

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

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

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

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

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

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

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

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

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

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

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

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



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

Задание	Процент учащихся, справившихся с заданием
1	88%
2	81%
3	78%
4	64%

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

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



Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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