ВВЕДЕНИЕ В ТОПОЛОГИЮ. ПРОБЛЕМА ЧЕТЫРЕХ КРАСОК.

Украйченко Наталья Николаевна, МБОУ лицей №57, учитель математики

Богданова Марина Николаевна, МБОУ лицей №57, учитель математики

Введение

Научно-исследовательская работа посвящена изучению теоремы «Четырех красок». Цель проекта – понять, что такое топология, и изучить теорему четырёх красок.

Задачи работы:

1.Изучить имеющуюся литературу по данной теме.

2.Провести исследование по данной теме, связанное с внеурочной деятельностью

3.Рассказать о теореме четырёх красок.

4.Проверить данную теорему на практике

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

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

I. Введение в топологию.

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

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

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

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

II. Проблема 4 красок

2.1.История возникновения теоремы

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

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

Возник естественный вопрос: для раскраски любой ли карты хватит четырех красок? Студент Френсис не смог ответить на него. Через своего брата, Фредерика, сообщили об этом наблюдении известному английскому математику О. Де Моргану. Так эта проблема дошла до математической общественности, и точную формулировку гипотезы опубликовал в 1878 году другой английский математик А. Кэли: всякую ли расположенную на сфере карту можно раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета.

Вот карта графств Британии, раскрашенная четырьмя красками [Рис.1]

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

За первым ошибочным доказательством последовало множество других. Проблемой четырех красок занимались многие известные математики прошлого, но гипотеза не спешила раскрывать все свои секреты. После многих неудачных попыток доказать гипотезу для любого числа стран, математики решили доказать её, начиная с малых натуральных чисел. Так П. Франклин в 1913 году доказал гипотезу для карты в которой не более чем 25 стран, со временем он увеличил это число до 38.

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

Более ста лет математикам не удавалось получить доказательство. Лишь в 1976 К. Аппель и В. Хакен из Иллинойского университета смогли доказать гипотезу. Своего успеха они добились благодаря новаторскому шагу, – применение компьютера в доказательстве математической теоремы. Идея их доказательства состояла в следующем: сначала доказывается возможность раскраски для карт с числом n стран, ₀, затем с помощью компьютера подтверждается возможность раскраски карт и для₀. Потратив свыше тысячи часов машинного времени, перебрав громадное число вариантов, компьютер подтвердил справедливость гипотезы. Таким образом, вековая проблема четырех красок была решена.

Пытались решить эту проблему и наши соотечественники. Так, в 1964 году В. А. Горбатов предложил своё классическое, с его слов, доказательство проблемы. Но математическое сообщество никак не отреагировало на него, и не подтвердив его, и не опровергнув.

Я тоже попробовал самостоятельно раскрашивать карты, чтобы убедиться в том, что для раскраски любой конкретной карты хватает четырех красок. Вот, например, раскраска карты России, подтверждающая гипотезу Ф. Гутри, что карту можно раскрасить четырьмя красками. [Рис 2]

Раскрашивая карту, я обратил внимание и на то, что её нельзя раскрасить тремя красками. В самом деле, если рассмотреть четыре территории Чукотский автономный округ, Камчатский край, Республика Якутия, Магаданская область, то можно заметить, что Чукотский автономный округ, окружен только тремя этими территориями. Это значит, если территорию Чукотского округа покрасить первым цветом, то для покраски территорий Камчатского края, Республики Якутия, Магаданской области потребуется ещё три цвета.

2.2.Игра «4 краски»

Познакомившись с проблемой четырёх красок, известный американский популяризатор математики Стивен Барр придумал логическую игру на бумаге для двух игроков и бесхитростно назвал её «Четыре краски». Вот простые правила этой любопытной игры для двоих: Для этой игры нужны четыре цветных карандаша. Первый игрок начинает игру, рисуя произвольную пустую область. Второй игрок закрашивает её любым из четырёх цветов и в свою очередь рисует свою пустую область. Первый игрок закрашивает область второго игрока и добавляет новую область, и так далее — каждый игрок раскрашивает область соперника и добавляет свою. При этом области, имеющие общую границу, должны быть раскрашены в разные цвета. Проигрывает тот, кто на своём ходу вынужден будет взять пятую краску. Я познакомил с этой игрой своих одноклассников, и мы с удовольствием играем в эту игру в свободное время. Выигрышной стратегии мы пока не нашли, но некоторые тактические приёмы научились применять. На рисунке ниже приведена типичная картинка, которая остается после очередной игры «Четыре краски» [Рис 3]

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

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

Существуют также следующие вариации игры:

Карта заранее разбивается случайным образом на области различной величины, и каждый ход игры меняется игрок который закрашивает область, а также меняется цвет (в строгой последовательности). Таким образом каждый игрок закрашивает карту только двумя цветами, а в случае если не может закрасить так, чтобы области, имеющие общую границу были раскрашены в разные цвета. пропускает ход. Игра прекращается, когда ни один из игроков больше не сможет сделать ни одного хода. Выигрывает тот, у кого общая площадь закрашенных им областей больше.
Квадрат разбит на несколько квадратов (в основном 4x4), и его стороны окрашены в один из четырех цветов (каждый в разный цвет). Первым ходом закрашивается квадрат прилегающий к стороне, каждый последующий ход можно закрашивать тот квадрат, который прилегает к одному из закрашенных квадратов. Нельзя закрашивать квадрат теми цветами, которыми закрашен один из прилегающих к нему квадратов (в том числе и по диагонали) или прилегающая к квадрату сторона. Выигрывает игрок, делающий последний ход.

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

2.3.Задачи данной тематики

Задача 1. Раскрасьте эту карту из 100 стран в четыре цвета так, чтобы соседние страны были окрашены в разные цвета. Решение приведено на рисунке справа. [Рис 4] Задача 2. Рассмотрим все возможные карты на плоскости, образованные прямыми. Примером такой карты может служить обычная шахматная доска. Менее правильный узор изображен на рис.1 слева. Достаточно ли двух красок для раскрашивания всех таких карт?

Оказывается, достаточно, и доказать это нетрудно. На любой правильно раскрашенной карте интересующего нас типа проведем еще одну прямую (например, жирную прямую, как на рис.1 справа), разделив плоскость на две «карты». [Рис.5 Для раскраски любой карты, образованной прямыми, пересекающими всю ее поверхность от одного края листа до другого, достаточно двух красок]

Каждая из новых карт в отдельности раскрашена правильно, но к новой «границе» только что проведенной прямой примыкают пары областей, окрашенных в один и тот же цвет. Для того чтобы восстановить правильную раскраску всей карты в целом, нужно перекрасить одну из карт-половинок (какую именно — безразлично), изменив окраску каждой из областей на противоположную. То, что при этом получится, показано на рис. 1 слева. Карта над черной прямой «обращена» — перекрашена так, словно «отрицательные» области стали «положительными» и наоборот, и, как нетрудно видеть, вся карта раскрашена правильно.

Для завершения доказательства рассмотрим плоскость, разделенную на две области одной-единственной прямой. Такую карту, разумеется, можно раскрасить в два цвета. Проведем вторую прямую и раскрасим новую карту, переменив все цвета по одну сторону от новой прямой на противоположные. Затем проведем третью прямую и т. д. Ясно, что предложенный метод пригоден при любом числе прямых. Следовательно, «методом полной математической индукции» мы доказали теорему о возможности раскраски в два цвета всех карт, образованных прямыми на плоскости. Доказательство можно несколько обобщить на случай более разнообразных карт, например таких, как карта на рис. 2, образованная либо кривыми, пересекающими весь лист от одного края до другого, либо замкнутыми кривыми без самопересечений. [Рис.6. Двух красок достаточно для раскрашивания карты, образованной либо линиями, идущими от одного края листа до другого, либо замкнутыми кривыми].

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

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

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

Доказательство. Идею доказательства проведем для трёх окружностей с хордами, хотя все рассуждения можно обобщить на случай, когда на плоскости нарисовано n окружностей с хордами. Состоит она в следующем:

первая, малая окружность и её хорда разбивает плоскость на три части. Во всех областях первой части поставим по 0, во всех областях второй части поставим 1, во всех областях третьей части поставим 2 (рис.7.2);

вторая, средняя окружность и её хорда разбивает плоскость на три части. Во всех областях первой части поставим по 0, во всех областях второй части поставим 1, во всех областях третьей части поставим 2 (рис. 7.3);

третья, большая окружность и её хорда разбивает плоскость на три части. Во всех областях первой части поставим по 0, во всех областях второй части поставим 1, во всех областях третьей части поставим 2 (рис. 7.4).

При этом каждой области будет соответствовать три числа, найдем их сумму (рис. 7.5), и числа каждой области заменим остатком от деления его на 3 (рис.7. 6).

Области, у которых этот остаток равен 0, закрасим синей краской;

области, у которых этот остаток равен 1, закрасим желтой краской;

области, у которых этот остаток равен 2, закрасим красной краской.

Полученная таким образом раскраска (рис. 7.7) удовлетворяет условия задачи.

Заключение

Задача о четырех красках относится к самой элементарной ветви топологии, называемой «геометрией расположения». Это начало топологии, ее наглядная часть, поскольку современная топология гораздо более абстрактная и сложная, и не всякому студенту первого курса ее объяснишь. Задача же о четырех красках замечательна тем, что ее можно объяснить и первокласснику, и очень хочется нарисовать такую карту, для раскраски которой потребовалось бы пять цветов. Кстати, первоклассникам именно так и надо ставить задачу: не говорить им, что всегда достаточно четырех красок, а просить нарисовать карту, для которой четырех красок не хватает, и только спустя несколько дней сообщить, что это невозможно. Благодаря таким задачам любой человек с улицы сразу понимает, что математика очень элегантна. Ясное понимание несуществования чего-то — чисел ли с заданными свойствами, или способов построения геометрических фигур, или алгоритмов — создает особый дискурс, который можно было бы назвать культурой невозможного. И культура невозможного, и предпринимаемые математикой попытки познания бесконечного значительно расширяют горизонты мышления. Все это, ломая традиционный стереотип математики как сухой цифирии, создает ее образ как живой области знания.

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

Сами авторы доказательства сообщают: "Читатель должен разобраться в 50 страницах текста и диаграмм, 85 страницах с почти 2500 дополнительными диаграммами, 400 страницами микрофишей, содержащими еще диаграммы, а также тысячи отдельных проверок утверждений, сделанных в 24 леммах основного текста. Вдобавок читатель узнает, что проверка некоторых фактов потребовала 1200 часов компьютерного времени, а при проверке вручную потребовалось бы гораздо больше. Статьи устрашающи по стилю и длине, и немногие математики прочли их сколько-нибудь подробно".

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

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

Литература

Л. Беве, Любая карта на плоскости может быть раскрашена в четыре цвета, Квант, 1977 г., №1;
Е. Дынкин, В.Успенский, Математические беседы, М и Л, ГИТТЛ, 1952 г.;
А. А. Зыков. Основы теории графов. — М.: Вузовская книга, 2000. — С. 367—386.
Журнал //Наука и жизнь. – 1979. - № 3. – С.80
Методы четырехцветной раскраски вершин плоских графов. — М.: КомКнига, 2000. — 48 с. — 2005 экз. — ISBN 5-484-00127-7
Р.Курант, Г.Роббинс Что такое математика?
Самохин А. В. Проблема четырех красок: неоконченная история доказательства //СОЖ. — 2000. — № 7. — С. 91—96.
Родионов В. В. Методы четырехцветной раскраски вершин плоских графов. — М.: КомКнига, 2000. — 48 с. — 2005 экз. — ISBN 5-484-00127-7
Рингель Г. Теорема о раскраске карт / Перевод с английского В. Б. Алексеева. — М.: Мир, 1977. — 256 с. — книга с доказательством проблемы для всех поверхностей, кроме плоскости и сферы
И. Шарыгин, Л. Ерганжиева, Наглядная геометрия, 5-6 кл., М, Дрофа, 2007 г.