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

Числа Каталана довольно часто встречаются в дискретной математике. Например, числами Каталана являются:

а) число таких способов расстановки скобок в частном b1:b2: … :bn+1, при которых получающиеся выражения имеют смысл;

б) число способов попарного соединения 2n точек окружности n непересекающимися хордами;

в) число матриц размера (2´n), элементами которых являются числа 1, 2, …, 2n, расположенные в порядке возрастания в каждой строке и в каждом столбце;

г) число неизоморфных корневых бинарных деревьев с n вершинами.

Кроме чисел Каталана, известно достаточно много комбинаторных чисел (Стирлинга, Белла, Эйлера, Бернулли и другие).

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

Два мира есть у человека: Один, который нас творил, Другой, который мы от века Творим по мере наших сил Н. Заболоцкий

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

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

Форма представления результатов выполнения задания 1 1: альбом задач по комбинаторике и его презентация. Рекомендуемая литература: [3], [9], [10], [14], [18], [21], [26], [28], [31], [56], [61], [62], [64], [65] и др.

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

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

Примерное содержание электронного учебника:

·  Сведения из истории возникновения и развития комбинаторики.

·  Старинные комбинаторные задачи.

·  Понятия «множество» и «кортеж». Примеры.

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

·  Размещения. Размещения с повторениями. Примеры. Дидактический комплекс задач (тренировочные задачи; задачи для домашней работы; дополнительные задачи).

·  Перестановки. Перестановки с повторениями. Комплекс задач.

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

·  Приложения комбинаторики.

·  Задачи для зачетной работы. Контрольный тест.

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

Разработайте фрагмент учебного занятия по изучению элементов комбинаторики с использованием электронного учебника.

Форма представления результатов выполнения задания 1.2: электронная версия учебника с методическими рекомендациями и его презентация. Рекомендуемая литература: [3], [4], [9], [10], [18], [21], [26], [28], [31], [36], [38], [56], [61], [62], [64], [65].

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

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

Примерный план экскурса в историю науки

-  сведения о зарождении науки;

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

-  хронология основных переломных этапов развития науки;

-  биографические сведения, освещающие судьбы научных идей и судьбы их творцов;

-  сведения о современных тенденциях развития науки;

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

-  кроссворд или викторина по историческому экскурсу.

Форма представления результатов выполнения задания 1.3: презентация историеских экскурсов. Рекомендуемая литература: [9], [13], [58] и др.

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

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

v  Введение: сведения об актуальности темы сочинения;

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

v  Заключение: выводы, анализ перспектив развития этих связей и их приложений;

v  Библиографический список используемой литературы.

Примерные темы сочинений: комбинаторика в информатике; комбинаторика в теории вероятности; комбинаторика в теории игр; комбинаторика и периодическая таблица Менделеева; комбинаторика и физика; комбинаторика в кодировании; комбинаторная природа генетического кода; комбинаторика в школьном курсе математики и др.

Форма представления результатов выполнения задания 1.4: сочинение и его презентация на конкурс сочинений. Рекомендуемая литература: [8], [9], [24], [64] и др.

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

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

Примерный план Web-сайта

·  Что такое число? Исторический экскурс о возникновении чисел.

·  Числа Фибоначчи. Биографические сведения о Фибоначчи. Задача о кроликах. Замечательные свойства чисел Фибоначчи. Числа Фибоначчи и золотое сечение в Природе, Науке, Искусстве.

·  Гармонические числа – история их появления и основные свойства. Карточный фокус. Задача о червяке на резинке. Музыка и числа.

·  Числа Стирлинга первого и второго рода – сведения об их возникновении и приложениях.

·  Числа Бернулли – история их появления и основные свойства.

·  Фигурные числа

·  Комбинаторные задачи и числа Каталана.

·  Совершенные, дружественные, счастливые и др. числа.

·  Кроссворд, тест, ребус или викторина о специальных числах.

Форма представления результатов выполнения задания 1.5: Web-сайт и его презентация. Рекомендуемая литература: [1], [4], [8], [9], [17], [18], [26], [28], [38], [54], [67] и др.

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

Проанализируйте и сравните представленные в §3 подходы к выводу и доказательству формулы для суммы (n+1) первых членов любой арифметической прогрессии, ответив на вопросы: Какой из подходов приемлем для учащихся определенного возраста? Какие теоретические опорные знания и практические умения необходимо актуализировать перед рассмотрением каждого подхода? Существует ли еще какой-либо способ вывода формулы для суммы (n+1) первых членов любой арифметической прогрессии? Что называют арифметической прогрессией к-го порядка?

Аналогичные рассуждения проведите для геометрической прогрессии и различными способами осуществите вывод формулы для суммы (n+1) первых членов любой геометрической прогрессии.

Разработайте исторический экскурс о прогрессиях и комплекс заданий на мотивацию изучения учащимися 9 класса темы «Числовые последовательности. Прогрессии».

Смоделируйте вводный урок и урок обобщения и систематизации по теме «Прогрессии».

Форма представления результатов выполнения задания 1.6: альбом с оформленными результатами анализа; исторический экскурс и комплекс заданий на мотивацию изучения темы «Прогрессии»; конспекты двух уроков (вводный урок и урок обобщения и систематизации) по теме «Прогрессии». Его презентация. Рекомендуемая литература: [13], [26], [28], [37], [67] и др.

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

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

-  Неоднородные рекуррентные соотношения и методы их решения.

-  Рекуррентные соотношения и производящие функции.

-  Оценки и асимптотики комбинаторных чисел , .

-  Полиномиальная формула.

-  Число Фидия – золотое сечение.

Примерный план научной статьи

1.  Введение. Сведения об актуальности темы статьи. Чему посвящена статья? Какой вопрос затрагивается в статье? Основная цель статьи и т. п.

2.  Основная часть. Обоснованно раскрываются теоретические и практические аспекты проблематики статьи. Примеры.

3.  Заключение. Основные выводы, результаты, рекомендации и т. п.

4.  Библиографический список используемой литературы.

Форма представления результатов выполнения задания 1.7: печатный и электронный экземпляр статьи, подготовленный доклад с презентацией. Рекомендуемая литература: [1], [7], [8], [9], [17], [19], [37], [39], [49], [54], [55], [64], [67], [68] и др.

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

В специальной литературе найдите свойства чисел Фибоначчи и докажите их.

Форма представления результатов выполнения задания 1.8: альбом со свойствами и оформленными доказательствами. Презентация альбома. Рекомендуемая литература: [8], [9], [18], [21], [26], [28], [68] и др.

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

Проанализируйте ниже представленные четыре задачи по следующей схеме:

-  определите тематику, вид и уровень сложности рассматриваемых задач;

-  какие теоретические знания и практические умения потребуются для решения этих задач?

-  какие способы решения данных задач вы можете предложить?

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

1.  Найдите , если .

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

3.  Докажите, что числа и являются целыми и взаимно простыми числами.

4.  Докажите, что целая часть числа является четным числом.

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

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

Проведите структурно-логический и дидактический анализ теоретического материала по теме «Рекуррентные соотношения», согласно следующему плану:

I.  Установите соответствие между изучаемым материалом по теме «Рекуррентные соотношения» в вузовском курсе дискретной математики и школьном курсе математики:

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

2)  В каких классах школьного курса математики рассматриваются рекуррентные соотношения, в каком объеме и на каком уровне?

3)  Есть ли различия в изложении данного вопроса в курсе дискретной математики и школьном курсе математики?

4)  Какие факты, не изучаемые в школьном курсе математики, рассматриваются в вузовском курсе дискретной математики? Возможно ли их введение в школьный курс математики?

II.  Выявите соответствие предложенного учебного материала по теме «Рекуррентные соотношения» основным принципам дидактики математики: принцип научности, принцип доступности, принцип наглядности и др.

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

2)  Проанализируйте способы и методы их решения.

III.  Установите межпредметные связи по вопросам, связанным с рекуррентными соотношениями.

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

Форма представления результатов выполнения задания 1.10: альбом с оформленными результатами анализа; методическая копилка «в помощь учителю математики» и их презентация. Рекомендуемая литература: [3], [9], [10], [7], [11], [18], [19], [21], [37], [43], [61], [62], [64] и др.

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

Используя описанные в §3 методы исчисления конечных сумм, просуммируйте следующие суммы и докажите их справедливость:

1) ; 2) ; 3) ; 4) ; 5) ;

6) ; 7) ; 8) ;

9) (МИФИ) Вычислить сумму . Рекомендации к задаче 10: Представьте искомую сумму в виде сигма-рекуррентного соотношения и тогда методом неопределенных коэффициентов можно искать сумму в виде .

Какие методы исчисления конечных сумм, помимо тех, что описаны в §3, вы можете предложить? Приведите примеры.

Форма представления результатов выполнения задания 1.11: альбом с оформленными решениями и их презентацией. Рекомендуемая литература: [1], [17] , [39], [64], [67] и др.

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

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

Примерные рубрики журнала

o  Из истории кодирования

-  Способы шифрования в античные времена. Шифр «скитала». Полибианский квадрат. Код Чезаря.

-  В средние века. Шифрующие таблицы. Магический квадрат.

-  В XIX – начале XXвв. Шифратор Джефферсона. Линейка Сен-Сира. Шифр Вернама. Биографические сведения о Г. Вернаме, К. Шенноне.

o  Буквенные коды. Азбука Морзе

o  Телеграфные и почтовые коды

o  Кодирование в машинной технике

o  Расстояние и код Хемминга

o  Кодирование с помощью многочленов

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

o  Коды и тайнопись в художественных фильмах и литературе.

Рекомендуемая литература: [1], [17] , [27], [35], [43], [55], [68] и др.

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

1)  Оцените значение и роль основных методов дискретной математики в области исследования конечных математических структур.

2)  В чем, по вашему мнению, заключается основная цель изучения дискретной математики будущими учителями математики? Зачем будущим учителям математики изучать дискретную математику? Напишите сочинение на тему: «Что такое дискретная математика?», «Моя цель изучения дискретной математики».

3)  Проанализируйте историко-философские аспекты взаимодействия непрерывной и дискретной математики.

4)  Оцените роль и значение дискретной математики в развитии других областей науки. Оцените прикладное значение дискретной математики.

5)  Проанализируйте современные аспекты обучения школьников основам дискретной математики. Какие существуют возможности изучения дискретной математики в школе?

6)  Оцените перспективы развития дискретной математики.

7)  Оцените приложения комбинаторики.

8)  Проанализируйте современные аспекты обучения школьников комбинаторике.

9)  Оцените роль метода рекуррентных соотношений при решении комбинаторных задач и задач о возвратных последовательностях.

10)  Оцените роль рекуррентных соотношений в теории чисел.

11)  Сравните различные способы решения рекуррентных соотношений и оцените роль этих методов при решении комбинаторных задач.

12)  Оцените роль числа в науке, искусстве, природе.

13)  Оцените значимость перехода от сумм к рекуррентностям и, наоборот. Приведите примеры такого перехода.

14)  Сравните различные методы суммирования и оцените рациональность использования этих методов при исчислении конечных сумм. Какие методы суммирования вам известны из других математических курсов?

15)  Оцените роль формулы суммирования Эйлера-Маклорена.

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

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

Раздел 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эйлеровы и гамильтоновы графы

Первая работа о графах, принадлежащая швейцарскому математику Леонарду Эйлеру (), появилась в 1736 г. публикациях Петербургской Академии наук. Эйлер является одной из колоритнейших фигур в истории науки. В 1727 г., когда ему едва исполнилось 20 лет, он был приглашен в Российскую Академию наук. Он уже изучил теологию, восточные языки и медицину, прежде чем целиком посвятил себя занятиям математикой, физикой и астрономией. Он добился блестящих успехов во всех этих областях и написал огромное количество работ. К тому времени, когда он написал работу о графах, он потерял зрение на один глаз, а к старости совершенно ослеп, но даже это не остановило потока его работ. Уже довольно давно швейцарские математики, в частности математики его родного города Базеля, начали издавать полное собрание сочинений Эйлера, из которого пока опубликовано 50 томов. Первоначально предполагалось, что общее число томов будет близко к 100, но теперь уже думают, что оно окажется ближе к 200.

Эйлер начал свою работу о графах с рассмотрения одной головоломки – так называемой «задачи о кёнигсбергских мостах».

Город Кёнигсберг (ныне Калининград) расположен на берегах реки Преголя и двух островах. Различные части города соединены семью мостами (рис. 2).

Рис.2. Карта города Кёнигсберг

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

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

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

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

На языке теории графов эта задача звучит так: «найти в мультиграфе цикл, проходящий через каждое его ребро». Такой цикл, в произвольном связном графе, называется эйлеровым циклом, а сам граф – эйлеровым графом. Возникает вопрос: «Является ли мультиграф, изображенный на рис. 2 эйлеровым?». Л. Эйлер дал окончательный ответ на вопросы такого рода.

Критерий эйлеровости – необходимое и достаточное условие существования эйлеровых циклов: для того чтобы связный граф G обладал эйлеровым циклом, необходимо и достаточно, чтобы степени всех его вершин были чётными. Доказательство см.[50], [60], [68].

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

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

Известен анекдот: некто давал миллион рублей каждому, кто начертит следующую фигуру (рис. 3). Но при вычерчивании ставилось одно условие. Требовалось, чтобы эта фигура была вычерчена одним непрерывным росчерком, то есть, не отнимая пера или карандаша от бумаги и не удваивая ни одной линии, другими словами по раз проведённой линии нельзя было пройти второй раз. Надежда стать «миллионером», решив такую лёгкую задачу, может заставить испортить много бумаги и потратить много времени на попытки вычертить эту фигуру, как требовалось, одним росчерком. Задача, однако, не решается, и это тем досаднее, что она не решается только «чуть-чуть» (действительно, в этом легко убедиться, если применить критерий Эйлера для мультиграфа, изображённого на рис. 3: степени вершин этого мультиграфа – нечётные).

Известен ещё один пример.

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

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

Если задачу о Кенигсбергских мостах видоизменить следующим образом: «Можно ли проходя по ребрам мультиграфа (рис. 2), начиная с любой его вершины, обойти их все и вернуться в первоначальную вершину, посещая каждую ровно один раз?», то мы приходим к понятию «гамильтонов цикл».

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

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

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

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

Задача о трех домах и трех колодцах

Планерность графов

В другой трактовке эта задача называется задачей о газо-водо-электроснабжении.

Решение задачи сводится к существованию плоской укладки двудольного графа K3,3 (см. [50], [60]). Все попытки осуществить такую укладку неизбежно заканчивались неудачей. Как правило, легко нарисовать 8 непересекающихся дорожек, но девятая обязательно пересечёт хотя бы одну из этих восьми. Конечно, эти неудачи не случайны. Задача не имеет решения на плоскости.

Исторически первым подтверждением этого факта явился критерий планарности графа, доказанный независимо друг от друга (1927 г.) и К. Куратовским (1930г.): Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных K5 и K3,3. Доказательство можно найти в [50], [60].

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

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

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

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

Эта формула часто используется при решении задач.

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

Решение. У полученного графа 54 вершины, q рёбер и r граней, причём имеется одна внешняя четырёхугольная грань, а остальные грани – треугольные. Так как каждое ребро принадлежит ровно двум граням, то 2q=3(r–1)+4=3r+1. Если это значение для q подставить в формулу Эйлера, то получится: . Отсюда легко найти r=103. Значит, треугольников будет 102.

Задача о раскраске географической карты

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

Действительно история знаменитой проблемы четырёх красок, поставленной ещё в середине XIX века является уникальной и одновременно поучительной.