какая зависимость существует между четырьмя цветами

Чему нас может научить теорема о четырех красках в разработке ПО

Теорема о четырёх красках — это математическая формулировка, связанная с картами. Все примеры карт, которые я нашёл в Интернете, были слишком сложными для введения, поэтому я набросал собственный неказистый рисунок:

Если посмотреть под другим углом, то можно воспринимать её как граф — достаточно ужать все области до кругов и соединить круги, соответствующие соседним областям карты:

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

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

Первое, что поразило меня, как разработчика ПО: четыре цвета — это совсем мало. Кажется поразительным, что любой граф можно раскрасить всего четырьмя цветами; мне кажется, что если я нарисую графы некоторых из кодовых баз, с которыми я работал, где рёбрами будут соединены обменивающиеся данными объекты, то им запросто может потребоваться дюжина цветов.

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

Поэтому можно сделать так:

Сложность

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

Второй граф интуитивно кажется более сложным, или, по крайней мере, менее упорядоченным. Существует конкретный измеряемый способ оценки его сложности: для его раскраски требуется больше цветов. Для второго графа требуется четыре цвета, для первого — всего два. Почему?

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

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

как и количество элементов в графе:

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

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

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

В первом графе я использовал узел 3 для соединения со вторым графом; узел 3 является как-бы «интерфейсом» ромба, ограничивая доступ к нему. Благодаря следованию этому паттерну сложность графа не увеличивается.

Во втором графе узлы 1, 2 и 4 имеют соединения с более крупным подграфом. В этом случае нет одного узла, ограничивающего доступ к ромбу; более крупный граф имеет возможность соединяться с несколькими узлами в ромбе. Это привело к увеличению сложности всей системы. Кроме того, сложность каскадно распространилась на бо́льшую часть системы — я не могу изменить только один из цветов узла, а должен распространить изменения на бо́льший подграф.

Разработка ПО

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

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

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

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

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

Источник

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

Содержание

Общие идеи доказательства [ править ]

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

Теперь, если есть грань, образованная нашим планарным графом, не являющаяся треугольником, мы можем добавлять ребра без внедрения новых вершин до тех пор, пока все грани не станут треугольниками. Если полученный граф является раскрашиваемым в не более чем [math]4[/math] цвета, то и исходный граф раскрашиваем так же (так как удаление ребер не увеличивает хроматическое число). Поэтому достаточно доказать теорему для триангулированных графов, и без потери общности мы предполагаем, что граф триангулирован.

Для дальнейших рассуждений нам понадобится следующее утверждение:

\nexists [/math] [math]v \in V[/math] : [math]deg(v) \leqslant 4[/math]

Приведем пример нахождения неизбежной конфигурации:

Источник

Научно-исследовательская работа » Проблема 4 красок»

Выбранный для просмотра документ Король.doc

НАУЧНО-ПРАКТИЧЕСКАЯ КОНФЕРЕНЦИЯ УЧАЩИХСЯ

ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

Выполнила: ученица 9 «Б» класса

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

математики Хатунцева И.В.

Глава 1. Понятие проблемы четырех красок………………………………….4

Глава 3. Теоремы о числе необходимых красок…. ………………………….8

Глава 4. Применение в играх и задачах……………………………………….11

Список использованной литературы………..………………………………. 16

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

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

Этой теме посвящено много литературы. Об этом писал Мартин Гардер, рассказывая о разнообразных применениях проблемы четырех красок.

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

Глава 1. Понятие проблемы четырех красок.

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

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

В 1913 году эта теорема было доказана для 25 стран, через год для 38. Но проблема становилась совершенно непреступной с лавинообразным увеличением числа стран.

Глава 2. Что такое «карта»?

Конечно, все это звучит умно и красиво, но, начиная разбирать эту проблему, сначала стоит пояснить, что же такое «карта».

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

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

Итак, посмотрим, какие бывают карты.

Иногда к многоугольной карте в качестве дополнительных стран присоединяют одну или несколько внешних бесконечных областей плоскости ограниченных сторонами исходного многоугольника и лучами. Пример такой карты приведен на рисунке. Новые страны помечены цифрами 1,2,3,4

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

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

Глава 3. Теоремы о числе необходимых красок

В ходе раскрашивания различного вида карт были сделаны следующие выводы.

Если в каждой вершине карты сходится четное число ребер, то нам понадобиться 2 краски

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

А) 3 краски

Б) 4 краски

Если карта образованна двумя концентрированными окружностями с некоторым количество перегородок, то:

Б) Если количество перегородок является нечетным числом, то потребуется 4 краски.

Глава 4. Применение проблемы в играх и задачах

Познакомившись с проблемой красок, математик Стивен Барр придумал логическую игру для двух игроков названную «Четыре краски». По словам Мартина Гарднера — «Я не знаю лучшего способа понять трудности, которые встречаются на пути решения проблемы четырёх красок, чем просто поиграть в эту любопытную игру»

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

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

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

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

Раскрасьте эту карту из 100 стран в четыре цвета так, чтобы соседние страны были окрашены в разные цвета. Решение приведено на рисунке снизу.

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

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

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

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

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

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

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

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

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

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

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

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

Источник

СОДЕРЖАНИЕ

Точная формулировка теоремы

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

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

История

Ранние попытки доказательства

«FG», возможно, один из двух Гатри, опубликовал вопрос в The Athenaeum в 1854 году, и Де Морган снова поставил вопрос в том же журнале в 1860 году. Другая ранее опубликованная ссылка Артура Кейли ( 1879 ), в свою очередь, подтверждает гипотезу Де Морган.

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

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

В 1890 году, помимо выявления изъяна в доказательстве Кемпе, Хивуд доказал теорему о пяти цветах и обобщил гипотезу о четырех цветах на поверхности произвольного рода.

Доказательство на компьютере

В 1960-х и 1970-х годах немецкий математик Генрих Хееш разработал методы использования компьютеров для поиска доказательства. Примечательно, что он был первым, кто использовал разрядку для доказательства теоремы, которая оказалась важной в части неизбежности последующего доказательства Аппеля – Хакена. Он также расширил концепцию сводимости и вместе с Кеном Дарре разработал для нее компьютерный тест. К сожалению, в этот критический момент он не смог выделить необходимое суперкомпьютерное время для продолжения своей работы.

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

Упрощение и проверка

Резюме идей доказательства

Следующее обсуждение представляет собой краткое изложение, основанное на введении в « Каждую планарную карту можно раскрашивать в четыре цвета» ( Аппель и Хакен, 1989 ). Первоначальное предполагаемое доказательство Кемпе теоремы о четырех цветах, хотя и ошибочно, предоставило некоторые из основных инструментов, которые позже использовались для ее доказательства. Объяснение здесь переформулировано в терминах современной формулировки теории графов, приведенной выше.

Вспомните формулу выше:

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

Ложные опровержения

Теорема четырех цветов была известна тем, что за свою долгую историю привлекла большое количество ложных доказательств и опровержений. Сначала The New York Times отказалась из соображений политики опубликовать доказательство Аппеля-Хакена, опасаясь, что доказательство окажется ложным, как и предыдущие ( Wilson 2014 ). Некоторые предполагаемые доказательства, такие как упомянутые выше Кемпе и Тейта, находились под пристальным вниманием общественности более десяти лет, прежде чем были опровергнуты. Но многие другие, написанные любителями, вообще никогда не публиковались.

Источник

• ← коды в хиро мания
• коды на рисунки в роблоксе →