Исследовательский проект "Теория графов. Проблема четырех красок"

Государственное бюджетное профессиональное образовательное учреждение "Нижегородский строительный техникум" ПРОЕКТ «Теория графов. Проблема четырех красок» Выполнил: студентка гр.№352 Резунова Ирина Руководитель: Борисова Е.В г. Нижний Новгород 2016 год 1 Оглавление Введение. ....................................................................................... ............2 1. Теория графов.........................................................................................3 1. 1. Основные свойства плоского графа...................................................3 1.2. Применение формулы Эйлера для плоского графа..........................7 2. Правила раскраски географических карт.............................................. 9 2.1.Проблема окраски………........................................................................10 3. Проблема четырех красок......................................................................12 4.Карта Нижегородской области в четырех красках…..............................17 Заключение…………………………………………………………………… …………………………22 Список литературы:.................................................................................... ..23 2 Введение В последнее время теория графов стала простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. Это проблемы проектирования интегральных схем и схем управления, исследования логических цепей, блок – схем программ, экономики и статистики, химии и биологии, теории расписаний и дискретной математики. Многие учащиеся, окончив школу, не имеют никакого представления о том, что такое графы, не умеют работать с этим математическим понятием и не могут применять их при решении логических задач. Между тем, умение применять графы даёт возможность решать нестандартные задачи оригинальным и в то же время простым и удобным способом. Это и побудило выбрать нас выбрать тему работы: «Теория графов.Проблема четырёх красок» Актуальность темы заключается в том, что благодаря применению теории графов открывается широкая возможность использования оригинальных, но в то же время очень простых способов решения задач олимпиадного и занимательного уровня. Целью исследовательской работы является изучить правила раскрашивания географических карт и опытно – экспериментальным путем проверить задачу четырёх красок. Задачами работы в связи с указанной целью являются:рассмотреть основные свойства плоских графов и познакомиться с решением задачи о 7 мостах.Показать практическое применение формулы Эйлера для плоского 3 графа и с помощью этой формулы доказать задачу о возможности покрыть плоскость одноименными многоугольниками.Сформулировать правила и способы раскраски географических карт с помощью графов, проанализировать гипотезу английского математика Артура Кели.Рассказать о проблемах окраски карт,о проблеме четырех красок.Так же в ходе работы была рассмотрена окраска карт разных частей света и мною составлен граф для карты Африки,Европы,Нижегородской области и самостоятельно раскрашена карта Европы(пятью красками) ,Нижегородская область(четырьмя красками) и Африка. 1.Теория графов 1.1. Основные свойства плоского графа Теория графов-раздел дискретной математики изучающий свойства графов.Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи о кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. К XVIII в. через реку Прегель, протекавшую по городу Кенигсберг (Калининград), было построено 7 мостов, которые связывали её берега с двумя островами, расположенными в черте города.Рассказывают, что однажды один из жителей города спросил у своего соседа, сможет ли он пройти по всем мостам так, чтобы на каждом из них побывать лишь один раз и вернуться к тому мосту, откуда начал прогулку. Этой задачей заинтересовались многие, однако решить её никто из жителей города так и не смог. 4 В дальнейшем задача привлекла внимание ученых разных стран. Решить её удалось в 1736г. известному швейцарскому математику Леонарду Эйлеру, который в то время работал в Петербурге и не приезжал в Кенигсберг. Причём Л.Эйлер не только решил эту задачу, но и сумел найти общий метод решения аналогичных задач. Решая задачу о семи мостах, Эйлер поступил следующим образом. Он изобразил точками B и C берега реки, точками A и D острова, а линиями – мосты, соединяющие соответствующие участки берегов и островов. В результате получилась фигура, приведённая на рисунке 1. Такую фигуру называют графом. Точки, А, В, С, D называют вершинами графа, а линии, соединяющие вершины,— дугами (ребрами) графа. Подсчитаем число дуг, исходящих из каждой вершины графа (рис. 1). Из вершин В, С и D исходит по три дуги, а из вершины А — пять дуг. Вершины графа, из которых исходит нечетное число дуг, называется нечетными вершинами, а вершины, из которых исходит четное число дуг,— четными. 5 рис.1 Граф называется связным, если любые две его вершины связаны какой – то цепью (граф не имеет ни одной изолированной вершины). Граф, который можно начертить на плоскости так, чтобы ребра его пересекались только в вершинах, называется плоским графом. Рассмотрим следующие свойства связного графа : 1. Число нечетных вершин графа всегда четно. Невозможно начертить граф, который имел бы нечетное число нечетных вершин. рис.2 2. Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком. 6 рис.3 3. Граф только с двумя нечётными вершинами можно начертить одним росчерком, при этом движение нужно начать с одной из этих нечётных вершин и закончить в другой. рис.4 4. Если все вершины графа чётные, то можно одним росчерком (т. е. без отрыва карандаша от бумаги, проводя по каждой дуге только один раз) начертить граф, при этом движение можно начать с любой вершины и закончить его в той же вершине. рис.5 Граф, которую можно начертить одним росчерком (без отрыва карандаша от бумаги и без повторения движения по каждой из ребер), называется уникурсальным графом. 7 Роспись Магомета(Знак, состоящий из двух рогов Луны) рис.6 Связный граф уникурсален тогда и только тогда, когда степени всех его вершин четны или у него ровно две вершины нечетной степени. Граф называется эйлеровым, если для всякой вершины графа найдется маршрут начинающейся и заканчивающейся в этой вершине и проходящий через каждое ребро только один раз. Такой маршрут называется эйлеровым циклом. Граф является эйлеровым тогда и только тогда, когда степени всех его вершин четные. Задача о поиске эйлерова цикла в графе имеет практическое значение. Например: Эйлеровы циклы применяются при составлении схемы одностороннего движения в городе. 1.2. Применение формулы Эйлера для плоского графа Формула Эйлера. Для любого плоского графа имеет место соотношение В – Р + Г = 2, где В – число вершин графа, Р – число ребер графа, Г – число граней графа. 8 С помощью данной формулы можно доказать задачу о возможности покрыть плоскость одноименными многоугольниками при условии, что в каждой вершине сходятся одинаковое число ребер (сторон). Предположим, что вся плоскость покрыта однородным графом, степень каждой вершины которого m, а грани которого – одноименные n- угольники. Выясним, при каких значениях m и n такое покрытие имеет место. Пусть В – число вершин графа, Р – число его ребер, Г – число его граней. Тогда mВ = 2Р, nГ = 2Р. Поставив в формулу Эйлера (В – Р + Г = 2)В=nr/m и P=nr/2n получимr=4m/2m+2n-nm Так как данный однородный граф покрывает всю плоскость, то множество его граней бесконечно. Грубо говоря, можно считать, что выражение2m+2n-nm,при стремлении к 0. Для упрощения примем 2m+2n-nm=0 . Преобразуя последнее равенство, получим: (m-2)(n-2)=4 Найдем подбором натуральные значения m и n, 3удолвлетворяющие равенству: (m-2)(n-2)=4 m1 = 3 и n1 = 6; m2 = 4 и n2 = 4; m3 = 6 и n3 = 3. Ясно, что других значений m и n. Итак, если данный однородный граф покрывает всю плоскость, то грани его либо треугольники, либо четырехугольники, либо шестиугольники. Отсюда следует, что для того, чтобы однородным графом можно было покрыть всю плоскость, он должен иметь грани или треугольные, или четырехугольные, или шестиугольные. Степенью вершины графа называется число ребер, исходящих из каждой вершины. Если степени вершин однородного графа равны трем, то всю плоскость можно покрывать только шестиугольниками; если 9 степени вершин равны четырем, то грани его должны быть четырехугольниками; если степени вершин равны шести, то все его грани должны быть треугольниками. .7 Данная задача имеет практическое применение при составлении различных рисунков паркетного пола, декоративного панно, а также при раскрашивании географических карт. рис 10 2. Правила раскраски географических карт Кажется, нет ничего проще, чем раскрасить политическую контурную географическую карту. Для этого достаточно окрасить одну из изображенных на ней стран, а затем граничащие с ней страны окрашивать в другой цвет. Однако, если ограничить число цветов, которые при этом можно использовать, задача значительно усложняется. Еще более сложной будет задача об определении по чистой контурной карте минимального числа цветов, с помощью которых можно правильно раскрасить данную карту. Это весьма интересная математическая задача топологического характера, имеющая практическое применение. Аналогичные задачи возникают при раскрашивании тканей, составления различных рисунков в живописи и т.д. Задача раскрашивания карты различным числом красок привлекала многих математиков. Так в 1879 г. английский математик Артур Кели на заседании английского географического общества высказал гипотезу о том, что любую географическую карту можно раскрасить четырьмя красками так, что соседние страны будут окрашены в разные цвета. Но подтвердить или опровергнуть эту гипотезу до сих пор никому не удалось. Однако при попытках решить эту задачу математики сумели решить ряд других задач, связанных с раскрашиванием карты. 11 2.1.Рассмотрим проблему окраски карты подробнее Каждую географическую карту можно представить себе как некоторый плоский граф. Территории стран в этом случае будут служить гранями графа, границы стран – ребрами графа, а точки пересечения границ – вершинами графа. рис.8 Кроме того, будем считать, что каждая страна на карте представлена единой связной областью. Раскраска карт считается правильной, если страны, имеющие общую границу раскрашены в разные цвета. При решении задачи об определении по чистой контурной карте минимального числа цветов, с помощью которых можно правильно раскрасить данную карту, можно воспользоваться следующими правилами: 12 Правило 1. Если карта на плоскости представляет собой эйлеровый граф, то его можно раскрасить всего двумя красками. Практически окрасить подобную карту можно так: сначала окрасить одну ее область, затем окрасить тем же цветом все области, имеющие с ней только одну общую точку. После этого окрасить другим цветом область, имеющую с первоначальной общую границу, и продолжить раскрашивание так же, как и в первом случае. Не следует начинать окраску карты одновременно с двух мест, так как «стыковка» окрашенных областей может не получиться. Правило 2. Если в каждой вершине соответствующего карте графа сходятся три ребра, то такую карту можно правильно раскрасить тремя красками в том и только в том случае, если каждая страна имеет четное число границ. Например: Карту Северной Америки можно раскрасить тремя красками, если не учесть моря и океаны. 13 Рис.9 Правило 3. Любую карту можно раскрасить пятью разными красками. рис.11 Африка. 14 15 3. Проблема четырех красок Мы решили выяснить достаточно ли четырех красок для раскраски географической карты, состоящей из более 40 регионов. Данная задача носит название задачи о четырех красках или проблема четырех красок. Впервые это математическая задача была предложена студентом лондонского университета ФрэнсисомГутри в 1852 году. Задачу о четырех красках можно представить и несколько иначе. Рассмотрим для произвольной карты следующий граф: его вершины – столицы государств, а ребрами связаны те из них, которые имеют общий участок границы. Для полученного графа задача формулируется так: раскрасить его вершины, используя только четыре краски, чтобы при этом две вершины, которые соединены ребром, были разного цвета. Хроматическим числом графа называется наименьшее количество красок, с помощью которых можно так раскрасить вершины графа, что любые две вершины, соединённые ребром, окрашиваются при этом в разные цвета. Данная задача сведётся к следующей: верно ли, что хроматическое число любого графа, расположенного на плоскости не больше четырех? Попробуем проверить, с помощью графов, проблему четырех красок на картах Южной Америки и Африки. Составим соответствующий граф для каждой карты. рис.10 Южная Америка(состоит из треугольников) 16 17 Для раскраски карт с помощью графов применим "жадный" алгоритм раскраски графа. Суть этого алгоритма состоит в следующем: сначала мы пытаемся раскрасить как можно больше вершин в один цвет, затем закрашиваем во второй цвет также по возможности максимальное число оставшихся вершин, и т.д. При закраске вершин в новый цвет мы выполняем следующие действия: 1) Выбираем произвольную не закрашенную вершину и назначаем ей новый цвет; 2). Просматриваем список не закрашенных вершин и для каждой из них определяем, соединена ли она ребром с вершиной, уже закрашенной в новый цвет. Если не соединена, то к этой вершине также применяется новый цвет. Этот алгоритм назван "жадным" из-за того, что каждый цвет применяется к максимально большому числу вершин, без возможности пропуска некоторых из них или перекраски ранее закрашенных. 18 Используя «жадный» алгоритм для раскраски графов, раскрасим граф и соответствующую карту. Мы видим, что для любой карты достаточно четыре цвета, чтобы правильно раскрасить карту. 4.Карта Нижегородской области в четырех красках Я решила составить граф и раскрасить Нижегородскую область четырьмя красками. Применим для Нижегородской три правила раскраски карт: Первое правило не подходит, так как в Нижегородской области 42 района. Второе правило не подходит, потому что каждый город имеет нечетное число границ. Третье правило(любую карту можно раскрасить пятью красками). 19 20 рис.12 21 рис.13 22 23 рис.14 24 Заключение Именно это мы попытались показать, исследуя свойства графов, и показывая применение графов при раскраске географических карт. В данной работе мы рассмотрели основные свойства плоских графов, доказали применение формулы Эйлера для покрытия плоскости одноимёнными многоугольниками при условии, что в каждой вершине сходятся одинаковое количество рёбер. А также мы показали правила и способы раскраски географических карт с помощью графов. Эти правила раскраски географических карт можно применить на уроках географии. Задача правильной раскраски карты наименьшим количеством цветов развивает логическое мышление. Теория «раскраска графов» изучается в ВУЗах в дискретной математике и имеет большое практическое применение. Например: «раскраска графов» применяется: при составлении расписаний уроков для образовательных учреждений; планирование встреч, собраний, интервью; расписания движения транспорта, в том числе — авиатранспорта; расписания для коммунальных служб. С помощью раскраски графа можно решить задачи судоку. Раскраска в графах применяется при распределении памяти в ЭВМ, при проектировании сетей телевизионного вещания. 25 Список литературы: 1. Год: 1996 Автор: Н.Я. Виленкин, Л.П. Шибасов, З.Ф.Шибасова. Издательство: М.: Просвещение: АО "Учеб. лит".. 2. Петрянкин Василий http://infourok.ru/ [электронный ресурс]Исследовательская работа- «Проблема четырех красок» 3.Свободная энциклопедия Википедия,статья «Теория графов» [электронный ресурс]https /Теория графов / wiki :// ru . wikipedia . org 26 Пояснительная записка В последнее время теория графов стала простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. Это проблемы проектирования интегральных схем и схем управления, исследования логических цепей, блок – схем программ, экономики и статистики, химии и биологии, теории расписаний и. дискретной математики. Целью исследовательской работы является изучить правила раскрашивания географических карт и опытно – экспериментальным путем проверить задачу четырёх красок. Задачами работы в связи с указанной целью являются:рассмотреть основные свойства плоских графов и познакомиться с решением задачи о 7 мостах.Показать практическое применение формулы Эйлера для плоского графа и с помощью этой формулы доказать задачу о возможности покрыть плоскость одноименными многоугольниками.Сформулировать правила и способы раскраски географических карт с помощью графов, проанализировать гипотезу английского математика Артура Кели.Рассказать о проблемах окраски карт,о проблеме четырех красок.Так же в ходе работы была рассмотрена окраска карт разных частей света и мною составлен граф для карты Африки,Европы,Нижегородской области и самостоятельно раскрашена карта Европы(пятью красками) и Нижегородская область(четырьмя красками). Список литературы: 1. Год: 1996 Автор: Н.Я. Виленкин, Л.П. Шибасов, З.Ф.Шибасова. Издательство: М.: Просвещение: АО "Учеб. лит".. 2. Петрянкин Василий http://infourok.ru/ [электронный ресурс]Исследовательская работа- «Проблема четырех красок» 27 3.Свободная энциклопедия Википедия,статья «Теория графов» [электронный ресурс]https://ru.wikipedia.org/wiki/Теория графов 28