Исследовательская работа по математике на тему "Проблема четырех красок"

Научно-практическая конференция

Малой академии наук школьников г. Уфы

Секция: Прикладная математика

Исследовательская работа

Проблема четырех красок

Петрянкин Василий

МАОУ средняя общеобразовательная школа № 58

с углубленным изучением отдельных предметов,

8В класс

Научный руководитель:

учитель математики  Егорова Н.Т.

Уфа

Содержание

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

1. Основные свойства плоского графа……………………….….. 3

2. Применение формулы Эйлера для плоского графа...................6

3. Правила раскраски географических карт………………….….7

4. Проблема четырёх красок……………………………………….8

5. Заключение ………………………………………………………..9

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

7. Приложения……………………………………………………….11

Введение

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

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

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

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

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

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

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

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

Для реализации поставленной цели нами были выдвинуты задачи:

1.Рассмотреть основные свойства плоских графов.

2.Показать практическое применение формулы Эйлера для плоского графа..

3.Сформулировать правила и способы раскраски географических карт с помощью графов

4.Разработка сборника задач - головоломок.

1. Основные свойства плоского графа

Родоначальником теории графов считается  Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи о кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

К XVIII в. через реку Прегель, протекавшую по городу Кенигсберг (Калининград), было построено 7 мостов, которые связывали её берега с двумя островами, расположенными в черте города.  

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

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

 Решая задачу о семи мостах, Эйлер поступил следующим образом. Он изобразил точками B и C берега реки, точками A и  D острова, а линиями – мосты, соединяющие соответствующие участки берегов и островов. В результа­те получилась фигура, приведённая на рисунке 1.

Такую фигуру называют графом. Точки,  А, В, С, D называют вершинами графа, а линии,  соединяющие вершины,— дугами (ребрами) графа. Подсчитаем число дуг, исходящих из каждой вершины графа (рис. 1). Из вершин В, С и D исходит по три дуги, а из вершины А — пять дуг. Вершины графа, из ко­торых исходит нечетное число дуг,  называется нечетными вершинами, а вершины, из которых исходит четное число дуг,— четными.

Граф называется  связным, если любые две его вершины связаны какой – то цепью (граф не имеет ни одной изолированной вершины).

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

Рассмотрим следующие  свойства связного графа :

1.  Число нечетных вершин графа всегда четно.

 Невозможно начертить граф, который имел бы нечетное число нечетных вершин.

Рис.2

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

 

Рис.3

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

         Рассмотрим еще одну задачу, аналогичную задаче о семи мостов.

         Задача . Можно ли привязать к гвоздям А, В, С, D, К, Μ веревку так, как показано па рисунке 4, не разрезая ее на части и по сдваивая?

Рис. 4

         Решение. Из рисунка видно, что из вершин А, В, С и D исходят по три ребра, а из вершин Μ и К — по пять. Получили, что все шесть вершин нечётны. Согласно свойству 4, найденному Эйлером, привязать верёвку так, как требуется в условии задачи, невозможно.

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

           

Рис.5

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

                                

Рис.5

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

В следующих рисунках нарисованы уникурсальные графы: эскиз портрета Эйлера и  роспись Магомета (ПРИЛОЖЕНИЕ 1)

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

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

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

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

         Задача о поиске эйлерова цикла в графе имеет практическое значение. Например: Эйлеровы циклы применяются при составлении схемы одностороннего движения в городе.

2. Применение формулы Эйлера для плоского графа

Формула Эйлера.  Для любого плоского графа имеет место соотношение

В – Р + Г = 2,

где В – число вершин графа, Р – число ребер графа, Г – число граней графа.

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

  Предположим, что вся плоскость покрыта однородным графом, степень каждой вершины которого m, а грани которого – одноименные  n- угольники.

Выясним, при каких значениях  m и  n такое покрытие имеет место. Пусть В – число вершин графа, Р – число его ребер, Г – число его граней. Тогда mВ = 2Р, nГ = 2Р.

Поставив в формулу Эйлера (В – Р + Г = 2)  и , получим

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

.

Найдем подбором натуральные значения m  и n, 3удолвлетворяющие равенству : m₁ = 3  и n₁ = 6;  m₂ = 4  и n₂ = 4; m₃ = 6  и n₃ = 3.

Ясно, что других значений m и n.

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

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

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

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

                                                               Рис.6    

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

3. Правила раскраски географических карт

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

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

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

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

Рассмотрим проблему окраски карты подробнее.

Каждую географическую карту можно представить себе как  некоторый плоский  граф. Территории стран в этом случае будут служить гранями графа, границы стран – ребрами графа, а точки пересечения границ – вершинами графа. (ПРИЛОЖЕНИЕ  3)

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

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

Правило 1. Если карта на плоскости представляет собой эйлеровый граф, то его можно раскрасить всего двумя красками.  (ПРИЛОЖЕНИЕ 4)

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

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

На рисунках изображены графы соответствующие картам, которых можно раскрасить  тремя цветами:

                   

Например: Карту Северной Америки  можно раскрасить  тремя красками, если не учесть моря и океаны. (ПРИЛОЖЕНИЕ 5) 

Правило 3. Любую карту можно раскрасить пятью разными красками.

(ПРИЛОЖЕНИЕ 6)

4. Проблема четырех красок

Мы решили выяснить достаточно ли четырех красок для раскраски географической карты, состоящей из более 40 регионов.

Данная задача носит название задачи о четырех красках или проблема четырех красок. Впервые это математическая задача была предложена студентом лондонского университета Фрэнсисом  Гутри в 1852 году.

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

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

Попробуем проверить, с помощью графов, проблему четырех красок на картах Северной Америки, Южной Америки, Африки и Республики Башкортостан. Составим соответствующий  граф для каждой карты. (ПРИЛОЖЕНИЕ 5, 6, 7, 8, 9).

Для раскраски карт с помощью графов применим "жадный" алгоритм раскраски графа. Суть этого алгоритма состоит в следующем:  сначала мы пытаемся раскрасить как можно больше вершин в один цвет, затем закрашиваем во второй цвет также по возможности максимальное число оставшихся вершин, и т.д. При закраске вершин в новый цвет мы выполняем следующие действия: 1) Выбираем произвольную не закрашенную вершину и назначаем ей новый цвет; 2). Просматриваем список не закрашенных вершин и для каждой из них определяем, соединена ли она ребром с вершиной, уже закрашенной в новый цвет. Если не соединена, то к этой вершине также применяется новый цвет. Этот алгоритм назван "жадным" из-за того, что каждый цвет применяется к максимально большому числу вершин, без возможности пропуска некоторых из них или перекраски ранее закрашенных.

Используя «жадный» алгоритм для раскраски графов, раскрасим граф и соответствующую карту. Мы видим, что для любой карты достаточно четыре  цвета, чтобы правильно раскрасить карту. Чтобы раскрасить граф, соответствующий  карте Северной Америки, достаточно три цвета. Только страны Белиз и Сальвадор нужно красить третьим цветом. Чтобы покрасить граф, соответствующий карте Южной Америки необходимо четыре краски, хотя только одну страну (Аргентину) нужно красить четвертым цветом. Карту Республики Башкортостан, состоящую из 54 регионов также можно раскрасить четырьмя красками (хотя в литературе указывается, что четыре цвета достаточно только для карт, состоящих из 40 стран). Таким образом, мы выяснили наше предположение: для раскраски географической карты, состоящей из более 40 регионов достаточно  четырёх красок.

Заключение

«Мышление начинается с удивления» - заметил 2500 лет назад Аристотель. Наш современник Сухомлинский считал,  что «Чувство удивления – могучий источник желания знать: от удивления к знаниям – один шаг». А математика замечательный предмет для удивления. Именно это мы попытались показать, исследуя свойства графов, и показывая  применение графов при раскраске географических карт. В данной работе мы рассмотрели основные свойства плоских графов, доказали применение формулы Эйлера для покрытия плоскости одноимёнными многоугольниками при условии, что в каждой вершине сходятся одинаковое количество рёбер. А также мы показали правила и способы раскраски географических карт с помощью графов. Эти правила раскраски географических карт можно применить на уроках географии. Задача правильной  раскраски карты наименьшим количеством цветов развивает логическое мышление.  После исследования уникурсального графа составлены задачи – головоломки, которые можно использовать  на факультативных занятиях по математике.

Теория «раскраска графов» изучается в ВУЗах в дискретной математике и имеет большое практическое применение. Например:  «раскраска графов» применяется: при составлении расписаний уроков для образовательных учреждений;  планирование встреч, собраний, интервью; расписания движения  транспорта, в том числе — авиатранспорта; расписания для коммунальных служб.  С помощью раскраски графа можно решить задачи судоку. Раскраска в графах применяется при распределении памяти в ЭВМ, при проектировании сетей телевизионного вещания.

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

1. Вилинкин Н. Я., Шибасов Л. П., Шибасова З. Ф. За страницами учебника математики. — 1996.

2. Кордемский Б.А. Великие жизни в математике. – 1995.

3. Альхова З. Н., Макеева А. В. Внеклассная работа по математике. — 2001.

4. Новый справочник школьника: Универсальное пособие. — 2003. — Т. 2.

5. Смирнова И. М. В мире многогранников. — 1995.

6. Виленкин Н. Я. За страницами учебника математики.

7. Саркисян А.А., Колягин Ю.М. Познакомьтесь с топологией (на подступах к топологии). – 1976

8. Энциклопедия школьника по математике. – 2000.

9. Величко М.В. Проектная деятельность учащихся. - 2006.

ПРИЛОЖЕНИЕ 1

Эскиз портрета Эйлера

Знак, состоящий из двух рогов Луны который Магомет описывал одним росчерком (он был неграмотным)

ПРИЛОЖЕНИЕ 2

 

ПРИЛОЖЕНИЕ 3

Граф к картам

                     

ПРИЛОЖЕНИЕ 4

Эйлеровы графы

ПРИЛОЖЕНИЕ 5

Раскраска карты Северной Америки

ПРИЛОЖЕНИЕ 6

Раскраска карты Республики Башкотостан пятью красками  

                                        

ПРИЛОЖЕНИЕ 7

Раскраска карты Южной Америки

ПРИЛОЖЕНИЕ 8

Раскраска карты Африки четырьмя красками

             

ПРИЛОЖЕНИЕ 9

Раскраска  карты Республики Башкортостан четырьмя красками