Элективный курс Применение теории графов для решения логических задач

ЭЛЕКТИВНЫЙ КУРС «ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ К РЕШЕНИЮ ЛОГИЧЕСКИХ ЗАДАЧ».

1.1. МЕСТО И РОЛЬ ЭЛЕКТИВНОГО КУРСА В ОБУЧЕНИИ МАТЕМАТИКЕ.

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

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

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

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

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

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

Основные требования, предъявляемые к элективным курсам:

1.Их многообразие (направлений должно быть много);

2.Кратковременность (от 6 до 16 часов);

3.Оригинальность названия и содержания;

4.Нестандартизированность курса;

5.Окончание курса должно быть отмечено какой-либо работой (проект, творческое сочинение, реферат и т.п.);

6.Проект элективного курса может разрабатывать непосредственно педагог.

Успешный элективный курс отвечает следующим критериям:

1.Содержание программы курса достаточно актуально в современном мире;

2.Мотивационный потенциал курса находится на высоком уровне;

3.Содержание курса соответствует поставленным целям и имеет логическое построение.

1.2.ЭЛЕКТИВНЫЙ КУРС «ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ К РЕШЕНИЮ ЛОГИЧЕСКИХ ЗАДАЧ».

Данный элективный курс представлен для учащихся 9-ых классов.

1.2.1.Пояснительная записка

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

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

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

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

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

Настоящий элективный курс должен решать следующие задачи:

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

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

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

-повышение интереса к математики в целом;

-привитие навыков работы с научно-популярной литературой;

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

-воспитание усидчивости, настойчивости в достижении цели;

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

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

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

• учебно-организационные;

• учебно-интеллектуальные;

• учебно-коммуникативные;

• учебно-информационные.

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

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

Элективный курс состоит из 5 тем:

- Первое знакомство с графами;

-Одним росчерком пера;

- Путешествия по лабиринтам;

- Графы с цветными ребрами и их свойства;

-Графы и логические задачи.

Курс рассчитан на 12 часов. Из расчета 2 часа в неделю курс будет продолжаться примерно одну четверть. При завершении курса состоится конференция по защите творческих работ.

Программа располагает к самостоятельному поиску и самоопределению в выборе профиля обучения.

Формы работы и итоговый контроль

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

Учебно-тематическое планирование

№ п/п

Тема занятия

Кол-во часов

Форма проведения занятия

Форма контроля.

1.

Введение. Первое знакомство с графами.

2

Лекция - беседа

Решение задач.

2.

Одним росчерком пера.

2

Лекция-беседа. Практическая работа.

Решение задач. С/р.

3.

Путешествия по лабиринтам.

2

Сообщения учащихся. Беседа. Практическая работа.

Поисковые задания. Практическая работа.

4.

Графы с цветными ребрами и их свойства.

2

Сообщения учащихся. Беседа.Практикум по решению задач.

Сообщение по теме. Исследовательские задания.

5.

Графы и логические задачи.

2

Практикум по решению задач.

Творческие задания.Решение задач. С/р.

6.

Зачетный урок.

2

Урок-конференция.

Защита исследовательских работ. Выставка работ.

1.3 СОДЕРЖАНИЕ ЭЛЕКТИВНОГО КУРСА

1.3.1.Содержание занятия №1.

«Введение. Первое знакомство с графами».

Годом зарождения теории графов можно считать 1736-й, когда швейцарский математик Леонард Эйлер опубликовал в Санкт-Петербургской Академии наук работу, посвящённую семи мостам города Кёнигсберга (нынешний Калининград). Загадка о том, как пройти по всем мостам ровно однажды, была известна горожанам с тех пор, как все семь мостов были построены, т.е. с XVI века; математик же разработал её формализацию и доказал, что она не имеет решения (эту задачу мы рассмотрим на следующем занятии).

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

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

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

Задача: Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями. Сколько всего рукопожатий было сделано?
Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени (рис.2), а производимому рукопожатию - отрезок или часть кривой, соединяющая конкретные точки - имена (рис. 3).

Пустой граф с пятью вершинами

Неполный граф с пятью вершинами

Точки А, Б, В, Г, Д называются вершинами графа, а отрезки линий, соединяющие эти точки - ребрами графа. При изображении графов на рисунках или схемах отрезки могут быть прямолинейными или криволинейными; Длины отрезков и расположение точек произвольны.
Например, все три фигуры на рисунке изображают один и тот же граф.

Рассмотрим процесс соединения точек А, Б, В, Г, Д ребрами.
1. Ситуация, соответствующая моменту, когда рукопожатия еще не совершались, представляет собой точечную схему, изображенную на рисунке2. Такая схема, состоящая из «изолированных» вершин, называется пустым графом.
2. Ситуация, когда совершены еще не все рукопожатия, может схематически быть изображена, например, с помощью рисунка З: пожали руки А и Б, А и Г, Д и Г, В и Д. Следующий момент, когда добавятся, например, пожатия рук А и В, Г и Б, попробуйте изобразить сами.
Графы, в которых не построены все возможные ребра, называются неполными графами.
3. На рисунке 4 изображен граф, соответствующий всем совершенным рукопожатиям. Этот граф является полным графом.

Полный граф с пятью вершинами

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

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

Например, степень вершины А на рис.4 равна 4, т.е. является четной, а степень вершины В на рис.3 равна 1, т.е. является нечетной.
Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2.

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

Задачи.

1. Нарисуйте полный граф с n вершинами, если:

n=2, n=3, n=5.

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 вершинами, две из которых имеют одинаковую степень.

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

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

Ответ: Соединить телефоны таким образом невозможно.

1.3.2.Методические рекомендации к занятию № 1.

Форма проведения первого занятия лекция-беседа, т.к. это занятие вводное, ознакомительное. Данное занятие рассчитано на два часа. Для него понадобится мультимедийное оборудование, а именно компьютер, проектор. К занятию учителю рекомендуется подготовить презентацию, чтобы повысить интерес к данному элективному курсу. Также презентацию рекомендуется использовать для наглядности к каждому занятию данного элективного курса. Здесь мы будем пользоваться активными и интерактивными методами обучения: беседа с учениками (учитель задаёт вопросы ученикам, а они учителю), творческие задания; работа в микро-группах.

Сначала необходимо дать информацию о том, как будет проходить элективный курс, какие цели перед нами стоят. Следует объяснить ученикам, как будет проходить итоговая отчетность. Далее учитель расскажет немного из истории графов, о том, как зародилась теория графов, в каких сферах деятельности применяется эта теория, и для чего она понадобится нам. Это поможет привить интерес к данному элективному курсу и к изучению теории графов в дальнейшем. Затем учитель вместе с учениками формулирует основные понятия теории графов (понятия формулируются в ходе решения задачи). При решении данной задачи ученики сами предлагают свои варианты решения, так же ученики могут сами сформулировать некоторые понятия, например, понятие пустого графа, полного, неполного. Ученики могут предположить, что является степенью вершины и выявить закономерность между количеством вершин и ребер в полном графе. Далее предлагаются задачи для закрепления полученных знаний. Задачи №1, 2 можно дать для самостоятельного решения. После того как все решат можно вызвать 2-3 ученика к доске (для каждой задачи), для того чтобы они изобразили полученные графы. Ребята увидят, что изображения графов у всех различно и это не является ошибкой. Задачи №3,4 учитель может также предложить решить самостоятельно, но уже без проверки решения у доски. Задачи №5,6 решаем с вызовом учеников к доске. Для решения задачи №7 можно разделить учеников на микрогруппы по 3-4 человека, и та группа, которая решит задачу быстрее всех получат «5».

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

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

1.3.3.Содержание занятия №2.

«Одним росчерком пера».

Учитель предлагает детям решить задачу о Кенигсбергских мостах.

Схема мостов и соответствующий ей граф

Буква Л обозначает левый берег, П - правый, А и Б - острова.

Дети должны попробовать пройти через каждый мост ровно 1 раз и убедиться, что задача не имеет решения.

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

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

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

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

рис.1

Задачи.

1. Начертить граф с вершинами (1,2,3,4,5) и ребрами (1,2), (2,3), (3,4), (3,1), (4,5), является ли этот граф эйлеровым?

Ответ: да, это эйлеров граф.

2. Начертить граф с вершинами (А, Б, В, Г) и ребрами (А,Г), (А,Б), (Б,В), является ли этот граф эйлеровым?

Ответ: да, это эйлеров граф.

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

Математическая игра: Усадьба Хакенбуш.

Эту игру придумал математик Джон Конвей. Для игры используется картинка с "усадьбой Хакенбуш". А именно: картинка должна быть в рамке; все ее элементы должны быть связаны с рамкой; все соединения линий ограничиваются точками.
За один ход игрок стирает один любой отрезок картинки, ограниченный точками или одной точкой, если отрезок это петля.
Если после удаление этой линии, часть линий оказывается не связанной с рамкой, то она удалятся тоже.
На рисунке пример, где удалятся линия, выделенная зеленым цветом, и вместе с ней удаляются линии дыма, выделенные красным.
Игрок, который удаляет последний элемент картинки выигрывает.

Подведём итоги:

• Если все вершины графа четные, граф можно начертить одним росчерком. Порядок движения любой.

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

• Граф с более чем двумя нечетными вершинами нельзя начертить одним росчерком.

1.3.4.Методические рекомендации к занятию № 2.

В начале данного занятия дети будут решать задачи на карточках, составленные ими дома. На это можно отвести 15 минут. Затем учитель соберет карточки.

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

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

1.3.5.Содержание занятия №3.

«Путешествия по лабиринтам».

Лекция вдвоём (примерное содержание сообщения учеников).

Происхождение задач о лабиринтах относится к глубокой древности и теряется во мраке времен.

Слово «лабиринт» (греческое) означает «ходы в подземельях».

Возможен ли безвыходный лабиринт?

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

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

Геометрическая постановка задачи о лабиринтах

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

Решение задачи о лабиринтах

Правило 1. Отправляемся от выбранной вершины (первого перекрестка) и идем по любому ребру, пока не приходим или в тупик (к вершине), или к новому перекрестку (вершине).

Тогда:

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

2. Если приходим к новому перекрестку, то направляемся по новому произвольному ребру, не забывая всякий раз отмечать путь, по которому прибыли, и путь, по которому отправились дальше. Как показано на рисунке.

Пример.

Направление движения показано стрелкой . После прихода к пересечению путей выбирается направление, обозначенное стрелкой . Оба пути помечаются черточкой. (Крестиками обозначаются черточки, поставленные при последнем прохождении через перекресток.)

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

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

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

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

Правило 4. - ПРАВИЛО ОДНОЙ РУКИ. Оно состоит в том, что по лабиринту надо двигаться, не отрывая одной руки (правой или левой) от стены.

Задачи (для с/р).

1. Нарисуйте граф, соответствующий данному лабиринту.

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

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

4. Как можно достать из муравейника зернышко.

5.Это лабиринт английского короля Вильгельма III, состоит из аллей и изгородей. Нужно пройти в центр к деревьям и скамейкам под ними. Найдите путь к беседке, расположенной в парке.

1.3.6.Методические рекомендации к занятию № 3.

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

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

Список литературы к занятию №3.

1. Ттат У. Тоерия графов: пер. с англ. - М.: Мир, 1998.

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

3. Зыков А.А. Основы теории графов. - М.: Вузовская книга, 1987.

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

1.3.7.Содержание занятия №4.

«Графы с цветными ребрами».

Урок конференция (примерное сообщение учеников).

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

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

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

Перейдем теперь к решению задач.

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

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

Заметим, что из произвольной вершины нашего графа к пяти остальным непременно выйдут по меньшей мере три ребра одного цвета (докажите это). Пусть, например, из вершины A выходят три ребра красного цвета (рис.2) Какого цвета ребра могут соединять вершины B, C и D)? Если хотя бы одно из них окажется красным, как на рисунке 3, то получится треугольник с красными сторонами. Если же все эти ребра синие, как на рисунке 4, то они образуют треугольник с синими сторонами.

Задача полностью решена. Кроме того, при ее решении доказаны два свойства.

Свойство 1. Из любой вершины графа с шестью или более вершинами и ребрами двух цветов выходит, по меньшей мере, три ребра одного цвета.

Свойство 2. В любом графе с шестью или более вершинами и ребрами двух цветов найдется по меньшей мере один треугольник с одноцветными сторонами.

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

1. Каждый город соединен авиалиниями с двумя и только с двумя другими городами.

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

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

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

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

Теперь выберем одну из вершин, например A, а красными будут, скажем, ребра АВ и АС (рис. 5). Ребро СВ не может быть красным, следовательно, красным является одно из ребер либо CD, либо CE. Пусть красное - CD. Если теперь соединить красным ребром вершины B и D, то вершина E должна быть соединена красными ребрами с вершинами, которые принадлежат уже двум красным ребрам. По условию это невозможно. Остается соединить красными ребрами вершины D и E, B и E. Остальные ребра должны быть синими (рис. 1а).

Вместе с решением задачи получено еще одно свойство графа.

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

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

Решение. Пусть у графа с шестью вершинами A, B, C, D, E, F красные ребра соответствуют парам абонентов, которые говорили друг с другом по телефону, синие - тем, кто не говорил. Тогда найдется хотя бы один треугольник с одноцветными сторонами, например, треугольник ABF с красными сторонами. Временно исключим из рассмотрения одну из его вершин, скажем A, вместе с выходящими из нее ребрами. Найдется ли в оставшемся графе с пятью вершинами треугольник с одноцветными сторонами? Если найдется, то он содержится и в исходном графе. В противном случае получаем пятиугольник с красными сторонами и синими диагоналями (рис. 6). Теперь восстановим шестую вершину A с ее ребрами. Ребра AF и AB - красные. Если ребро AE или AC будет тоже красным, то образуется еще хотя бы один треугольник с красными сторонами AEF или ABC. Если оба эти ребра будут синего цвета, то появится треугольник АСЕ с синими сторонами.

Установлено свойство графа, являющееся обобщением свойства 2.

Свойство 4. В любом графе с шестью или более вершинами и ребрами двух цветов всегда найдутся два треугольника с одноцветными сторонами. Эти два треугольника могут иметь общую вершину или даже общее ребро.

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

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

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

Решение. Рассмотрим в графе один из треугольников, например KLM, с одноцветными сторонами. Если остальные пять вершин и ребра, соединяющие их попарно, содержат треугольник с одноцветными сторонами, то он и будет являться вторым искомым треугольником. Если остальные пять вершин A, B, C, D, E не содержат треугольника с одноцветными сторонами, то они образуют пятиугольник с красными сторонами и синими диагоналями (свойство 3). На рисунке 7 изображены не все ребра графа, а лишь треугольник KLM с красными сторонами и пятиугольник ABCDE с красными сторонами и синими диагоналями. Покажем, что если какая-нибудь вершина треугольника KLM соединена синими ребрами с двумя вершинами пятиугольника, взятыми через одну, например, K с A и C (рис. 8), то найдется еще один треугольник с одноцветными сторонами, не сцепленный с треугольником АСК. Действительно, посмотрим на пятиугольник BDELM. Ясно, что невозможно окрасить ребра BL и ВМ так, чтобы он превратился в пятиугольник с красными сторонами и синими диагоналями. Поэтому он обязательно содержит одноцветный треугольник, не сцепленный с треугольником АСК (рис. 9).

Остается рассмотреть случай, когда каждая вершина треугольника KLM соединена красными ребрами по меньшей мере с тремя последовательными вершинами пятиугольника ABCDE. Пусть, например, вершина K соединена красными ребрами с вершинами A, B и C. Тогда вершины L и M соединены красными ребрами с A, B и C. В противном случае найдутся два несцепленных треугольника с вершинами K, L или M и основаниями - сторонами пятиугольника ABCDE. Но тогда (см. рис. 10) мы находим два треугольника CLM и АВК с красными сторонами. Таким образом, во всех случаях найдутся два несцепленных треугольника с одноцветными сторонами.

Решим теперь задачу, предложенную на Шестой международной математической олимпиаде.

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

Решение. Условиям задачи соответствует граф с семнадцатью вершинами и ребрами трех цветов. Из каждой его вершины выходят 16 ребер, причем, всегда не менее шести одного цвета. (Доказать это нетрудно.) Если противоположные концы хотя бы двух из них соединены ребром того же цвета, то образуется треугольник с одноцветными сторонами. Если нет, то 6 вершин будут соединены попарно ребрами не более чем двух цветов, а тогда, как мы уже знаем (см. задачу 1), в этом графе с шестью вершинами найдется треугольник с одноцветными сторонами.

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

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

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

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

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

5. В городе n жителей. Любые двое из них либо дружат, либо враждуют. Каждый день не более чем один из них может начать новую жизнь: поссориться со всеми друзьями и подружиться со всеми врагами. Известно, что любые три жителя могут подружиться. Доказать, что все жители могут подружиться.

Решения.

1. Пусть красное ребро означает, что два делегата могут объясниться на одном языке, а синее - что не могут. Если красного треугольника нет, то по свойству 2 должен быть треугольник с синими сторонами. Но это противоречит условию.

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

Предположим, что нет красного треугольника. Пусть какая-нибудь вершина A соединена красными ребрами с B₁, B₂, B₃ и B₄, синими - с C₁, C₂, C₃ и C₄. Ребра вида B_iB_j - синие (рис. 1). Каждая из B_i соединена тремя красными ребрами с вершинами C_j, Два красных ребра связывают вершины вида C между собой (поскольку красных ребер B_iC_j - двенадцать). Пусть B_i связана красными ребрами с C₁ C₂, и C₃. Между собой C₁ C₂, и C₃ соединены синими ребрами, иначе образовался бы треугольник с красными сторонами (рис. 2).

Тогда C₄ принадлежит двум красным ребрам вида. C₄C_i, например, C₄C₃ и C₄C₂. Но C₄ принадлежит еще двум красным ребрам. Одно из них, - например, C₄B₂ (рис. 3). Хотя бы одно из ребер B₂C₂ и B₂C₃ - тоже красное, то есть хотя бы один из треугольников B₂C₃C₄ и B₂C₂C₄ имеет красные стороны.

3. Имеем полный граф с n вершинами и ребрами двух цветов (синее ребро - двое могут объясниться на каком-нибудь языке, красное - не могут). По условию, среди любых четырех вершин графа всегда найдется, по меньшей мере, одна, синяя степень которой равна трем.

Случай, когда все ребра синие, тривиален. Пусть найдется красное ребро AB. Добавим еще какие-нибудь две вершины C и D. Из четырех вершин A, B, C и и найдется хотя бы одна, синяя степень которой равна трем. Это - C или D. Пусть, например, синюю степень три имеет C. Добавим еще одну вершину - E. Из вершин A, B, C, E или C или E имеет синюю степень, равную трем. В обоих случаях C соединена синим ребром с E. Так переберем все вершины. В итоге окажется, что C соединена синими ребрами со всеми вершинами графа. Во всякой четверке вершин, включающей A и B, есть вершина, соединенная синими ребрами со всеми остальными вершинами графа. Отсюда, кроме A и B существует, самое большее, одна вершина, не соединенная синими ребрами со всеми остальными.

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

Рассмотрим некоторое красное ребро АВ. Пусть синяя степень вершины A равна k.

Предположим, что k >= n/2. Легко видеть, что B соединена красными ребрами с теми вершинами, с которыми A соединена синими ребрами. Поэтому, если красная степень вершины B равна l, то l = k + 1 > k >= n/2.

5. Каждому жителю поставим в соответствие вершину графа. Пусть синее ребро означает, что двое дружат, а красное - что не дружат. Получим граф с n вершинами и ребрами двух цветов, который можно подвергать следующим преобразованиям: выбирать вершину и все красные ребра, которым она принадлежит, перекрашивать в синие, а все синие - в красные. По условию, каждый треугольник может стать синим, то есть в графе могут быть только или треугольники с синими сторонами, или треугольники, у которых одна сторона - синяя и две - красные. В любом таком графе найдется вершина, красная степень которой больше синей ее степени (см. задачу 4). Если каждый раз выбирать в графе вершину с наибольшей красной степенью и перекрашивать ребра, которым она принадлежит, то с каждым шагом число синих ребер будет увеличиваться. Число ребер в графе с n вершинами конечно, поэтому через конечное число шагов все ребра графа станут синими.

1.3.8.Методические рекомендации к занятию №4.

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

В конце урока можно устроить фронтальный опрос, тем самым закрепить полученные знания.

На этом занятии также используем интерактивные методы обучения.

Список литературы к занятию №4.

1. Уилсон Р. Введение в теорию графов. - М.: Мир, 1977, 35-40с.

2. Харари Ф. Теория графов. - М.: Едиториал УРСС, 2003.

3. Зыков А.А. Основы теории графов. - М.: Вузовская книга, 1987, 25-30 с.

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

1.3.9.Содержание занятия №5.

«Решение логических задач».

1.Встретились три подруги: Белова, Краснова и Чернова. На одной из них было надето черное платье, на другой - красное, а на третьей белое. Девочка в красном платье говорит Черновой: « Нам надо поменяться платьями, а то цвет наших платьев не соответствует нашим фамилиям». Кто из девочек в какое платье был одет?

Решение. Здесь мы имеем два равночисленных множества: множество фамилий и множество цветов платьев. Между этими множествами надо установить взаимно-однозначное соответствие. Для этого построим граф. Пусть белые кружочки Б, К и Ч изображают элементы первого множества (Белова, Краснова и Чернова), а черные кружочки б, к и ч - элементы второго множества - белое, красное и чёрное. Условимся соединять эти кружочки тонкой линией, если между ними нет соответствия. Если же соответствие между кружочками установлено правильно, то будем соединять их жирной линией.

Следовательно, Белова одета в чёрное платье, Чернова одета в красное платье и Краснова - в белое платье.

2. Несколько мальчиков встретились на вокзале, чтобы поехать за город в лес. При встрече все они поздоровались друг с другом за руку. Сколько мальчиков поехало за город, если всего было 10 рукопожатий? Будем решать эту задачу графически. Вначале отметим точки А и В и соединим их отрезком. Точками будем изображать мальчиков, а отрезок будет означать рукопожатие. Добавим еще одну точку С и соединим её с точками А и В. Всего получается три отрезка.

Отметим следующую точку Д и соединим её отрезками с тремя точками А, В и С. Теперь уже получилось шесть отрезков. Наконец, отметим пятую точку Е и соединим её со всеми точками, отмеченными ранее. Получилось 10 отрезков, т. е 10 рукопожатий. Значит, на вокзале встретились 5 мальчиков.

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

Теперь видно, что долететь от Земли до Марса нельзя.

4. Петя, Гена, Дима и Вова занимаются в детской спортивной школе в разных секциях: гимнастической, баскетбольной, волейбольной и легкой атлетики. Петя, Дима и волейболист учатся в одном классе. Петя и Гена на тренировки ходят пешком вместе, а гимнаст ездит на автобусе. Легкоатлет не знаком ни с баскетболистом, ни с волейболистом. Кто из мальчиков в какой секции занимается? Решение. Петя - баскетболист, Гена - волейболист, Дима - гимнаст, а Вова - легкоатлет.

Ответ: Витя знаком с Серёжей и Колей, Серёжа знаком с Витей и с Пете, Петя знаком с Серёжей и с Максимом, Максим знаком с Пете и с Колей, Коля знаком с Петей и с Витей.

5. Марина, Лариса, Жанна и катя умеют играть на разных инструментах (пианино, виолончели, гитаре, скрипке), но только каждая на одном. Они же знают иностранные языки (английский, французский, немецкий. Испанский), но каждая только один. Известно: 1) девушка, которая играет на гитаре, говорит по-испански; 2) Лариса не играет ни на скрипке, ни на виолончели и на знает английского языка; 3) Марина не играет ни на скрипке, ни на виолончели и на знает ни немецкого, ни английского языка; 4) девушка, которая говорит по-немецки, не играет на виолончели; 5) Жанна знает французский язык, но не играет на скрипке. Кто на каком инструменте играет и какой иностранный язык знает?

Решение

Из пятого условия, что Жанна знает французский язык, рисуем стрелку. Из третьего условия, что Марина не знает ни немецкого, ни английского, а французский знает Жанна, то Марина знает испанский и рассматривая первое условие она играет на гитаре. Из условия N2 видим, что Лариса играет на пианино, т.к. Марина играет на гитаре, а на других инструментах она играть не умеет, и значит, она говорит по-немецки.

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

6. Три друга: Алеша, Боря и Витя - учатся в одном классе. Один из них ездит домой из школы на автобусе, один - на трамвае и один - на троллейбусе. Однажды после уроков Алеша пошел проводить своего друга до остановки автобуса. Когда мимо них проходил троллейбус, третий друг крикнул из окна: «Боря, ты забыл в школе тетрадку!» Кто на чем ездит домой?

Ответ: Алеша в трамвае, Боря в автобусе, Витя на троллейбусе.

7. Клоуны Бам, Бим, Бом вышли на арену в красной, синей и зеленой рубашках. Их туфли тоже были этих трех цветов. Туфли и рубашка Бима были одного цвета. На Боме не было ничего красного. Туфли Бама были синие, а рубашка нет. Каких цветов были туфли и рубашка у Бома и Бима?

Решение:

Красные туфли ,красная рубашка- Бам

Синие туфли ,синяя рубашка - Бим

Зеленые туфли , зеленая рубашка - Бом

Ответ: Бом - синяя рубашка и зленные туфли

Бам - зеленая рубашка и синие туфли.

8. Первенство класса.

В первенстве класса по настольному теннису 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводится по круговой схеме - каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной и Еленой; Борис, как уже говорилось, с Андреем и еще Галиной; Виктор - с Галей, Димой и Еленой; Галина - с Андреем и Борисом; Дмитрий - с Виктором; Елена - с Андреем и Виктором. Сколько игр проведено к настоящему моменту и сколько еще осталось?

Решение: Изобразим данные задачи в виде схемы. Участников изобразим точками по первым буквам имени. Если двое участников уже сыграли между собой, то будем соединять изображающие их точки отрезками. Такие схемы и называются графами. Точки А, Б, В, Г, Д, Е - вершины графа, соединяющие их отрезки - ребрами графа. Заметьте, что точки пересечения ребер графа не являются его вершинами. Во избежание путаницы вершины графа часто изображают маленькими кружочками, а не точками. Ребра же зачастую удобнее изображать не прямолинейными отрезками, а дугами.

Б В Б В

А Г А

Г

Е Д

Рис.1 Рис.2

Число игр, проведенных к настоящему моменту равно числу ребер, т.е. 7 игр (рис.1). Чтобы найти число игр, которое осталось провести, постоим еще один граф с теми же вершинами, но ребрами будем соединять тех участников, которые еще не сыграли друг с другом
(рис.2). Ребер у этого графа оказалось 8, значит, осталось провести 8 игр.

9. В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что вода и молоко не в бутылке, сосуд с лимонадом стоит между кувшином и сосудом с квасом, в банке не лимонад и не вода. Стакан стоит около банки и сосуда с молоком. В какой сосуд налита каждая жидкость?

Ответ: Молоко - в кувшине, лимонад - в бутылке, квас - в банке, вода - в стакане.

10. На даче поселились пять мальчиков: Андрюша, Боря, Володя, Гена и Дима. Все были разного возраста: одному был 1 год, одному 2 года, остальные 3, 4 и 5 лет. Володя был самым маленьким, Диме было столько лет, сколько Андрюше и Гене вместе? Сколько лет Боре? Возраст кого из мальчиков можно еще определить?

11. Четырём людям надо в темноте перейти через мост.
У людей есть один фонарик на четверых.
Переходить мост можно только с фонариком, потому что темно и мост без перил.
Одновременно на мосту мосту могут находиться не более двух человек, потому что мост старый и не выдержит больше.
У каждого человека своя скорость прохождения через мост: первый проходит мост за 1 минуту, второй - за 2 минуты, третий - за 5, четвёртый - за 10 минут.
Когда два человека переходят мост вместе, они идут со скоростью наиболее медленного из них.Какое минимальное время понадобится этой четвёрке, чтобы перейти мост, и в какой последовательности им надо его переходить

Решение

Обозначим людей 1,2,5,10 по времени, затрачиваемому на переход через мост.
Вот последовательность переходов, гарантирующая минимальное время (время на каждый переход указано в скобках
0. Все на исходной позиции: 1, 2, 5, 10 ⇔ - (0 мин.)
1. 1 и 2 идут на другой берег: 5, 10 ⇔ 1, 2 (2 мин.)
2. 1 возвращается: 1, 5, 10 ⇔ 2 (1 мин.)
3. 5 и 10 идут на другой берег: 1 ⇔ 2, 5, 10 (10 мин.)
4. 2 возвращается: 1, 2 ⇔ 5, 10 (2 мин.)
5. 1 и 2 идут на другой берег: - ⇔ 1, 2, 5, 10 (2 мин.)
Итого: 2 + 1 + 10 + 2 + 2 = 17 минут.
Формальное доказательство можно провести с использованием графа, вершинами в котором являются положения людей и фонарика на разных концах моста; две вершины соединены ребром тогда и только тогда, когда из одного положения можно перейти в другое по условиям задачи (фонарик, не более двух человек за переход etc); вес ребра - время, затрачиваемое на такой переход.
Для решения этой задачи надо найти на этом графе минимальный путь из начального положения в конечное.

1.3.10.Методические рекомендации к занятию №5.

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

Для решения первой и второй задачи можно вызвать ученика к доске. Разобрать задачу всем классом. Можно предложить ребятам проверить решение второй задачи на практике. Вызвать к доске сначала 2, затем 3, 4 и 5 учащихся и попросить их пожать друг другу руки. Весь класс сможет убедиться, что всего было 10 рукопожатий - использование элементов игры.

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

Для решения 5,6 и 7 задач разделим класс на 3 группы(1ый ряд-1ая группа, 2-ой - вторая и третий - соответственно). Чей ряд быстрее решит- получают оценки. При этом учитель должен спросить решение задачи у слабого ученика из группы.

8, 9, 10 задачу ученики должны решить самостоятельно. 11 задачу учитель вызывает ученика и вместе с классом разбирают решение. Последняя задача покажет детям, что логические задачи могут быть решены различными способами. Возможно некоторых детей заинтересуют другие способы решения ранее пройденных задач и найдут их. Это повысит интерес к математике.

1.3.11.Методические рекомендации к занятию №6. «Урок- конференция».

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

Предполагаемые темы творческих работ:

1.Графы в головоломках. (Мельников О.И. Занимательные задачи по теории графов. - М.: НТООО «ТеатраСистемс», 2001.; Ттат У. Тоерия графов: пер. с англ. - М.: Мир, 1998.)

2. Графы и игры на шахматной доске. (Мельников О.И. Занимательные задачи по теории графов. - М.: НТООО «ТеатраСистемс», 2001.)

3. Геометрическая задача о лабиринтах. (Уилсон Р. Введение в теорию графов. - М.: Мир, 1977.)

4. Графы и подсчет числа изомеров. (Берж К. Теория графов и ее применения. - М.: Иностранной литературы, 1962.)

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

6. Расчет сетевых графиков. ( Берж К. Теория графов и ее применения. - М.: Иностранной литературы, 1962.)

7. Графы и транспортные сети. (Берж К. Теория графов и ее применения. - М.: Иностранной литературы, 1962.; Уилсон Р. Введение в теорию графов. - М.: Мир, 1977.)

8. Графы в электротехнике. (Берж К. Теория графов и ее применения. - М.: Иностранной литературы, 1962.)

9. Графы в психологии. (Берж К. Теория графов и ее применения. - М.: Иностранной литературы, 1962.).

10. Проблема четырех красок. (Донец Г.А. Алгебраический подход к проблеме раскраски плоских графов. - М.: Наукова думка, 1982.)

11. Графы в физике. (Берж К. Теория графов и ее применения. - М.: Иностранной литературы, 1962.).

12. Графы с цветными ребрами. (Донец Г.А. Алгебраический подход к проблеме раскраски плоских графов. - М.: Наукова думка, 1982.).