Дискретная математика для будущего учителя математики (стр. 5 )

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

В 1852 году английский студент Френсис Гатри, составляя карту графств Англии, обратил внимание, что для такой цели вполне хватает четырех красок. Его брат, Фредерик, сообщил об этом наблюдении известному математику О. Де Моргану. А тот в свою очередь рассказал об этом в письме от 23 октября великому ирландскому математику и физику Уильяму Роэну Гамильтону: «…мой студент попросил меня сегодня объяснить одну задачу, которая мне не была ранее известна и пока не понятна до конца. Он утверждает, что если любую фигуру разделить любым способом на части и раскрасить их различными красками так, чтобы фигуры, имеющие общий отрезок граничной линии, были окрашены в различные цвета, то всего потребуются четыре краски, но не больше. Мне известен случай, когда требуется четыре краски. Вопрос: нельзя ли придумать случай, когда необходимы пять или более красок?.. Если Вы придумаете очень простой пример, который покажет, насколько я глуп, то, думается, мне надо будет поступить, как Сфинксу».

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

Точная формулировка гипотезы была опубликована в 1878 году выдающимся английским математиком А. Кэли в его докладе на заседании Британского географического общества.

Чтобы поставить задачу с полной строгостью, надо в каждой стране выбрать по точке (вершине графа), которые соединяются между собой простыми замкнутыми кривыми (рёбрами графа) в том и только том случае, если эти точки лежат в соседних странах и потребовать, чтобы полученный граф был связными. Тогда гипотезу четырёх красок на языке теории графов можно сформулировать так: всякий планарный граф 4-раскрашиваем или верно ли, что для любого планарного графа G , где -хроматическое число графа?

В силу простоты своей формулировки эта проблема постоянно привлекала к себе внимание, причём не только профессионалов-математиков, но и многочисленных любителей.

Много было опубликовано разных «доказательств» гипотезы четырех красок, но со временем в каждой из них обнаруживалась ошибка.

В начале XX века идеи Дж. Д. Биркгофа позволили П Франклину в 1913 году доказать гипотезу для карты с не более чем 25 странами. Позже это число было увеличено до 38.

Казалось, история проблемы четырех красок повторяет историю Великой теоремы Ферма. В правильности исходной гипотезы Гатри почти не было сомнений, но до тех пор, пока не получено доказательство для общего случая, всегда оставалась возможность, что кому-нибудь все же удастся начертить карту, которая опровергнет эту гипотезу. И, действительно, в 1975 году известный популизатор науки и многолетний ведущий раздела «Математические игры» журнала «Scientific American» Мартин Гарднер опубликовал карту (см. рис. 6), для раскрашивания которой якобы требовались пять красок. Однако номер журнала «Scientific American» вышел 1 апреля, а Гарднер был великолепно осведомлен о том, что хотя раскрасить его карту четырьмя красками довольно трудно, но отнюдь не невозможно.

Рис. 6

Со временем становилось ясно, что традиционные подходы не позволяют преодолеть пропасть, отделяющую предложенное Оре и Стемплом доказательство для карт, содержащих не более 39 областей, от доказательства для любых карт, возможно, состоящих из бесконечно большого числа областей. И вот в 1976 году два математика из Иллинойского университета, Вольфганг Хакен и Кеннет Аппель, предложили новый метод, перевернувший традиционные представления о математическом доказательстве.

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

Разумеется, проверка всех 1482 карт и перебор различных комбинаций раскраски каждой из них – задача необычайно громоздкая и трудоемкая, заведомо выходящая за рамки возможностей любой группы математиков. Даже при использовании компьютера перебор возможных вариантов мог бы затянуться на столетие. Но Хакен и Аппель не пали духом и принялись разыскивать удачные ходы и стратегии, использование которых позволило бы ускорить проверку карт и вариантов их раскрашивания. В 1975 году, через пять лет, после того как они приступили к работе над проблемой четырех красок, Хакен и Аппель стали свидетелями, что компьютер не только выполняет вычисления, но и делает нечто большее, а именно привносит в работу новые идеи.

В июне 1976 года, затратив 1200 часов машинного времени, Хакен и Аппель заявили во всеуслышание, что им удаолось проанализировать все 1482 карты и для раскрашивания ни одной из них не требуется более четырех красок. Проблема четырех красок Гатри была, наконец, решена. Решение проблемы четырех красок с помощью компьютера было выдающимся достижением, но в то же время оно вызывало у математического сообщества чувство тревоги, так как проверка доказательства в традиционном смысле пока не представляется возможной.

Попытки доказать эту гипотезу более доступным и менее трудоемким способом, не прекращаются. А вот доказать, что любой планарный граф 5-раскрашиваем довольно легко (см.[19], [50], [60], [63] и др.).

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

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

Задача. Имеется шесть групп учащихся: 1) математики; 2) химики; 3) историки; 4) физики; 5) биологи; 6) литераторы. Учащиеся каждой группы должны посещать лекции по соответствующей дисциплине. Например, математики – по математике, физики – по физике и т. д. Математики также должны посещать лекции по физике, физики – по математике, химики – по физике, биологи – по физике и химии. Кроме того, учащиеся каждой группы хотели бы посещать лекции по истории, а математики и физики – ещё и лекции по литературе. Требуется составить оптимальное расписание, которое удовлетворило бы всех учащихся.

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

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

Математика	Химия
Физика
Биология	Литература
История

Существует довольно обширный класс и других практических задач, которые сводятся к правильной раскраске вершин графа. Таковы, например, задачи об обслуживании авиалиний, распределении оборудования, проектировании коробки скоростей, распределении памяти ЭВМ и другие [19],[20],[39],[47],[60],[68].

§ 2. Приложения теории графов

Не столь важно знание фактов, сколь знание связи между ними [31] Леонардо да Винчи (), итальянский живописец

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

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

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

Полные графы

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

(29).

Доказательство формулы (29) см. в [20], [42], [50].

С полными графами связано множество однотипных задач. Например:

Задача 1. В соревновании, в котором каждая команда сыграла с каждым, участвовало 6 команд. Сколько встреч было сыграно?

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

По формуле (29) получаем, что встреч было сыграно.

Задача 2. В одной компании при встрече каждый пожал руку каждому. Всего было сделано 15 рукопожатий. Сколько человек в компании?

Решение. Пусть каждый человек в компании – это вершина графа, тогда ребра графа – это рукопожатия. Граф полный. Известно, что ребер в таком графе 15, необходимо узнать его порядок, т. е. количество его вершин. Из формулы (29) , приходим к квадратному уравнению , . В компании 6 человек.

Связные графы

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

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

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

Задача 2.3. (про внучек):

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

– Какой язык знает Жанна? – спросила я.

– Французский.

– А кто играет на гитаре?

– Помню только, что эта та девочка, которая говорит по-испански. – ответила бабушка.

Поговорив с бабушкой, я также узнала, что Лариса не играет ни на скрипке, ни на виолончели и не знает английского языка. Марина не играет ни на скрипке, ни на виолончели и не знает ни немецкого, ни английского языка. Девушка, которая говорит по-немецки, не играет на виолончели. Жанна не играет на скрипке. И ещё есть внучка Катя. Я совсем запуталась. Скажите мне, кто на каком инструменте играет и на каком языке говорит?

Решение. В задаче речь идёт о трёх множествах: имена, инструменты, языки. Каждое множество содержит по четыре элемента. Обозначим их точками – вершинами графа. В зависимости от условий задачи, соединим вершины графа – сплошными отрезками (рёбра графа), если имеет место соответствие между данными элементами; или пунктирной линией – если соответствия нет. Задача сводится к нахождению на графе компонент связности (рис. 8).

1)  Так как Лариса, Марина, Жанна не играют на скрипке, то Катя играет на скрипке.

2)  Так как Жанна знает французский, то Марина не знает французский и Марина не знает английский и немецкий, значит Марина знает испанский и играет на гитаре.

3)  Из этого, следует, что Лариса не играет на виолончели и скрипке, значит Лариса играет на пианино.

4)  Из первых трёх пунктов, следует, что Жанна играет на виолончели и знает французский.

5)  Из пунктов 2 и 4 и Лариса не знает английский, значит Лариса знает немецкий.

6)  Из пунктов 2, 4, 5, следует, что Катя знает английский.

Марина

 

Гитара Английский

 

Пианино Немецкий

Скрипка Испанский

Виолончель Французский

Рис. 8. Граф решения задачи про внучек

Деревья

Деревом называется связный граф, не содержащий циклов.

Ряд задач из различных областей науки приводят к рассмотрению особого вида графов, которые называются деревьями. Деревья открывались несколько раз независимо друг от друга. Г. Кирхгоф применил их к исследованию электрических цепей, А. Кэли с помощью деревьев перечислил изомеры насыщенных углеводородов. К. Жордан впервые рассмотрел их как чисто математический объект.

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

Можно выбрать одну из вершин дерева и назвать её корнем. Само дерево при этом называется корневым. Любое корневое дерево можно ориентировать по направлению от корня к каждой висячей вершине (на рис.9 корнем является вершина A).

Такие деревья используются как модели для структуры многопользовательской директории файлов.

Корневые деревья сильно напоминают родословные, поэтому для них часто употребляется "семейная" терминология: отец, сын, брат и т. п. Например, вершина B3 приходится отцом для C3 и C4, а те, в свою очередь, сыновья для B3 и братья между собой (рис.9). Использование деревьев и такой терминологии может оказаться полезным при решении задач.

Задача 4. У царя Гвидона было три сына. Из его потомков сто имели по два сына, а остальные умерли бездетными. Сколько потомков было у царя Гвидона?

Решение. Царя Гвидона следует поместить в корне родословного древа. От него отходят три ветви, соответствующие сыновьям, потом ветви пойдут от сыновей и так далее. При этом в каждую вершину, кроме корневой, входит одна дуга орграфа (стрелка), а выходят либо две, либо ни одной. Кроме того, две дуги выходят ровно из ста вершин. Ясно, что число потомков равно именно числу выходящих дуг, то есть 3+2×100=203.

Задача 5. (задача из химии).

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

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

В построенном графе можно перейти по ребрам от любой вершины к любой другой, и в нем нет циклов. Т. е. имеем дело с деревом. Пусть молекула содержит n атомов углерода и m атомов водорода, поэтому в графе будет (n+m) вершин. Далее следует воспользоваться двумя предварительно доказанными простыми соотношениями. Первое: в дереве число ребер на единицу меньше числа вершин. Следовательно, в графе n+m-1 ребер. Второе: сумма числа ребер, выходящих из вершин графа, равна удвоенному числу ребер. Последнее соотношение называется леммой о рукопожатиях. Из вершин, обозначающих атомы углерода, выходит по 4 ребра, а из вершин, обозначающих атомы водорода, - одно. Из леммы о рукопожатиях вытекает: 4n+m=2(n+m-1). Отсюда получаем: m=2n+2. Это значит, что формула насыщенного углеводорода, имеющего n атомов углерода, - .

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

Графы Кэли

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

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

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

Деятельностный блок раздела 2

Задание 2.1. (предметное задание)

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

С помощью цветных графов Кэли докажите:

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

-  изоморфизм групп самосовмещений додекаэдра и группы самосовмещений икосаэдра.

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

Форма представления результатов выполнения задания 2.1: презентация полученных результатов. Рекомендуемая литература: [16].

Задание 2.2. (профессионально-педагогическое задание)

Разработайте школьный элективный курс «Графы и их применение».

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

Примерный план занятий элективного курса «Графы и их применение»

Занятие 1. Из истории возникновения теории графов. Графы помогают решать задачи.

Занятие 2. Некоторые основные понятия теории графов: полный граф, дополнение графа, степень вершины графа, маршруты в графе, связность графа, операции над графами.

Занятие 3. Деревья. Свойства деревьев. Остовое дерево. Деревья в программировании.

Занятие 4. Задача о трех домах и трех колодцах. Микросхемы в радиоэлектронике. Укладка графа. Формула Эйлера.

Занятие 5. Эйлеровы циклы. Фигуры непрерывного рисования. Правила обхода фигур одним росчерком. Задача о кёнигсбергских мостах. Исторический экскурс о Леонарде Эйлере.

Занятие 6. Гамильтоновы циклы. Гамильтона «Кругосветное путешествие». Задача коммивояжера.

Занятие 7. Лабиринты. Обходы лабиринтов.

Занятие 8. Раскраска графов. Задачи, связанные с раскраской графа. Гипотеза четырех красок. Свойства шахматной доски.

Занятие 9. О сетевых задачах. Основные понятия. Потоки в сетях. Сетевое планирование и управление.

Занятие 10. Алгоритмы. Сложность алгоритмов.

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

Форма представления результатов выполнения задания 2.2: методическая разработка элективного курса и его презентация в Power Point. Рекомендуемая литература: [5], [6], [20], [22], [24], [25], [26], [33], [40], [41], [48], [60] и др.

Задание 2.3. (общепрофессиональное задание)

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

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

Методика построения опорных конспектов:

o  определить объем излагаемого материала, используемого для опорного конспекта;

o  разделить этот материал на основные блоки;

o  выделить в них основные определения и тезисы;

o  продумать отражение этих определений или понятий в виде опорных сигналов;

o  внести их в схему блока;

o  обозначить взаимосвязи между опорными сигналами внутри каждого блока;

o  обозначить взаимосвязь между всеми блоками теоретического материала;

o  вынести условные обозначения за пределы опорного конспекта.

Постановка задания 2.3. Составьте опорный конспект, в котором наглядно будет закодировано основное содержание учебного материала по теме «Основные понятия теории графов. Определение графа».

Форма представления результатов выполнения задания 2.3: макет опорного конспекта и его презентация.

Рекомендуемая литература: [20], [25], [30], [47], [59], [60], [63], [67], [68] и др.

Задание 2.4. (профессионально-педагогическое задание)

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

Форма представления результатов выполнения задания 2.4: альбом – методическая копилка «в помощь учителю математики» и ее презентация.

Рекомендуемая литература: [3], [11], [14], [40], [61], [62], [68]

Задание 2.5. (общепрофессиональное задание)

Ознакомьтесь со стандартными требованиями, предъявляемыми к оформлению реферата и технологиями его написания. Напишите реферат о приложениях теории графов. Подготовьте реферативное сообщение. Рекомендуемая литература: [5], [6], [20], [22], [24], [25], [26], [33], [40], [41], [48], [60] и др.

Задание 2.6. (общепрофессиональное задание)

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

Рекомендации по написанию аннотации

Аннотация – краткая характеристика печатного издания (или его части) с точки зрения содержания, назначения, формы и других особенностей.

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

Чтобы составить аннотацию, нужно ответить на следующие вопросы: Как называется книга (статья, монография)? Где и когда напечатана? Чему посвящена? Какие вопросы рассматриваются в книге? Кому она адресована?

Форма представления результатов выполнения задания 2.6: альбом со списком аннотированной литературы по теории графов и его презентация.

Задание 2.7. (предметное задание)

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

Форма представления результатов выполнения задания 2.7: альбом с оформленными результатами и комплексом задач. Презентация альбома.

Задание 2.8. (предметное задание)

Составьте комплекс задач, сводящихся к раскраске графа.

Форма представления результатов выполнения задания 2.8: альбом задач и презентация их решений.

Рекомендуемая литература: [19],[20],[39],[47],[60],[68].

Задание 2.9. (профессионально-педагогическое задание)

А) Найдите в специальной литературе различные приемы решения логических задач (особо обратите внимание на прием решения при помощи графов). Напишите методичку для учителя «Приемы решения логических задач».

Б) С дидактической точки зрения проанализируйте задачи 1-6. Опишите методику их решения.

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

Задача 2. Встретились трое друзей – Белов, Чернов и Рыжов. Один из них блондин, другой – брюнет, третий – рыжий. Брюнет сказал Белову: «Ни у одного из нас цвет волос не соответствует фамилии». Какой цвет волос у каждого из них, если известно, что брюнет всегда говорит правду?

Задача 3. Следователь допросил трёх лиц А, В и С, подозреваемых в совершении преступления. На допросе А сказал, что показания В неверны. В сказал, что показания С неверны. Наконец, С сказал, что А говорит неправду и В говорит неправду. Может ли следователь на основании этих показаний установить кто из допрашиваемых говорит правду?

Задача 4. В забеге шести спортсменов Алексей отстал от Бориса и ещё двух спортсменов. Виктор финишировал после Дмитрия, но ранее Геннадия. Дмитрий опередил Бориса, но всё же пришёл после Евгения. Какое место занял каждый спортсмен?

Задача 5. На острове есть несколько населённых пунктов. Из каждого пункта выходят две проезжие дороги и три пешеходные тропы. Каждая проезжая дорога и каждая пешеходная тропа приводят к некоторому населённому пункту. Любые два населённых пункта связаны чем-то одним – или дорогой, или тропой. Сколько на острове населённых пунктов, проезжих дорог, и пешеходных троп?

Задача 6. После родительского собрания Федин папа сказал классному руководителю:

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

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

Что ещё собирался сказать классный руководитель?

Форма представления результатов выполнения задания 2.9: Альбом с оформленными результатами анализа задач (1-6) и их решениями. Презентация методички.

Рекомендуемая литература: [23], [36], [45], [66].

Задание 2.10. (предметное задание)

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

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

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

1)  определения связности графа;

2)  нахождения маршрутов в графе (поиск в глубину, поиск в ширину);

3)  выделения эйлерова и гамильтонова цикла в графе;

4)  нахождения остова минимального веса в графе (алгоритм Краскала);

5)  правильной раскраски вершин графа.

Форма представления результатов выполнения задания 2.10: презентация разработанных компьютерных программ с демонстрацией их работы на конкретных задачах. Рекомендуемая литература: [29], [46] и др.

Задание 2.11. (профессионально-педагогическое задание)

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

Ценностный блок раздела 2

1)  Оцените перспективы развития теории графов.

2)  Оцените прикладное значение теории графов.

3)  Оцените вклад Л. Эйлера в развитие теории графов.

4)  Оцените значимость матричного представления графов.

5)  Оцените роль операций над графами как аппарата, используемого для доказательства теорем и построения алгоритмов теории графов.

6)  Оцените роль и значение понятия «дерево» в теории графов, в информатике.

7)  Оцените прикладное значение раскраски графов.

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

9)  Напишите сочинение: «Мои методические рекомендации по изучению дискретной математики».

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

1)  Андерсон, Дж. Дискретная математика и комбинаторика. – М.: Изд. дом «Вильямс», 2004.

2)  Большой энциклопедический словарь: в 2-х т. / Гл. ред. . – Сов. энциклопедия, 1991.

3)  Бабинская, математических олимпиад. – М., 1975

4)  Баррет, Д. GavaScript. Web – профессионалам. – Киев: БХВ, 2001.

5)  Березина, и их применение. – М.: Просвещение, 1979.

6)  Варга, Т. Математика 2. Деревья и графы. – М.: Педагогика, 1978.

7)  Волков, В. Рекуррентные соотношения. // Газета «Математика», прил. к газете «Первое сентября»– № 13 – с. 39-41.

8)  Воробьев, Фибоначчи. – М.: Наука, 1992.

9)  Виленкин, / , , . – М.: ФИМА, МЦНМО, 2006.

10)  Виленкин, и математический анализ (для школ с углубленным изучением математики) /, -Мусатов, . – М.: Просвещение, 1990

11)  Гашков, элементарная алгебра в задачах и упражнениях. – М.: МЦНМО, 2006.

12)  логики: В 4 т. М.: Мысль, 1970

13)  Глейзер, математики в школе. В трех книгах. – М.: Просвещение, гг.

14)  Горбачев, олимпиадных задач по математике. – М.: МЦНМО, 2004.

15)  Готт, неисчерпаемый познаваемый мир. – М.: Знание, 1974.

16)  Гроссман, И. Группы и их графы / И. Гроссман, В. Магнус. – М.: Мир, 1971.

17)  Грэхем, Р. Конкретная математика. Основание информатики / Р. Грэхем, Д. Кнут, О. Паташник. – М.: Мир, 2006. – 703 с.

18)  Ежов, комбинаторики / , , . – М.: Наука, 1977.

19)  Елисеев, дискретной математики: учебное пособие / , . – Арзамас, АГПИ им. , 2005.

20)  Емеличев, по теории графов / , , . – М.: Наука, 1990.

21)  Жданов, задач по дискретной математике: Учебное пособие /, , . – М.: МПГУ, 2005

22)  Загоруйко, теории графов. – Новосибирск, 1993.

23)  Заесёнок, приёмы решения логических задач // Математика в школе - № г. - с. 29-33

24)  Захарова, математика и ее приложения: учебное пособие. – Пенза: Изд-во Пенз. гос. ун-та, 2006.

25)  Зыков, теории графов. – М.: Наука, 1987.

26)  Игнатьев, по математике «В царстве смекалки, или арифметика для всех» – Ростов, 1995 г

27)  ЭВМ и математика. Кишинев: Штиинца, 1984

28)  Колосов, и задачи алгебры, теории чисел и комбинаторики – М.: Гелиос АРВ, 2001.

29)  Кнут, Д. Искусство программирования для ЭВМ, в двух томах. – М.: Мир, 1977.

30)  Кристофидес, Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978.

31)  Левин, А. Что такое комбинаторика // Журнал «Квант» - 1999. - №5,6.

32)  Леонардо да Винчи. Избранные естественно-научные произведения /Ред., пер. и коммент. . – М.: Изд-во АН СССР, 1955

33)  Ловас, Л. и др. Прикладные задачи по теории графов /Л. Ловас, . – М.: Мир, 1998.

34)  Логинов, в дискретную математику. Лекции и упражнения. – Калуга, 1998.

35)  Льюис Кэрролл, кн. 1 «Алиса в стране чудес», кн. 2 «Сквозь зеркало и что там увидела Алиса» / Орловской, София, 1967

36)  Лютикас, о теории вероятностей. – М: Просвещение, 1976.

37)  Маркушевич, последовательности. – М.: Наука, 1993.

38)  Html 4.0 – СПб.: БХВ, 1999.

39)  Матросов, по дискретной математике / , . – М.: МГПУ, 1997.

40)  Мельников, задачи по теории графов – Минск: Тетрасистемс, 2001.

41)  Мельников, в стране графов. – М.: КомКнига/URSS, 2006

42)  Мельников, дискретной математике: монография. – М.: Изд-во ЛКИ, 2008.

43)  Миракова, математика и IT-технологии. Учебно-методическое пособие /, . – Орехово-Зуево, МГОПИ, 2007

44)  Нефедов, дискретной математики /, . – М.: МАИ, 1992.

45)  Никифорова, М. Занимательные логические задачи для 5-6 кл. // Газета «Математика» № 7, 2005 г., с 16-18; № 10, 2005 г. с. 4-7.

46)  Новиков, математика для программистов /. – СПб.: Питер, 2001.

47)  Оре, О. Теория графов. – М.: Наука, 1980.

48)  Оре, О. Графы и их применение: Пер. с англ. / Под ред. и с предисл. . – М.: Издательство ЛКИ, 2008.

49)  Романовский, анализ. – СПб.: Невский Диалект; БХВ-Петербург, 2003.

50)  Руцкий, математика: Учебное пособие. – Красноярск: РИО КГПУ, 2004.

51)  Руцкий, задач по дискретной математике. Часть 1. Рекуррентные соотношения, суммирование, асимптотическая аппроксимация. – Красноярск: РИО КГПУ, 2008.

52)  Руцкий, задач по дискретной математике. Часть 2. Теория графов. – Красноярск: РИО КГПУ, 2006.

53)  Руцкий, математика. Методические рекомендации для студентов по самостоятельной работе. – Красноярск: РИО КГПУ, 2008.

54)  Савин, А. Число Фидия – золотое сечение //Журнал «Квант» - 1997. - №6

55)  Сачков, методы дискретной математики /. – М.: Наука, 1977.

56)  Семеновых, А. Комбинаторика //газета «Математика» прил. к газете «Первое сентября». – 2004. – №№ 15–17.

57)  Спирина, математика /, . – М.: Изд. центр «Академия», 2006. – 368 с.

58)  Стройк, очерк истории математики. – М.: Наука, 1984.

59)  Татт, У. Теория графов. – М.: Мир, 1988.

60)  Уилсон, Р. Введение в теорию графов /Р. Уилсон. – М.: Мир, 1977.

61)  Фарков, олимпиады в школе. 5-11 класс. – М., 2004

62)  Фомин, -Петербургские математические олимпиады. – СПб.: Политехника, 1994

63)  Харари, Ф. Теория графов /Пер. с англ. и предисл. . Под ред. . Изд. 3-е, стереотипное. – М.: КомКнига, 2006.

64)  Холл, М. Комбинаторика. – М.: Мир, 1988.

65)  Цыганов, Ш. Комбинаторика от А до Я //газета «Математика» прил. к газете «Первое сентября». – 2001. – №№ 25–28.

66)  Шевченко, способы решения логических задач. – Киев, Вища школа, головное изд-во, 1979 – 80 с.

67)  Энциклопедия: Дискретная математика /Гл. ред. . – М.: БРЭ, 2004

68)  Яблонский, в дискретную математику /. – М.: Высшая школа, 2003.

69)  Яглом, алгебра, конечная геометрия и коды. – М.: Знание, 1980

Список экзаменационных вопросов по дискретной математике

1.Комбинаторика. Комбинаторные правила суммы и произведения. Комбинаторные объекты и числа. Примеры. Комбинаторика в школьном курсе математики.

2.Рекуррентные соотношения. Задачи, приводимые к рекуррентным соотношениям. Возвратные последовательности в школьном курсе математики.

3.Решение линейных рекуррентных соотношений второго порядка с постоянными коэффициентами. Примеры.

4.Решение линейных рекуррентных соотношений k-го порядка. Примеры.

5.Специальные комбинаторные числа.

6.Суммы, формы записи сумм, законы преобразования сумм. Суммы и рекуррентные соотношения. Примеры.

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

8.Методы исчисления конечных сумм. Примеры.

9.Сложность алгоритмов. Оценки и асимптотики комбинаторных чисел.

10.  Графы, орграфы, псевдографы, мультиграфы. Основные элементы графа и его внутренняя структура. Примеры. Графы в школьном курсе математики.

11.  Степени вершин графов. Теорема о сумме степеней вершин графа. Полустепени вершин орграфа. Теорема о сумме полустепеней вершин орграфа. Примеры.

12.  Матричное задание графов. Матрицы смежности и инцидентности. Примеры.

13.  Операции над графами. Подграфы. Примеры.

14.  Изоморфизм графов. Примеры.

15.  Маршруты и пути в графах и орграфах. Цепи, циклы, простые цепи и простые циклы. Теоремы о простых цепях и циклах. Примеры.

16.  Связность и сильная связность в графах и орграфах. Компоненты связности графа. Теорема о дополнении графа. Связь числа рёбер, вершин и компонент связности.

17.  Поиск маршрутов в графах. Алгоритмы поиска в ширину и в глубину.

18.  Нагруженные графы. Поиск минимальных маршрутов в графах.

19.  Деревья. Свойства деревьев. Характеризационная теорема.

20.  Остовное дерево. Поиск минимального остовного дерева в нагруженных графах.

21.  Эйлеровы графы и циклы. Критерий эйлеровости графа. Алгоритм выделения эйлерова цикла в графе. Примеры.

22.  Гамильтоновы графы и циклы. Достаточные условия существования гамильтоновых циклов. Методы выделения гамильтоновых циклов в графе. Примеры.

23.  Двудольные графы. Теорема Кёнига. Способ распознавания двудольности графа. Примеры.

24.  Плоские и планарные графы. Грани плоского графа. Примеры укладки графов. Формула Эйлера.

25.  Следствие из формулы Эйлера. Непланарность графов К3.3 и К5. Критерий планарности графа.

26.  Правильная раскраска вершин графа. Хроматическое число. Алгоритм последовательной раскраски. Примеры.

27.  Раскраска планарных графов. Гипотеза о четырёх красках. Теорема о пяти красках.

28.  Реберная раскраска графов. Примеры.

29.  Потоки в сетях.

Содержание

Введение …………………………………………………………………………………..3

Когнитивный блок раздела 1

Комбинаторика в школьном курсе математики…………………....…………...7

§1 Основные комбинаторные объекты и числа…………………………………..8

§2 Рекуррентные соотношения. Числа Фибоначчи……………………………..15

§3 Конечные суммы…………………………………………………………………….22

§4 Производящие функции. Числа Каталана…………………………………….28

Деятельностный блок раздела 1…………………………………………..………..31

Ценностный блок раздела 1……………………………………………………........38

Когнитивный блок раздела 2

Элементы теории конечных графов в школьном курсе математики….…..39

§1 Из истории возникновения теории графов……………………………….......41

§2 Приложения теории графов…………………………………………………..…51

Деятельностный блок раздела 2…………………………………………..…….….56

Ценностный блок раздела 2……………………………………………..………......61

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

Список экзаменационных вопросов по дискретной математике.................65