Методика преподавания элементов теории графов на факультативных занятиях по математике

Остапенко Л.Н.

Методика преподавания элементов теории графов на факультативных занятиях по математике

44.03.01 Педагогическое образование, профиль Математика

Народное образование. Педагогика

Дипломы

Вуз: Белгородский государственный университет - национальный исследовательский университет (НИУ «БелГУ»)

ID: 5c1a66b27966e104f6f8585c

UUID: 7f5ad630-e5d2-0136-02a4-525400005860

Язык: Русский

Опубликовано: больше 5 лет назад

Просмотры: 127

Остапенко Л.Н.

Источник: Федеральное государственное автономное образовательное учреждение высшего образования «Белгородский государственный национальный исследовательский университет»

Комментировать 0

Рецензировать 0

Скачать - 835,6 КБ

Поделиться работой

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «БЕЛГОРОДСКИЙ ГОСУДАРСТВЕННЫЙНАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ» ( Н И У « Б е л Г У » ) ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ ФАКУЛЬТЕТ МАТЕМАТИКИ И ЕСТЕСТВЕННОНАУЧНОГО ОБРАЗОВАНИЯ КАФЕДРА МАТЕМАТИКИ МЕТОДИКА ПРЕПОДАВАНИЯ ЭЛЕМЕНТОВ ТЕОРИИ ГРАФОВ НА ФАКУЛЬТАТИВНЫХ ЗАНЯТИЯХ ПО МАТЕМАТИКЕ Выпускная квалификационная работа обучающегося по направлению подготовки 44.03.01 Педагогическое образование, профиль Математика заочной формы обучения, группы 02041351 Остапенко Любови Николаевны Научный руководитель: к. ф.-м. н., доцент Мотькина Н.Н. БЕЛГОРОД 2018

ОГЛАВЛЕНИЕ ВВЕДЕНИЕ……………………………………………………………….... 3 1 ВОПРОСЫ ТЕОРИИ ГРАФОВ ПРИ ОБУЧЕНИИ В СРЕДНЕЙ ШКОЛЕ …………………………………………………………………….. 6 1.1 История возникновения теории графов ……………………………… 6 1.2 Основные понятия теории графов……………………………………. 10 1.3 Эйлеровы и гамильтоновы графы ………………………………… 13 1.4 Лабиринты …………………………………………………………….. 16 1.5 Графы с цветными рёбрами и их свойства………………………… 20 2 МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ФАКУЛЬТАТИВНОГО КУРСА «ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ»……………………………………… 22 2.1 Роль факультативных занятий как формы обучения математике...... 22 2.2 Программа и содержание факультативного курса “Элементы теории графов» для обучающихся 9 класса. ……………………………. 27 ЗАКЛЮЧЕНИЕ…………………………………………………………….. 37 СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ………………………. 38 ПРИЛОЖЕНИЕ……………………………………………………………. 40 2

ВВЕДЕНИЕ В настоящее время дискретная математика приобретает все большее значение. Это связано с развитием теории вероятностей, математической логики и информационных технологий. Одним из разделов дискретной математики является теория графов. Впервые основы теории графов появились в работе Л. Эйлера в 1736 году, где он описывал решения головоломок и математических развлекательных задач. Широкое развитие теория графов получила с 50-х годов ХХ века в связи со становлением кибернетики и развитием вычислительной техники [26]. Родившись при решении головоломок и занимательных игр, теория графов стала в настоящее время простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. Графы существуют везде, не только в науке. Любой из нас, так или иначе, невольно сталкивается с ними в повседневной жизни. Примерами этого служат карты дорог, схемы метро, карты звездного неба, молекулы химических соединений и даже взаимоотношения между людьми. В основе большинства компьютерных программ также лежат графы, которые делают возможными современную коммуникацию и технологические процессы. Теория графов применяется в экономике и статистике, химии и биологии. В значительной степени через теорию графов происходит проникновение математических методов в науку и технику. Теория графов быстро развивается, находит всё новые приложения и ждёт молодых исследователей. Теория графов в школьной программе не изучается, так как образовательная программа и так очень насыщена, но задачи на графы часто встречаются на математических олимпиадах школьников.Поэтому обучающихся необходимо познакомить с теорией графов на факультативных занятиях, научить их оперировать терминами теории графов, использовать и применять ее при решении задач. Ведь графы способствуют развитию 3

математического мышления. Применение графов, не вызывая особых затруднений у школьников, может способствовать наглядности обучения, при которой реальные объекты заменяются их знаковым изображением. Кроме того, теория графов позволяет ученикам понять красоту математики, а это, в свою очередь, несет воспитательный и мотивационный характер. Все вышесказанное определяет актуальность исследования. Цель представить исследования: теоретически факультативной курс обосновать «Элементы и теории содержательно графов» для обучающихся 9 классов общеобразовательной школы. Объект и предмет исследования: Объектом исследования данной выпускной квалификационной работы является процесс обучения элементам теории графов на факультативных занятиях в общеобразовательной школе. Предметом исследования является методика преподавания основ теории графов в общеобразовательной школе. Гипотеза: проведение факультативных занятий по теории графов способствует развитию у обучающихся математического мышления. В ходе исследования нами были поставлены следующие задачи: 1. Изучить и проанализировать учебно – методическую и психолого – педагогическую литературу по проблеме исследования. 2.Изучить основные понятия и утверждения теории графов. 3. Раскрыть возможность использования графов как средства обучения решению задач. 4. Изучить роль факультативных занятий как формы обучения математике. 5. Разработать программу факультативного курса «Элементы теории графов» для обучающихся 9 классов общеобразовательной школы. 6. Разработать содержание факультативных занятий по теме “Элементы теории графов” для обучающихся 9 классов и представить методику их проведения. 4

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

1 ВОПРОСЫ ТЕОРИИ ГРАФОВ ПРИ ОБУЧЕНИИВ СРЕДНЕЙ ШКОЛЕ 1.1 История возникновения теории графов Теория графов – раздел дискретной математики, изучающий свойства графов. Довольно долго учение о графах рассматривали, как «несерьёзную тему», «прикладное» значение которой целиком связано с головоломками, играми и развлечениями. Очень долго теория графов находилась в стороне от главных направлений исследований ученых, была в царстве математики на положении Золушки, чьи дарования раскрылись в полной мере лишь тогда, когда она привлекла внимание весьма сложного раздела современной математики, интересующего небольшой круг специалистов – топологии [16]. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кёнига в 30 – е годы XX столетия. В последнее время графы и связанные с ними методы исследований органически пронизывают на разных уровнях едва ли не всю современную математику [4]. Отцом теории графов является Эйлер. Он в 1736 году решил известную в то время задачу, которая называлась проблемой кёнигсбергских мостов. В городе Кёнигсберге было два острова. Эти острова соединены семью мостами с берегами реки Преголя и друг с другом. В задаче нужно было найти маршрут прохождения всех четырёх частей суши, который начинался бы с любой из них, кончался бы на этой же части и ровно один раз проходил по каждому мосту. Эйлер доказал невозможность такого маршрута, чем внёс исключительный вклад в решение этой задачи. Чтобы доказать, что в этой задаче нет решения, Эйлер обозначил каждую часть суши точкой (вершиной), а каждый мост – линией (ребром), 6

соединяющей соответствующие точки. Получился «граф» на котором точки отмечены теми же буквами что и четыре части суши. Утверждение Эйлера о не существовании «положительного» решения у этой задачи равносильно утверждению о невозможности обойти специальным образом граф. Отправляясь от этого частного случая, Эйлер обобщил постановку задачи и нашёл критерий существования обхода (специального маршрута) у данного графа, а именно граф должен быть связным и каждая его вершина должна быть инцидентна чётному числу рёбер [8]. В 1847 году Кирхгофтом для решения совместной системы линейных алгебраических уравнений, была разработана теория деревьев, которая позволяла найти значение силы тока в каждом проводнике (дуге) и в каждом контуре рассматриваемой электрической цепи. Хотя он был физиком, но подходил к решению задач как математик. Абстрагируясь от электрических схем и цепей, которые содержат сопротивления, конденсаторы, индуктивности и т.д., он рассматривал соответствующие комбинаторные структуры, содержащие только вершины и связи (рёбра или дуги), причём для связей не нужно указывать, каким типам электрических элементов они соответствуют. Таким образом, в действительности Кирхгоф заменил каждую электрическую цепь соответствующим ей графом и показал, что для решения системы уравнений необязательно рассматривать в отдельности каждый цикл графа электрической цепи. Вместо этого он предложил простую, но эффективную методику, в соответствии с которой достаточно ограничиться только независимыми простыми циклами графа, определяемыми любым из его «основных деревьев»[5]. Кэли, занимаясь чисто практическими задачами органической химии, в 1857 году открыл важный класс графов, называемых деревьями. Он стремился перечислить изомеры предельных углеводородов с данным числом атомов углерода. Конечно, Кэли, прежде всего, сформулировал задачу абстрактно: найти число всех деревьев с p вершинами, каждое из которых имеет вершины со степенями 1 и 4. Однако сразу задача им не была 7

решена, и он стал изменять её формулировку таким образом, чтобы можно было решить новую задачу о перечислении: а) корневых деревьев; б) всех деревьев; в) деревьев, у которых степени вершин не превышают 4, и, наконец, г) деревьев, у которых степени вершин равны 1 и 4. В 1869 году Жордан, даже не подозревая о значении своего открытия в области химии, ввёл и изучал деревья, как чисто математические объекты. В 1859 году сэр Вильям Гамильтон придумал игру «Вокруг Света». В игре используется додекаэдр, каждой из 20 вершин которого приписано название известного города. Играющий должен обойти «вокруг света», найдя такой замкнутый путь, идущий по ребрам многогранника, который проходил бы через каждую вершину ровно один раз. Гамильтон продал свою идею одному мастеру игрушек за 25 гиней, поступив при этом жестоко, так как данная игра не принесет абсолютно никакой финансовой удачи. Задача эта на языке теории графов формулируется так: найти основной цикл в графе додекаэдра. Существование основного цикла очевидно. В 1878 году английский математик А.Кэли опубликовал известную нерешённую задачу о четырёх красках. Любой математик может объяснить эту замечательную задачу любому из нас всего лишь в течение пяти минут, но понимать проблему будут все, а вот решить её никто не сможет. Ровно через год В.Кемпе представил первое доказательство гипотезы, а П.Хивуд через одиннадцать лет в этом доказательстве обнаружил ошибку, и одновременно извлёк из него важное, доказав, что для раскраски любой карты, даже самой сложной конфигурации, достаточно пяти красок. После первого ошибочного доказательства последовало много других. Проблемой четырёх красок занимались многие известные математики прошлого, но никто из них не раскрыл секрета гипотезы. Было много неудачных попыток доказать гипотезу для любого числа стран, затем математики решили доказать её, начиная с малых натуральных чисел. Так П. Франклин в 1913 году доказал гипотезу для карты в которой не более чем 25 стран, со временем он увеличил это число до 38. С увеличением числа стран растёт 8

и число различных вариантов их взаимного расположения, и число вариантов раскраски карт. Проблема четырёх красок становилась совершенно неприступной[21]. Математикам не удавалось получить доказательство более ста лет. Лишь в 1976 К. Аппель и В. Хакен из Иллинойского университета смогли доказать гипотезу. Но этого новаторскому шагу, – успеха они смогли добиться применение компьютера в благодаря доказательстве математической теоремы. Идея их доказательства состояла в следующем: сначала доказывается возможность раскраски для карт с числом n стран, 𝑛𝑛 ≥ 𝑛𝑛 0 , затем с помощью компьютера подтверждается возможность раскраски R карт и для 𝑛𝑛 < 𝑛𝑛 0 . На доказательство ушло более тысячи часов машинного R времени, перебрав громадное число вариантов, компьютер подтвердил справедливость гипотезы. Таким образом, вековая проблема четырех красок была решена[18]. В 1936 году психолог Левин высказал предположение, что «жизненное пространство» индивидуума можно представить с помощью планарной карты. На такой карте области представляют различные типы деятельности человека, например, то, что он делает на работе, дома, или же его хобби. Эта точка зрения привела психологов Научно-исследовательского центра групповой динамики к другой психологической интерпретации графа. Люди в этой интерпретации представляются вершинами, а их отношения ребрами. Примерами таких отношений являются, например, любовь, ненависть, общение, подчинение. Физики-теоретики, для внутренних нужд своей науки, “открывали” теорию графов не один раз. Внутри чистой математики теория графов впервые изучалась Вебленом в его классической книге по топологии. В 20-м веке задачи связанные с графами, появились в разделах математики: алгебре, теории вероятностей, теории чисел, топологии и других. Методы этих разделов стали успешно использоваться для решения задач теории графов. Наряду с термином "граф" в начале 20 века 9

употреблялись в качестве синонимов и другие термины, например, карта, комплекс, диаграмма, сеть, лабиринт. Начиная с 50-х годов XX века в связи с развитием вычислительной техники, становлением кибернетики, теория графов получила широкое развитие [26]. 1.2 Основные понятия теории графов Граф представляет собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек. На схемах и рисунках, отрезки бывают прямолинейными и криволинейными, а длины отрезков и расположение точек - произвольными. Точки называют вершинами графа, а отрезки – рёбрами[26]. Вершины, не принадлежащие ни одному ребру, называются изолированными. Граф, состоящий из изолированных вершин – нулевой граф (рисунок 1.1). Рисунок 1.1- Нулевой граф Если каждые две различные вершины графа соединены одним и только одним ребром, то такой граф называется полным (рисунок 1.2). В полном графе каждая его вершина принадлежит одному и тому же числу рёбер. Чтобы задать полный граф необходимо знать число его вершин. Две вершины, соединенные ребром, называются смежными. Два ребра, которые 10

имеют общую концевую вершину (инцидентные этой вершине), также называются смежными. Рисунок 1.2 – Полный граф Число рёбер, которые выходят из одной вершины называется степенью вершины. Вершины могут быть чётные (если имеют чётную степень) и нечётные (если имеют нечётную степень). О степенях вершин графа можно узнать всего лишь имея общее представление о графе, например степень каждой вершины полного графа на единицу меньше числа его вершин [9]. Если вершинам графа сопоставить буквы, числа или некую другую информацию, то говорят, что такой граф является помеченным. Если рёбрам графа поставлены в соответствие некие веса, такой граф называется взвешенным. Если на рёбра графа нанести стрелки, обозначающие направления, то эти ориентированные рёбра графа будут называться дугами. Если у графа все рёбра являются ориентированными, то такой граф называется ориентированным, или орграфом. Графы могут быть также представлены в виде списков, таблиц, выражений. Вершины графа могут быть изображены точками, окружностями, треугольниками, а рёбра – отрезками, прямыми или же фигурно изогнутыми линиями. Учитывая подобное разнообразие, важно уметь определять, когда два представления графа являются эквивалентными (изоморфными). Эквивалентные представления графа содержат одинаковые вершины и одинаковые связи между ними. Иными словами, между вершинами и 11

рёбрами двух представлений должно существовать взаимно однозначное соответствие, такое, что степени вершин в обоих случаях будут одинаковы (рисунок 1.3). Рисунок 1.3- Разные представления одного и того же графа В теории графов существует три вида графов: обыкновенные, мультиграфы и псевдографы (рисунок 1.4). Рисунок 1.4 – Три вида графов Если граф обыкновенный, то его вершины могут быть соединены только лишь одним ребром, если же рёбер более одного, то этот граф будет являться мультиграфом. А в случае, когда вершина мультиграфа может соединяться сама собой, граф называется псевдографом.Если начало и конец ребра находятся в одной вершине, то оно называется петлёй [8]. Путём в графе называется любая последовательность вершин, в которой каждые две соседние вершины соединены ребром. Длиной пути называется количество рёбер в нём. Если же первая и последняя вершины пути совпадают и все рёбра в нём различны, то такой путь называется 12

циклом [13]. Любой цикл можно представить графически в виде многоугольника (рисунок 1.5). Рисунок 1.5 – Примеры циклов 1.3 Эйлеровы и гамильтоновы графы Эйлеровым путём называется путь, содержащий все рёбра графа, а эйлеровым циклом или эйлеровой цепью, называется цикл, который содержит все рёбра графа и притом только по одному разу. Граф, который содержит такой цикл, называется эйлеровым[16]. Задачи на головоломки, в которых необходимо вычертить на плоскости одним росчерком замкнутые кривые, при этом обходя каждый участок ровно один раз, являются примерами задач на Эйлеровы графы. Чтобы граф имел эйлерову линию, он должен быть связным. Каждая эйлерова линия должна входить в каждую вершину и выходить из неё одно и то же число раз, следовательно, степени всех вершин графа должны быть чётными[11]. Всё это присутствует в задаче о кёнигсбергских мостах. Для наличия в графе эйлеровой линии должны выполняться два необходимых условия. Это связность и чётность степеней всех вершин графа. Эйлер доказал, что эти условия являются также и достаточными[17]. Задачу Эйлера о кёнигсберских мостах можно обобщить: «Для каких графов можно найти такой цикл, в котором участвовало бы каждое ребро 13

графа, причём только один раз?» Ответ на этот вопрос даёт следующая теорема. Теорема.Граф является эйлеровым тогда и только тогда, когда он связный и степень каждой его вершины чётна. Доказательство. Если граф эйлеров, то он связный и степень каждой его вершины чётна (рассуждение, как в задаче о кёнигсберских мостах). Докажем обратное, что связный граф,степень каждой вершины которого чётна, является эйлеровым. Начнём обходить граф с некоторой вершины р, проходя каждый раз через новые рёбра. Так как степень каждой вершины чётна, этот обход может закончится только в р. Это означает, что в графе, есть цикл. Обозначим его с 1 . Сотрём рёбра этого цикла. Граф распадётся на части, каждая из которых является связным графом и имеет общую вершину с удалённым циклом с 1 .Степень каждой вершины также чётна. Если в полученном графе нет рёбер, то всё доказано. В противном случае применим к нему вышесказанные соображения. Действуя, таким образом, мы получим разбиение исходного графа на циклы. Рассмотрим цикл с 2 , имеющий вершину v с циклом с 1 .Путь, начинающийся с v и состоящий из цикла с 1 и следующего непосредственно за ним циклас 2 , является замкнутым и содержит рёбра этих двух циклов. Продолжая эту процедуру, мы сможем построить цикл, содержащий все рёбра графа по одному разу. Следовательно, рассматриваемый граф эйлеров, что и требовалось доказать [13]. Примерами эйлеровых графов могут служить: 1.План выставки, если расположить её экспонаты по двум сторонам залов, т.е. можно составить замкнутый маршрут, используя который посетитель сможет пройти по каждому залу в точности два раза – по одному с каждой стороны в разных направлениях. 2.Обойти можно любой город, пройдя по каждой улице ровно два раза - по одному в каждом направлении. 14

Гамильтонов граф, цикл, путь связаны с именем ирландского математика Уильяма Гамильтона, который в 1859 году в ходе исследования задачи «кругосветного путешествия» по додекаэдру определил эти классы. Вершины додекаэдра в этой задаче обозначали известные города, такие как Брюссель, Эдинбург, Франкфурт и др., а рёбра — это соединяющие их дороги. Путешественник должен пройти «вокруг света», найдя путь, проходящий ровно один раз через все вершины. Чтобы задача стала интересней, заранее устанавливается порядок прохождения городов. А для более лёгкого запоминания уже соединённых городов, в каждую вершину додекаэдра был вбит гвоздь, и проложенный путь отмечался небольшой верёвкой, которую можно обматывать вокруг гвоздя. Но такая конструкция оказалась слишком громоздкой, и Гамильтон предложил новый вариант игры, заменив додекаэдр плоским графом, изоморфным графу, построенному на рёбрах додекаэдра [4]. Путь, который проходит через каждую из вершин ровно один раз, называется гамильтоновым, а если этот путь замкнутый, то это гамильтонов цикл. Граф, содержащий гамильтонов цикл – гамильтонов [3]. По способу задания эйлеровы и гамильтоновы пути и циклы сходны. Эйлеровы пути и циклы содержат все рёбра, и при том по одному каждое, а гамильтоновы - все вершины и тоже по одному разу каждую. Для того чтобы выяснить, обладает ли граф эйлеровым путём или циклом, нужно всего лишь определить степень каждой из его вершин, а вот способа определить обладает ли граф гамильтоновым путём или циклом не существует. Решение этой проблемы имеет практическую ценность, так как к игре Гамильтона близка известная задача о коммивояжере, который должен объехать несколько пунктов и вернуться обратно. Он обязан побывать в каждом пункте в точности по одному разу, и заинтересован затратить на поездку как можно меньше времени. А для этого требуется определить все варианты посещения городов и подсчитать в каждом случае затрату времени. 15

В теории графов существует несколько достаточных условий существования гамильтоновых циклов в графе: 1.Всякий полный граф является гамильтоновым, так как он содержит такой простой цикл, которому принадлежат все вершины данного графа. 2.Если у графа, кроме простого цикла, который проходит через все его вершины, содержатся и другие рёбра, то этот граф также будет являться гамильтоновым. Если граф имеет один гамильтонов цикл, то он может иметь и другие гамильтоновы циклы. На вопрос о существовании в графе гамильтонова цикла отвечает известная теорема Дирака. Теорема. Если в простом графе с n (≥ 3) вершинами локальная степень каждой вершины не менее n/2, то граф является гамильтоновым[4]. 1.4 Лабиринты Задачи о лабиринтах появились ещё в глубокой древности. В то время бывало, что вокруг крепостей строили сооружения (лабиринты) по плану, который, знал только владелец крепости. Эти сооружения во время воин служили убежищем или местом, где хранили драгоценности. Иногда их использовали для наказания, помещая туда людей, приговорённых к смертной казни. Не зная устройства лабиринта, человек не находил выхода из него и после долгих скитаний погибал от голода [19].Древние люди считали задачу о лабиринтах вообще неразрешимой. Но на самом деле безвыходных лабиринтов нет, разобраться и найти выход из самого запутанного лабиринта не составляет особого труда [14]. Что же означает слово лабиринт. Произошло слово «лабиринт» от слова «Лабрис» - так в Древней Греции назвали оружие – секиру с двойным лезвием. Древний бог Арес-Дионис спустился с неба на Землю, когда на ней еще ничего не было, только мрак. Арес-Дионис прокладывал себе путь, 16

рассекая лабрисом темноту и прорезая борозды. Шёл он, описывая круги. И дорога, которую он прорезал, с каждым шагом становилась светлее. Так родился лабиринт, то есть «путь». Люди пытались изобретать самые разнообразные замысловатые и "безвыходные" лабиринты. Но возможно ли построить или даже начертить безвыходный лабиринт? Ответ на этот вопрос дал выдающийся математик XVIII века Эйлер. Исследования, проводимые им, привели к заключению, что нет безвыходных лабиринтов. Лабиринты это запутанные коридоры с тупиками, входами и выходами[10]. Геометрическая постановка задачи о лабиринтах заключается в следующем: дорожки, аллеи, коридоры, шахты, галереи и другие лабиринты тянутся, изгибаются во все стороны, разветвляются по разным направлениям, перекрещиваются, образуют тупики и так далее. Лабиринт - это граф. А исследовать его - это найти путь в этом графе. Способ обходить все рёбра графа можно использовать, например, для поиска пути, позволяющего выбраться из лабиринта. Маршруты в лабиринтах могут быть представлены графами. Рёбра графа – это коридоры, а вершины – входы, выходы, перекрёстки и тупики. Если схему лабиринта преобразовать в граф, то с этим лабиринтом намного легче разобраться. На графах представленных лабиринтов легко увидеть прямой маршрут, ведущий к цели. Задачи о лабиринтах можно разделить на две группы: а) задачи, в которых необходимо найти путь в лабиринте, если указаны начальная и конечная точки движения; б) задачи, в которых необходимо найти выход из лабиринта [19]. Для решения подобных задач французский математик М.Тремо установил следующие правила: 1. Отправляемся от выбранной вершины (первого перекрестка) и идем по любому ребру, пока не приходим или в тупик (к вершине), или к новому перекрестку (вершине). Тогда: 17

а) Если окажется, что мы попали в тупик, возвращаемся назад и пройденное ребро должно быть уже отброшено, так как мы прошли его два раза (туда и обратно). б) Если приходим к новому перекрестку, то направляемся по новому произвольному ребру, не забывая всякий раз отмечать путь, по которому прибыли, и путь, по которому отправились дальше. 2. Прибыв на известный нам перекресток по новой дороге, мы должны сейчас же повернуть обратно, предварительно отметив этот путь двумя чёрточками (рисунок 1.6). Рисунок 1.6 – Правило 2 3. Если мы приходим на известный перекресток таким, путём, которым уже раз прошли, то, отметив этот путь второй черточкой, отправляемся дальше путём, которым еще не проходили, если только такой путь существует. Этот случай изображен на рисунке (рисунок 1.7). Рисунок 1.7 – Правило 3.1 18

Но если такого пути нет, то выбирается дорога, по которой мы прошли только один раз. Случай этот показан на рисунке (рисунок 1.8). Рисунок 1.8 – Правило 3.2 4.Правило одной руки. Оно состоит в том, что по лабиринту надо двигаться, не отрывая одной руки (правой или левой) от стены. В 1882 году Тремо разработал метод, позволяющий попасть в центр сложного, многосвязного лабиринта или выйти из него. Заключаются он в следующих правилах: выйдя из любой точки лабиринта, надо сделать отметку на его стене и двигаться в произвольном направлении до тупика или перекрестка; в первом случае вернуться назад, поставить вторую метку, означающую, что путь пройден дважды - туда и назад, и идти в направлении, не пройденном ни разу, или пройденном один раз; во втором - идти по произвольному направлению, отмечая каждый перекресток на входе и на выходе одной меткой; если на перекресте одна метка уже имеется, то следует идти новым путём, если нет - то пройденным путём, отметив его второй меткой. Зная алгоритм Тремо, можно скорректировать поведение легендарного Тесея. Вдохновленный подарком любимой Ариадны, он уверенно идет по лабиринту. Вдруг перед ним возникает ход, по которому уже протянута нить. Что делать? Ни в коем случае не пересекать ее, а вернуться по уже известному пути, сдваивая нить, пока не найдется еще один не пройдённый ход. Значит, и нитью под землей надо уметь пользоваться[4]. 19

1.5 Графы с цветными рёбрами и их свойства Граф с цветными рёбрами – это граф, рёбра которого окрашены в несколько цветов. В теории графов задачи на раскраски рёбер занимают важное место. Использование таких графов делает многие задачи более наглядными и упрощает их решение. Целый ряд практических задач сводится к построению раскрасок [22]. Характерной особенностью задач с цветными рёбрами является существование объектов, которые по той или иной причине не могут быть объединены в одну группу. В качестве примера можно рассмотреть ситуацию, когда среди участников шашечного турнира, в какой - то промежуток времени имеются участники уже сыгравшие партию друг с другом и участники ещё не сыгравшие. Для удобства рёбра графа, соответствующие одному отношению окрашивают в один цвет, а другому отношению – во второй цвет. На рисунке изображен граф с пятью вершинами и ребрами двух цветов, но этот граф можно изобразить и другими непохожими рисунками (рисунок 1.9). Рисунок 1.9 – Граф с цветными рёбрами Свойства графов с цветными рёбрами: 1 . Из любой вершины графа с шестью или более вершинами и рёбрами двух цветов выходит, по меньшей мере, три ребра одного цвета. 2 . В любом графе с шестью или более вершинами и рёбрами двух цветов найдётся по меньшей мере один треугольник с одноцветными сторонами. 20

3.Если в графе с пятью вершинами и рёбрами двух цветов нет треугольника с одноцветными сторонами, то граф можно изобразить в виде "пятиугольника" с красными сторонами и синими диагоналями. 4. В любом графе с шестью или более вершинами и рёбрами двух цветов всегда найдутся два треугольника с одноцветными сторонами. Эти два треугольника могут иметь общую вершину или даже общее ребро. 5. В полном графе с 17 или более вершинами и рёбрами 3 цветов всегда найдется, по меньшей мере, один треугольник с одноцветными сторонами[6]. 21

2 МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ФАКУЛЬТАТИВНОГО КУРСА «ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ» 2.1 Роль факультативных занятий как формы обучения математике Факультативный курс – (франц. facultative –возможность) учебный курс или предмет, который изучают студенты вузов и обучающиеся средних учебных заведений по желанию для того чтобы углубить и расширить свои научно – теоретические знания [23]. Уже на рубеже XIX и XX вв. педагоги утверждали, что преподавание в общеобразовательной школе какого – либо предмета по программе будет успешнее, если он будет дополнен циклом необязательных для обучающихся внепрограммных занятий по группам. Эти групповые занятия должны были, первым делом, учитывать «местные условия», такие как: реальные запросы и интересы конкретного коллектива обучающихся, реальные возможности преподавателя вызвать и развить интерес обучающихся к важным аспектам конкретного предмета, не охваченного обязательной программой. Именно так возникла идея организации факультативных занятий в школе [30]. Назначение факультативных занятий заключается в развитии способностей, интересов обучающихся в сочетании с общеобразовательной подготовкой, зарождение интереса к математике уже на первичном уровне и развитие его до познавательного уровня и тем самым формирование основы для выбора профиля. Факультативные занятия являются одной из форм дифференцированного обучения. Целью организации факультативных занятий является расширение кругозора обучающихся, развитие их 22

математического мышления, формирование активного познавательного интереса к предмету. Программа факультативных занятий по математике в объединении с программой основного курса математики для средней школы составляют программу повышенного уровня для обучающихся данного класса. Обучающиеся посещают факультативные занятия по желанию, следовательно, педагогу необходимо создать такие условия, при которых способные дети смогут реализовать свои возможности, а остальные смогут решать посильные для них задачи или, трудные задания, но с помощью учителя. Для того чтобы факультативные занятия были эффективными, их рекомендуется организовывать там, где имеются: 1)высококвалифицированные педагоги, которые способны проводить занятия на высоком научно-методическом уровне; 2) обучающихся, желающих изучать данный факультативный курс не менее 10 человек [1]. В общеобразовательных учреждениях с малой наполняемостью, группы обучающихся для факультативных занятий можно комплектовать по параллелям или из обучающихся смежных классов (5-6 классы, 8-9 классы и т.п.). Запись обучающихся на факультативные занятия идёт на добровольных началах и с учётом их интересов, без принуждения обучающихся изучать факультативные предметы в обязательном порядке. Более внимательно нужно относиться к тем обучающимся, которые испытывают трудности в изучении математики или совмещают обучение в школе с другими видами занятий (спорт, музыка и т. д.). По завершению факультативного курса обучающиеся сдают зачет (с оценкой), о чем делается отметка в аттестате. Отличительной особенностью факультативного курса является то, что программа курса для каждого класса составлена из ряда основных тем (независимых друг от друга), содержание которых непосредственно 23

примыкает к общему курсу математики. Однако содержание учебной работы обучающихся на факультативных занятиях определяется не только математическим содержанием изучаемых тем и разделов, но и различными методическими факторами: - характером объяснения учителя; - соотношением учебных упражнений и теории; - содержанием познавательных вопросов и задач; - сочетанием самостоятельной работы и коллективного обсуждения полученных каждым обучающимся результатов. Проведение факультативных занятий по математике не означает отказа от других форм внеклассной работы (математические кружки, вечера, олимпиады и т. д.). Факультативные занятия должны дополнять эти формы работы с обучающимися, интересующимися математикой [6]. К проведению факультативных занятий предъявляются следующие требования: 1.Преемственность в содержании, методах и формах организации занятий по математике должна определяться целями обучения математики, всестороннего развития и воспитания учащихся. 2. Взаимосвязанное построение уроков и факультативных занятий по математики не должно противоречить дидактическим принципам в обучении математики. 3. Не должно быть противоречий с научно обоснованными психологопедагогическими требованиями, такими как: изучение новых понятий на основе известных; опора при изучении математических абстракций на конкретные модели; использование практических возможностей приложения математики не только на развивающем этапе изучения данного вопроса, но и в качестве мотива, обосновывающего необходимость изучения этого раздела, вопроса. 4. Не должно быть несогласованности с нормами организации работы общеобразовательной школы. Например, нельзя часы, отведенные на 24

факультативные занятия, использовать для внеклассной работы или дополнительных занятий по математике. 5. Главным критерием эффективности взаимосвязанного построения факультативных занятий по математике должна быть результативность неразрывно связанных друг с другом процессов обучения, развития и воспитания школьников. 6. Факультативные занятия по математике целесообразно проводить, учитывая их функции – развивающую, воспитывающую и учебную[1]. Методические рекомендации по организации факультативных занятий: 1.Взаимосвязь в содержании, формах и методах организации учебной работы и факультативных занятий. 2.Обеспечение взаимосвязи (по содержанию) уроков и факультативных занятий. 3.Единство в содержании факультативных занятий и различных разделов математики. 4. Активизация самостоятельной работы обучающихся. 5.Построение учебного процесса как совместной исследовательской деятельности обучающихся. 6.Использование на лекциях наглядных пособий, конспект-таблиц. 7.Использование системы ключевых задач по темам на факультативных занятиях. 8.Использование историко-математического материала на факультативных занятиях. 9.Принципы занимательности занятий. 10.Построение занятий проблемного изучения материала. Факультативные занятия, прежде всего, должны быть интересными и увлекательными для обучающихся. В этом отношении главная цель педагога - добиться понимания обучающимися того, что они подготовлены к работе над сложными проблемами, но 25 всё же для этого необходима

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

Таким образом, в основе выбора обучающимися факультативных занятий по математике лежит серьезный интерес к математике или её приложениям. Этот интерес удовлетворяется и развивается при рассмотрении тем, имеющих большое общекультурное или прикладное значение, в частности, при изучении вопросов теории графов. В соответствии с требованиями, предъявляемыми к факультативным занятиям, на основе материала первой главы, мною разработана программа факультативного курса для обучающихся 9 класса «Элементы теории графов». К сожалению, у меня не было возможности провести факультативные занятия в этом учебном году, так как я работаю в 5-8 классах. В следующем учебном году я планирую организовать проведение факультативного курса. Надеюсь, что обучающиеся проявят интерес к факультативным факультативный школьной задач курс будет заинтересуются и занятиям по теории графов, что способствовать решению поставленных реформой образовательных, воспитательных и развивающих обучения, повышению их развитию математического мышления школьников, культурного уровня, формированию самостоятельной творческой мыслительной деятельности обучающихся, подготовит их к олимпиадам и к обучению в ВУЗе. 2.2 Программа и содержание факультативного курса “Элементы теории графов» для обучающихся 9 класса Программа факультативного курса является обучающей и содержит: -Пояснительную записку. -Цели курса, задачи курса. -Содержание курса. -Требования к умениям и навыкам. -Учебно - тематическое планирование. -Методические рекомендации. 27

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

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

практикум, урок-беседа, урок обобщающей задачи, работа в группах, защита творческих работ. В результате изучения курса обучающиеся должны знать: - основные понятия и утверждения теории графов; - определение эйлерова и гамильтонового графов и их элементов; - определение лабиринта и правила решения задач на лабиринты; - определение графов с цветными рёбрами и их свойства. В результате изучения данного факультативного курса развиваются следующие общеучебные и профильные умения и. навыки: - учебно-организаторские; - учебно-интеллектуальные; - учебно-коммуникативные; - учебно-информационные. Факультативный курс «Элементы теории графов рассчитан на 12 часов и включает в себя 5 тем (таблица 2.1).Результатом усвоения материала факультативного курса является написание и защита обучающимися творческих работ к итоговому занятию по одной из предложенных тем. Знания, полученные после прохождения факультативного курса «Элементы теории графов» возможно, практически реализовать в средней школе при решении олимпиадных задач, в области высшей математики. Все задачи для практической части занятий факультативного курса и темы докладов вынесены в Приложение 1 к выпускной квалификационной работе. 30

Таблица 2. 1 – Учебно-тематический план Тема занятия Кол-во часов Форма проведения занятия Форма контроля История возникновения теории графов. Основные понятия теории графов. 2 Лекция-беседа. Практическая работа. Решение задач. Самостоятельная работа. Эйлеровы и гамильтоновы графы 2 Лабиринты 2 Графы с цветными рёбрами и их свойства 2 Лекция-беседа. Практическая работа. Сообщения обучающихся. Беседа. Практическая работа. Сообщения обучающихся. Беседа. Практикум по решению задач. Графы и логические задачи 2 Практикум по решению задач. Зачётный урок 2 Урокконференция. Решение задач. Самостоятельная работа. Поисковые задания. Практическая работа. Сообщения по теме. Исследовательские задания. Творческие задания. Решение задач. Самостоятельная работа. Защита творческих работ. Методические рекомендации к проведению занятий. Занятие №1. Форма проведения первого занятия лекция-беседа, т.к. это занятие вводное, ознакомительное. Рассчитано первое занятие на два часа. Для его проведения понадобится компьютер и проектор, так как учителю рекомендуется подготовить презентацию, чтобы повысить интерес к данному факультативному курсу. Здесь мы будем пользоваться активными и интерактивными методами обучения: беседа с учениками (учитель задаёт вопросы обучающимся, а они учителю), творческие задания, работа в микрогруппах. 31

В начале первого занятия обучающимся необходимо дать информацию о том, как будет проходить факультативный курс, какие цели перед ними стоят, как будет проходить итоговое занятие. Далее учитель расскажет материал из истории графов, о том, как зародилась теория графов, в каких сферах деятельности применяется эта теория, и для чего она может пригодится самим обучающимся. Это поможет привить интерес к данному факультативному курсу и к изучению теории графов в дальнейшем. Затем учитель вместе с обучающимися формулирует основные понятия теории графов в ходе решения следующей задачи: В первенстве класса по настольному теннису 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводится по круговой схеме – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной и Еленой; Борис, как уже говорилось, с Андреем и еще Галиной; Виктор – с Галей, Димой и Еленой; Галина – с Андреем и Борисом; Дмитрий – с Виктором; Елена – с Андреем и Виктором. Сколько игр проведено к настоящему моменту и сколько еще осталось? Далее учитель предлагает обучающимся задачи на закрепление полученных знаний. Задачи №1, 2 можно дать для самостоятельного решения. После того как все решат можно вызвать 2-3 ученика к доске (для каждой задачи), для того чтобы они изобразили полученные графы. Ребята увидят, что изображения графов у всех различно и это не является ошибкой. Задачи №3,4 учитель может также предложить решить самостоятельно, но уже без проверки решения у доски. Задачи №5 и № 6 решаем с вызовом учеников к доске. Для решения задач №7 и №8 можно разделить учеников на микрогруппы по 3-4 обучающегося, и та группа, которая решит задачу быстрее всех, получат «5». Для домашнего задания можно предложить обучающимся самим придумать по одной задаче друг для друга на карточках (с одной стороны 32

будет условие задачи, с другой решение) и в начале следующего занятия они обменяются карточками и решат их. Таким образом, данное занятие пройдет довольно оживленно, каждому ученику представится возможность принять участие в беседе, дать определение новому понятию. У обучающихся, которые слабы в математике проявится к ней интерес. Занятие №2. В начале данного занятия обучающиеся решают задачи на карточках, которые они составили дома, обмениваясь ими. На это можно отвести 20-25 минут. Затем учитель собирает карточки с решениями. Форма проведения данного занятия комбинированная. Также на занятии пользуемся активными и интерактивными методами обучения: творческие задания, беседа с учителем, поиск решений. Для наглядности учителю рекомендуется приготовить презентацию. В начале занятия учитель формулирует задачу о Кёнигсбергских мостах: «Кёнигсберг расположен на двух островах и берегах реки Прегель. Части города соединены семью мостами так, как показано на рисунке (рисунок 2.1). В воскресные дни горожане совершают прогулки по городу. Может ли кто-нибудь из них, выйдя из дома, пройти только один разпо каждому мосту и вернуться домой?», и предлагает обучающимся решить её. На рисунке буква Л обозначает левый берег, П – правый, А и Б – острова (рисунок 2.2). Дети должны попробовать пройти через каждый мост ровно 1 раз и убедиться, что задача не имеет решения. Рисунок 2.1 – Рисунок к задаче о Кёнигсбергских мостах 33

Рисунок 2.2 – Граф к задаче о Кёнигсбергских мостах Обучающиеся предлагают свои решения, выходят к доске, и приходят к выводу, что эта задача решения не имеет. Потом предложить ученикам составить подобные задачи, которые будут иметь решения. Далее учитель даёт определение эйлерова пути, эйлерова цикла, эйлерова графа. Затем формулирует и доказывает теорему об эйлеровом графе. Затем учитель знакомит обучающихся с именем ирландского математика Гамильтона и с его исследованием задачи «кругосветного путешествия» по додекаэдру, вводит понятия гамильтонов путь, гамильтонов цикл, гамильтонов граф. Знакомит обучающихся с достаточными условиями существования гамильтоновых циклов и теоремой Дирака. После этого учитель предлагает обучающимся задачи для самостоятельного решения. После решения задач рекомендуется провести фронтальный опрос на пройденные свойства графов. Занятие №3 Данное занятие рассчитано на два часа. На занятии рекомендуется пользоваться интерактивными методами обучения: ученик в роли учителя, беседа, поисковые задачи, соревнования, творческое задание. Необходимо за неделю до занятия трём обучающимся дать задание подготовить сообщение по данной теме. Они должны будут сделать презентацию и разобрать данную тему, чтобы выступить на уроке вместо 34

учителя. Занятие должно пройти в форме беседы. Первый обучающийся расскажет об истории появления задач о лабиринтах об их геометрической постановке. Два других обучающихся расскажут по два правила прохождения лабиринта. Слушатели будут задавать вопросы. После теоретической части учитель предлагает решить задачи. Данные соревнования, задачи кто имеют быстрее поисковый пройдет характер. лабиринт. Можно После устроить прохождения лабиринтов ученики должны высказать своё мнение, какими правилами прохождения они пользовались, какое им понравилось больше. На дом дать творческое графическое задание каждому придумать свой лабиринт. На следующем занятии ребята обменяются лабиринтами и пройдут их. Занятие №4 В начале занятия обучающиеся обмениваются карточками с лабиринтами, придуманными дома, и пытаются их пройти. На это можно отвести 5-10 минут. Затем учитель собирает карточки с решениями. За неделю до занятия выбрать группу из 5 учеников, дать им задание подготовить презентацию и рассмотреть задачи на свойства графов с цветными рёбрами, описанные в первой главе дипломной работы. Урок будет проходить в форме лекция-беседа. Каждый ученик разберет по 1 задаче. Он подготовит вопросы, которые будет задавать слушателям. После того, как будет разобрана теоретическая часть, разделить класс на 4 группы. В каждой группе будет присутствовать ученик, который выступал в роли учителя. Дать всем одинаковые задачи для самостоятельного решения, и та группа, которая решит все задачи быстрее всех получает «5», вторая группа «4». В конце занятия можно устроить фронтальный опрос, тем самым закрепить полученные знания. Занятие №5 Данное занятие - практикум по решению логических задач. Рассчитано на два часа. Используем интерактивные методы обучения.Для решения 35

первой и второй задачи можно вызвать обучающегося к доске. Разобрать задачу всем классом. Можно предложить ребятам проверить решение второй задачи на практике. Вызвать к доске сначала 2, затем 3, 4 и 5 обучающихся и попросить их пожать друг другу руки. Весь класс сможет убедиться, что всего было 10 рукопожатий - использование элементов игры. Затем, можно предложить обучающимся решить задачи. Первые две задачи самостоятельно. Первые пять обучающихся, правильно решившие задачу, получают оценку. Первые двое показывают решение на доске соответственно 1 и 2 задачи. Для решения 5,6 и 7 задач разделим класс на 3 группы по рядам. Чей ряд быстрее решит - получают оценки. При этом учитель должен спросить решение задачи у слабого ученика из группы. 8 и 9 задачу ученики должны решить самостоятельно. Возможно, некоторых детей заинтересуют другие способы решения ранее пройденных задач и найдут их. Это повысит интерес к математике. Занятие №6 Данное занятие является заключительным и представляет собой урокконференцию. Обучающиеся заранее должны будут взять темы докладов у учителя и подготовить выступление с презентацией. Доклады представляются в качестве поисковых и исследовательских заданий. Защита каждой работы рассчитана на 7-10 минут. Темы докладов подобраны так, чтобы показать значимость математики среди наук, показать в каких областях применяется теория графов. Возможно, это занятие подтолкнёт некоторых ребят выбрать математический профиль в дальнейшем обучении. 36

ЗАКЛЮЧЕНИЕ Теория графов в настоящее время является интенсивно развивающимся разделом дискретной математики. Это объясняется тем, что в виде графовых моделей описываются многие объекты и ситуации. В ходе написания выпускной квалификационной работы была изучена и проанализирована учебно-методическая и психолого – педагогическая литература по теме исследования. В результате были определены основные понятия и утверждения теории графов, раскрыта возможность использования графов как средства обучения решению задач, определена роль факультативных занятий как формы обучения математике. В соответствии с требованиями и методическими рекомендациями была разработана программа факультативного курса «Элементы теории графов» для обучающихся 9 классов, произведен отбор математического содержания курса, осуществлена разработка системы задач для каждой темы, составлены методические рекомендации для учителя по проведению факультативного курса. Результаты исследования показали, что изучение элементов теории графов на факультативном курсе полезно и методически целесообразно. Курс способствует решению поставленных школьной реформой образовательных, воспитательных и развивающих задач обучения, развитию математического мышления школьников, повышению культурного уровня обучающихся, формированию самостоятельной творческой мыслительной деятельности обучающихся, подготавливает их к олимпиадам и к обучению в ВУЗе. Следовательно, цель выпускной квалификационной работы реализована, задачи решены. В перспективе целесообразным будет создание факультативных курсов для обучающихся 10-11 классов, посвященных другим, не менее важным вопросам теории графов. 37

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 1.Балк М.Б., Балк Г.Д. Математический факультатив - вчера, сегодня, завтра // Математика в школе. - 2007. - №3. - С.14-17. 2.Барболин М. Головоломки и графы // Квант.- 1975.- № 2.-С.59-60. 3. Белов В.В. Теория графов.- М.: Высшая школа, 1976.- 392 с. 4.Березина Л. Ю. Графы и их применение. - М.: Просвещение, 1979.- 143 с. 5.Берж К. Теория графов и её применение.- М.: Иностранная литература, 1962.- 320 с. 6. Донец Г.А. Алгебраический подход к проблеме раскраски плоских графов.- М.: Наукова думка, 1982.-144с. 7. Журбенко И.Г. О материалах для факультативных занятий // Математика в школе.- 2009.-№2.- С.52-53 8. Зыков А.А. Основы теории графов. - М.: Вузовская книга, 2004.-664 с. 9.Калугин Н.А. Элементы теории графов. – Самара: Издательство СГАУ, 2013. – 48 с. 10. Керн Г. Лабиринты мира. СПб.: Изд-во "Азбука-классика", 2007.- 448с. 11.Литвинова С.А, Куликова Л.В. и др. За страницами учебника математики. - Волгоград: Панорама, 2006.-176 с. 12.Мельников О.И. Занимательные задачи по теории графов.-Минск:НТООО «ТетраСистемс», 2001.- 144 с. 13.Мотькина Н.Н. Начала теории графов в задачах. – Петрозаводск: КГПУ, 2000.-20 с. 13.Никитина Г.Н. Некоторые приёмы развития пространственного мышления учащихся // Математика в школе.-1993.- № 5.-С.53-56. 14.Носов В.И., Т.В. Бернштейн Т.В.,Носкова Н.В., Храмова Т.В. Элементы теории графов.- Новосибирск, 2008. — 107с. 15. Олехник С. Н., Нестеренко Ю.В. и др. Старинные занимательные задачи.М.: Наука, 1985.- 160 с. 16. Оре О. Теория графов.- М.: Наука, 1980.-352 с. 38

17.ОреО. Графы и их применение. - Издательство «Мир»,1965.- 174 с. 18.Самохин А. В. Проблема четырех красок: неоконченная история доказательства //СОЖ. - 2000. - № 7. - С. 91-96. 19.Саркисян А.А., Колягин Ю.М. Познакомьтесь с топологией.- М.: Просвещение, 1976.- 80 с. 20.Судоплатов С.В.,Овчинникова Е.В. Элементы дискретной математики. М.:ИНФРА-М,2002.-143с. 21.Ткачева М. В. Домашняя математика. - М.: Просвещение, 1994. – 255с. 22. Уилсон Р. Введение в теорию графов М.: Мир, 1977. – 208 с. 23.Факультативный курс //Большая советская энциклопедия /Сост. В. А. Юдин. - М.: Советская энциклопедия, 1985. – с. 573. 24.Фляйшнер Г. Эйлеровы графы и смежные вопросы. Пер. с англ.М.:Мир,2002, 176 с. 25.Энциклопедия для детей. Т 11. Математика. - М.: Аванта Плюс, 2004.-688 с. 26. Энциклопедический словарь юного математика/Сост. Э-68 А. П. Савин. М.: Педагогика, 1989. - 352 с. 27.Харари Ф. Перечисление графов. – М.: Мир, 1977. – 324 с. 28. Харари Ф. Теория графов. – М.: Мир, 1977. – 296 с. 29. Химические приложения топологии и теории графов: пер. с англ. / под ред. Р. Кинга. – М.: Мир, 1987. – 560 с. 30.Якунина М.С. Больше внимания факультативам // Математика в школе. 2010. №3. - С.51-52. 39

ПРИЛОЖЕНИЕ 1 Задачи к занятию №1 1.Нарисуйте полный граф с n вершинами, если: n=2, n=3, n=5 . Решение: (рисунок 1). Рисунок 1- Решение задачи №1 2.Скольким рёбрам принадлежит вершина в полном графе с n вершинами, n=3, n=5, n=k? Ответ: двум рёбрам. 3.Существует ли полный граф с семью рёбрами? Ответ: да, существует. 4.Сколько рёбер в полном графе с n вершинами, если n =3, n=4, n=5? Ответ: 3 ребра, 4 ребра, 5 рёбер. 5.Найдется ли граф с пятью вершинами, степени которых все различны, т.е. равны 0, 1, 2, 3, 4? Ответ: да, найдется. 6. Нарисуйте граф с 5 вершинами, две из которых имеют одинаковую степень. Решение: (рисунок 2). Рисунок 2- Решение задачи № 6 7.В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими? Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а рёбра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа - 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 40

(т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится равным 37,5. Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным. Ответ. Соединить телефоны таким образом невозможно. 8. Можно ли нарисовать изображенный на рисунке граф не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз(рисунок 3). Рисунок 3 - Рисунок к задаче № 8 Решение. Если мы будем рисовать граф так, как сказано в условии, то в каждую вершину, кроме начальной и конечной, мы войдем столько же раз, сколько выйдем из нее. То есть все вершины графа, кроме двух должны быть четными. В нашем же графе имеется три нечетные вершины, поэтому его нельзя нарисовать указанным в условии способом. Задачи к занятию №2 9.Начертить граф с вершинами (1,2,3,4,5) и рёбрами (1,2), (2,3), (3,4), (3,1), (4,5), является ли этот граф эйлеровым? Решение:(рисунок 4). Ответ: да, является. Рисунок 4- Решение задачи № 9 10.Начертить граф с вершинами (А, Б, В, Г) и рёбрами (А, Г), (А, Б), (Б, В), является ли этот граф эйлеровым? Решение:(рисунок 5). 41

Ответ: да, является. Рисунок 5- Решение задачи №10 11.Попробуйте, не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии, вычертить следующие фигуры (рисунок 6). Рисунок 6- Рисунок к задаче №11 12. Какие буквы русского алфавита можно нарисовать, не отрывая карандаша от бумаги? Ответ: Б, В, Г, З, И, Л, М, О, П, Р, С, Ф, Ъ, Ь, Я. 13.Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все 12 ребер куба, не проходя дважды по одному ребру? Подпрыгивать и перелетать с места на место не разрешается. Решение:Рёбра и вершины куба образуют граф, все 8 вершин которого имеют кратность 3, и, следовательно, требуемый обход невозможен. 14.Мальчик нарисовал на бумаге три синих и три красных контура, которые нигде не пересекались. Затем рисунок накрыли листом бумаги так, что один из контуров оказался целиком накрыт, а все другие были частично видны. Нарисуйте закрытую часть рисунка (рисунок 7). Решение:(рисунок 8). 42

Рисунок 7- Рисунок к задаче №14 Рисунок 8- Решение задачи №14 15. Задача о четырех островах и четырнадцати мостах. Четыре острова соединены между собой и с берегами реки так, как показано на рисунке. Можно ли за одну прогулку обойти все эти мосты, побывав на каждом из них один раз (рисунок 9). Рисунок 9- Рисунок к задаче №15 Решение: Имеются две нечетные вершины В и С. Следовательно, за одну прогулку можно обойти все мосты, побывав на каждом из них один раз. При этом прогулку надо начинать на острове В и заканчивать на острове С или наоборот (рисунок 10). 43

Рисунок 10- Решение задачи №15 Задачи к занятию №3 16. Нарисуйте граф, соответствующий данному лабиринту (рисунок 11). Рисунок 11- Рисунок к задаче №16 Решение:(рисунок 12). Рисунок 12- Решение задачи №16 17. Убедитесь в том, что, войдя в лабиринт, изображенный на рисунке, можно, касаясь правой рукой стены, дойти до центра и вернуться (рисунок 11). 18. Убедитесь, что из любой точки лабиринта в его центр можно попасть, пользуясь правилом одной руки (рисунок 11). 19.На квадратной клумбе размером 4 на 4 метра выращено 16 кустов георгинов. Расстояние между кустами составляло один метр. Пока кусты не распустились, садовник обходил их по самому короткому пути, а когда они распустились – по самому длинному. Как выглядели самый короткий и самый длинный путь (рисунок 13)? 44

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Рисунок 13- Рисунок к задаче №19 Решение: Самый короткий путь:1, 2, 3, 4, 8, 7, 6, 5, 9, 10, 11, 12, 16, 15, 14, 13. Самый длинный путь: 5, 9, 13, 10, 7, 4, 3, 2, 1, 6, 11, 16, 12, 8, 15, 14. 20.Пройдите лабиринт от входа, расположенного у верхнего правого угла, до выхода, расположенного в нижнем правом углу (рисунок 14). Решение: (рисунок 15). Рисунок 14- Рисунок к задаче №20 Рисунок 15 – Решение задачи №20 45

21. Пройдите лабиринт сверху донизу, ни разу не пересекая собственную дорогу, при этом собирая числа таким образом, чтобы в сумме они давали двадцать (рисунок 16). Решение: (рисунок 16). Рисунок 16 – Рисунок к задаче №21 Рисунок 16 – Решение задачи №21 Задачи к занятию №4 2 2 . Шесть школьников участвуют в шахматном турнире, который проводится в один круг. Докажите, что всегда среди них найдутся три участника турнира, которые провели уже все встречи между собой, либо еще не сыграли друг с другом ни одной партии. Р е ш е н и е . Любые два участника турнира находятся между собой непременно в одном из двух отношений: они либо уже сыграли между собой партию, либо еще не сыграли. Каждому участнику поставим в соответствие вершину графа. Соединим вершины попарно рёбрами двух цветов. Пусть ребро красного цвета означает, что двое уже сыграли между собой, а синего - что не сыграли. Мы получили граф с шестью 46

вершинами и рёбрами двух цветов. Теперь для решения задачи достаточно доказать, что в таком графе обязательно найдется "треугольник" с одноцветными сторонами. Заметим, что из произвольной вершины нашего графа к пяти остальным непременно выйдут, по меньшей мере, три ребра одного цвета (докажите это). Пусть, например, из вершины A выходят три ребра красного цвета (рисунок 17). Какого цвета рёбра могут соединять вершины B, C и D? Если хотя бы одно из них окажется красным, как на рисунке 18, то получится треугольник с красными сторонами. Если же все эти ребра синие, как на рисунке 19, то они образуют треугольник с синими сторонами. Задача полностью решена. Кроме того, при ее решении доказаны первые два свойства. Рисунок 17 Рисунок 18 Рисунок 19 2 3 . На географической карте выбраны пять городов. Известно, что из любых трех из них найдутся два, соединенные авиалиниями, и два - не соединенные. Докажите, что тогда: 1. Каждый город соединен авиалиниями с двумя и только с двумя другими городами. 2. Вылетев из любого города, можно облететь пять остальных городов, побывав в каждом по одному разу, и вернуться назад. Р е ш е н и е . Каждые два города находятся в одном из двух отношений - они либо соединены между собой авиалиниями, либо не соединены. Пусть вершины графа соответствуют городам, красное ребро - наличию авиалинии, синее - отсутствию. По условию, среди трех рёбер, соединяющих любые три вершины, одно ребро красное, второе - синее, а это означает, что в графе нет ни одного треугольника с одноцветными сторонами. Остается показать, что в графе с пятью вершинами и рёбрами двух цветов каждая вершина принадлежит двум красным и двум синим ребрам, причем, красные ребра образуют замкнутую линию, проходящую через каждую вершину только один раз, или иначе, что в таком графе найдется "пятиугольник", все стороны которого красные, а все диагонали - синие. 47

Ясно, что из каждой вершины графа выходят два красных ребра и два синих, поскольку в противном случае образовался бы треугольник с одноцветными сторонами. Следовательно, каждый город соединен авиалиниями с двумя и только с двумя городами. Теперь выберем одну из вершин, например A, а красными будут, скажем, рёбра АВ и АС (рисунок 20). Ребро СВ не может быть красным, следовательно, красным является одно из ребер либо CD, либо CE. Пусть красное - CD. Если теперь соединить красным ребром вершины B и D, то вершина E должна быть соединена красными ребрами с вершинами, которые принадлежат уже двум красным ребрам. По условию это невозможно. Остается соединить красными рёбрами вершины D и E, B и E. Остальные ребра должны быть синими (рисунок 20). Рисунок 20 – Рисунок к задаче 23 Вместе с решением задачи получено 3 свойство графа. 2 4 . В течение дня два из шести телефонных абонентов могут поговорить друг с другом по телефону, а могут и не поговорить. Докажите, что всегда можно найти две тройки абонентов, в каждой из которых либо все переговорили друг с другом, либо все не переговорили. Р е ш е н и е . Пусть у графа с шестью вершинами A, B, C, D, E, F красные рёбра соответствуют парам абонентов, которые говорили друг с другом по телефону, синие тем, кто не говорил. Тогда найдется хотя бы один треугольник с одноцветными сторонами, например, треугольник ABF с красными сторонами. Временно исключим из рассмотрения одну из его вершин, скажем A, вместе с выходящими из нее ребрами. Найдется ли в оставшемся графе с пятью вершинами треугольник с одноцветными сторонами? Если найдется, то он содержится и в исходном графе. В противном случае получаем пятиугольник с красными сторонами и синими диагоналями (рис. 6). Теперь восстановим шестую вершину A с ее ребрами. Ребра AF и AB - красные. Если ребро AE 48

или AC будет тоже красным, то образуется еще хотя бы один треугольник с красными сторонами AEF или ABC. Если оба эти рёбра будут синего цвета, то появится треугольник АСЕ с синими сторонами. Установлено 4 свойство графа с цветными рёбрами. 2 5 . Назовем группу людей "однородной", если любые два человека из этой группы знакомы, или, напротив, не знакомы. Докажите, что среди восьми случайно встретившихся людей всегда найдутся две однородные группы, состоящие из трех человек каждая, причем, никто из первой группы не входит во вторую.Иначе говоря, требуется доказать, что в графе с восемью вершинами и рёбрами двух цветов всегда найдутся два не сцепленных треугольника с одноцветными сторонами. Р е ш е н и е . Рассмотрим в графе один из треугольников, например KLM, с одноцветными сторонами. Если остальные пять вершин и ребра, соединяющие их попарно, содержат треугольник с одноцветными сторонами, то он и будет являться вторым искомым треугольником. Если остальные пять вершин A, B, C, D, E не содержат треугольника с одноцветными сторонами, то они образуют пятиугольник с красными сторонами и синими диагоналями (свойство 3). На рисунке 20 изображены не все рёбра графа, а лишь треугольник KLM с красными сторонами и пятиугольник ABCDE с красными сторонами и синими диагоналями. Покажем, что если какая-нибудь вершина треугольника KLM соединена синими рёбрами с двумя вершинами пятиугольника, взятыми через одну, например, K с A и C (рисунок 21), то найдется еще один треугольник с одноцветными сторонами, не сцепленный с треугольником АСК. Действительно, посмотрим на пятиугольник BDELM. Ясно, что невозможно окрасить рёбра BL и ВМ так, чтобы он превратился в пятиугольник с красными сторонами и синими диагоналями. Поэтому он обязательно содержит одноцветный треугольник, не сцепленный с треугольником АСК (рисунок 22). Рисунок 21 Рисунок 22 49 Рисунок 23

Остается рассмотреть случай, когда каждая вершина треугольника KLM соединена красными ребрами, по меньшей мере, с тремя последовательными вершинами пятиугольника ABCDE. Пусть, например, вершина K соединена красными рёбрами с вершинами A, B и C. Тогда вершины L и M соединены красными рёбрами с A, B и C. В противном случае найдутся два несцепленных треугольника с вершинами K, L или M и основаниями - сторонами пятиугольника ABCDE. Но тогда мы находим два треугольника CLM и АВК с красными сторонами. Таким образом, во всех случаях найдутся два несцепленных треугольника с одноцветными сторонами (рисунок 23). 2 6 . Каждый из 17 ученых переписывается с остальными. В их переписке речь идет о трёх темах. Каждая пара ученых переписывается друг с другом лишь по одной теме. Докажите, что не менее трёх ученых переписываются друг с другом по одной и той же теме. Р е ш е н и е . Условиям задачи соответствует граф с семнадцатью вершинами и рёбрами трех цветов. Из каждой его вершины выходят 16 рёбер, причем, всегда не менее шести одного цвета. (Доказать это нетрудно.) Если противоположные концы хотя бы двух из них соединены ребром того же цвета, то образуется треугольник с одноцветными сторонами. Если нет, то 6 вершин будут соединены попарно рёбрами не более чем двух цветов, а тогда, как мы уже знаем, в этом графе с шестью вершинами найдется треугольник с одноцветными сторонами. Задачи к занятию №4 для самостоятельного решения 27. На одном из фестивалей встретились 6 делегатов. Оказалось, что из любых троих по меньшей мере двое могут объясниться друг с другом. Докажите, что найдутся три делегата, которые могут объясниться друг с другом. Решение.Пусть красное ребро означает, что два делегата могут объясниться на одном языке, а синее - что не могут. Если красного треугольника нет, то по свойству 2 должен быть треугольник с синими сторонами. Но это противоречит условию. 28.В трехмерном пространстве 9 точек размещены так, что никакие три не лежат на одной прямой. Каждая точка соединена отрезками прямых в точности с четырьмя другими. Докажите, что всегда найдется хотя бы один треугольник с вершинами в этих точках. Решение. Проведённому отрезку поставим в соответствие красное ребро, не проведенному - синее. Докажем, что в полном графе с девятью вершинами, каждая из которых принадлежит четырем красным ребрам и четырем синим, найдется треугольник с красными сторонами.

Рисунок 24 – Рисунок к задаче №28 Предположим, что нет красного треугольника. Пусть какая-нибудь вершина A соединена красными рёбрами с B 1 , B 2 , B 3 и B 4 , синими - с C 1 , C 2 , C 3 и C 4 . Рёбра вида B i B j - синие (рисунок 24). Каждая из B i соединена тремя красными рёбрами с вершинами C j .Два красных ребра связывают вершины вида C между собой (поскольку красных рёбер B i C j двенадцать). Пусть B i связана красными рёбрами с C 1 C 2 , и C 3 . Между собой C 1 C 2 , и C 3 соединены синими рёбрами, иначе образовался бы треугольник с красными сторонами (рисунок 25). Рисунок 25 – Рисунок к задаче №28 Тогда C 4 принадлежит двум красным ребрам вида. C 4 C i , например, C 4 C 3 и C 4 C 2 . Но C 4 принадлежит еще двум красным ребрам. Одно из них, - например, C 4 B 2 (рисунок 26). Хотя бы одно из ребер B 2 C 2 и B 2 C 3 - тоже красное, то есть хотя бы один из треугольников B 2 C 3 C 4 и B 2 C 2 C 4 имеет красные стороны. 51

Рисунок 26 – Рисунок к задаче №28 29.В работе международного симпозиума лингвистов участвуют n человек. Из любых четырех хотя бы один может объясниться с каждым из оставшихся трех участников хотя бы на одном языке. Докажите, что найдется участник симпозиума, который может объясниться с каждым из остальных участников. Решение.Имеем полный граф с n вершинами и ребрами двух цветов (синее ребро двое могут объясниться на каком-нибудь языке, красное - не могут). По условию, среди любых четырех вершин графа всегда найдется, по меньшей мере, одна, синяя степень которой равна трем. Случай, когда все ребра синие, тривиален. Пусть найдется красное ребро AB. Добавим еще какие-нибудь две вершины C и D. Из четырех вершин A, B, C и и найдется хотя бы одна, синяя степень которой равна трем. Это - C или D. Пусть, например, синюю степень три имеет C. Добавим еще одну вершину - E. Из вершин A, B, C, E или C или E имеет синюю степень, равную трем. В обоих случаях C соединена синим ребром с E. Так переберем все вершины. В итоге окажется, что C соединена синими рёбрами со всеми вершинами графа. Во всякой четверке вершин, включающей A и B, есть вершина, соединенная синими ребрами со всеми остальными вершинами графа. Отсюда, кроме A и B существует, самое большее, одна вершина, не соединенная синими рёбрами со всеми остальными. 30. В городе n жителей. Любые двое из них либо дружат, либо враждуют. Каждый день не более чем один из них может начать новую жизнь: поссориться со всеми друзьями и подружиться со всеми врагами. Известно, что любые три жителя могут подружиться. Доказать, что все жители могут подружиться. Решение. Каждому жителю поставим в соответствие вершину графа. Пусть синее ребро означает, что двое дружат, а красное - что не дружат. Получим граф с n вершинами и рёбрами двух цветов, который можно подвергать следующим преобразованиям: 52

выбирать вершину и все красные ребра, которым она принадлежит, перекрашивать в синие, а все синие - в красные. По условию, каждый треугольник может стать синим, то есть в графе могут быть только или треугольники с синими сторонами, или треугольники, у которых одна сторона - синяя и две - красные. В любом таком графе найдется вершина, красная степень которой больше синей её степени. Если каждый раз выбирать в графе вершину с наибольшей красной степенью и перекрашивать ребра, которым она принадлежит, то с каждым шагом число синих рёбер будет увеличиваться. Число рёбер в графе с n вершинами конечно, поэтому через конечное число шагов все рёбра графа станут синими. Задачи к занятию №5 31.Встретились три подруги: Белова, Краснова и Чернова. На одной из них было надето черное платье, на другой – красное, а на третьей белое. Девочка в красном платье говорит Черновой: « Нам надо поменяться платьями, а то цвет наших платьев не соответствует нашим фамилиям». Кто из девочек в какое платье был одет? Решение. Здесь мы имеем два равночисленных множества: множество фамилий и множество цветов платьев. Между этими множествами надо установить взаимнооднозначное соответствие. Для этого построим граф. Пусть белые кружочки Б, К и Ч изображают элементы первого множества (Белова, Краснова и Чернова), а черные кружочки б, к и ч – элементы второго множества – белое, красное и чёрное. Условимся соединять эти кружочки тонкой линией, если между ними нет соответствия. Если же соответствие между кружочками установлено правильно, то будем соединять их жирной линией. Следовательно, Белова одета в чёрное платье, Чернова одета в красное платье и Краснова – в белое платье. 32. Несколько мальчиков встретились на вокзале, чтобы поехать за город в лес. При встрече все они поздоровались друг с другом за руку. Сколько мальчиков поехало за город, если всего было 10 рукопожатий? Решение. Будем решать эту задачу графически. Вначале отметим точки А и В и соединим их отрезком. Точками будем изображать мальчиков, а отрезок будет означать рукопожатие. Добавим еще одну точку С и соединим её с точками А и В. Всего получается три отрезка (рисунок 27). 53

Рисунок 27 – Рисунок к задаче № 32 Отметим следующую точку Д и соединим её отрезками с тремя точками А, В и С. Теперь уже получилось шесть отрезков. Наконец, отметим пятую точку Е и соединим её со всеми точками, отмеченными ранее. Получилось 10 отрезков, т. е 10 рукопожатий. Значит, на вокзале встретились 5 мальчиков. 33.Между 9 планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля–Меркурий, Плутон–Венера, Земля–Плутон, Плутон–Меркурий, Меркурий–Венера, Уран–Нептун, Нептун–Сатурн, Сатурн–Юпитер, Юпитер–Марс и Марс–Уран. Можно ли добраться с Земли до Марса? Решение. Нарисуем граф, где вершины – это планеты, а рёбра – это маршруты (рисунок 28). Рисунок 28 – Рисунок к задаче № 33 Теперь видно, что долететь от Земли до Марса нельзя. 34. Петя, Гена, Дима и Вова занимаются в детской спортивной школе в разных секциях: гимнастической, баскетбольной, волейбольной и легкой атлетики. Петя, Дима и волейболист учатся в одном классе. Петя и Гена на тренировки ходят пешком вместе, а гимнаст ездит на автобусе. Легкоатлет не знаком ни с баскетболистом, ни с волейболистом. Кто из мальчиков в какой секции занимается? 54

Решение.Петя – баскетболист, Гена – волейболист, Дима – гимнаст, а Вова – легкоатлет (рисунок 29). Рисунок 29 – Рисунок к задаче № 34 Ответ: Витя знаком с Серёжей и Колей, Серёжа знаком с Витей и сПете, Петя знаком с Серёжей и с Максимом, Максим знаком сПете и с Колей, Коля знаком с Петей и с Витей. 35.Марина, Лариса, Жанна и Катя, умеют играть на разных инструментах (пианино, виолончели, гитаре, скрипке), но только каждая на одном. Они же знают иностранные языки (английский, французский, немецкий, испанский), но каждая только один (рисунок 30). Известно: 1) девушка, которая играет на гитаре, говорит по-испански; 2) Лариса не играет ни на скрипке, ни на виолончели и на знает английского языка; 3) Марина не играет ни на скрипке, ни на виолончели и на знает ни немецкого, ни английского языка; 4) девушка, которая говорит по-немецки, не играет на виолончели; 5) Жанна знает французский язык, но не играет на скрипке. Кто на каком инструменте играет и какой иностранный язык знает? 55

Рисунок 30 – Рисунок к задаче № 35 Решение. Из пятого условия, что Жанна знает французский язык, рисуем стрелку. Из третьего условия, что Марина не знает ни немецкого, ни английского, а французский знает Жанна, то Марина знает испанский и рассматривая первое условие она играет на гитаре. Из условия N2 видим, что Лариса играет на пианино, т.к. Марина играет на гитаре, а на других инструментах она играть не умеет, и значит, она говорит по-немецки (рисунок 31). Рисунок 31 – Решение задачи № 35 Т.к. Жанна не играет на скрипке, то остается один инструмент, на котором она может играть это виолончель. Тогда Катя играет на скрипке, и знает английский язык (рисунок 35). 36. Три друга: Алёша, Боря и Витя – учатся в одном классе. Один из них ездит домой из школы на автобусе, один – на трамвае и один – на троллейбусе. Однажды после уроков 56

Алёша пошёл проводить своего друга до остановки автобуса. Когда мимо них проходил троллейбус, третий друг крикнул из окна: «Боря, ты забыл в школе тетрадку!» Кто на чем ездит домой? Ответ: Алёша в трамвае, Боря в автобусе, Витя на троллейбусе. 37.Клоуны Бам, Бим, Бом вышли на арену в красной, синей и зеленой рубашках. Их туфли тоже были этих трёх цветов. Туфли и рубашка Бима были одного цвета. На Боме не было ничего красного. Туфли Бама были синие, а рубашка нет. Каких цветов были туфли и рубашка у Бома и Бима? Решение: Красные туфли, красная рубашка - Бам Синие туфли, синяя рубашка - Бим Зеленые туфли, зеленая рубашка - Бом Ответ: Бом – синяя рубашка и зелёные туфли, Бам – зелёная рубашка и синие туфли. 38. В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что вода и молоко не в бутылке, сосуд с лимонадом стоит между кувшином и сосудом с квасом, в банке не лимонад и не вода. Стакан стоит около банки и сосуда с молоком. В какой сосуд налита каждая жидкость? Ответ: Молоко – в кувшине, лимонад – в бутылке, квас – в банке, вода – в стакане. Темы творческих работ: 1.Графы в головоломках. 2. Графы и игры на шахматной доске. 3. Геометрическая задача о лабиринтах. 4. Графы и подсчет числа изомеров. 5. Графы в генетике. 6. Расчет сетевых графиков. 7. Графы и транспортные сети. 8. Графы в электротехнике. 9. Графы в психологии. 10. Проблема четырех красок. 11. Графы в физике. 12. Графы с цветными рёбрами. 57

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв