13.04.2014

Решение Задачи о четырех красках

Решение Задачи о четырех красках


1. Условие

Дано: карта со странами.

Требуется: раскрасить страны в наименьшее количество цветов (красок).

Гипотеза: любую карту можно раскрасить, используя не более 4 (четырех) различных цветов (красок).

Требуется: доказать или опровергнуть данную гипотезу.


2. План доказательства

  1. Условие;
  2. План доказательства;
  3. Формализация условия;
  4. Главная идея доказательства;
  5. Доказательство;


3. Формализация условия

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

Опр.: Границей Страны называется объединение кривых ограничиваемых данную страну.

Примечание: Количество замкнутых кривых, их длина и площадь области (страны) должны быть конечными величинами.

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

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

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

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

Опр.: Соседними Странами на карте называютя Страны, имеющие общий участок границы.

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

Опр.: Раскраской Карты является такая пометка каждой Страны из множества пометок M, такая что любые (или каждые) две соседние страны на карте имеют разные пометки.

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

Опр.: Графом G(V,E) называется совокупность двух конечных множеств - непустого множества V (множества вершин) и множества E двухэлементных подмножеств множества V (E - множество ребер).

Опр.: Если задана функция F: V -> M и/или F: E -> M, то множество M называется множеством Пометок, а граф называется Помеченным (или Нагруженным). В качестве множества пометок обычно используются буквы или целые числа. Если функция F инъективна, то есть разные вершины (рёбра) имеют разные пометки, то граф называется Нумерованным.


4. Главная идея доказательства

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

Проблемы раскраски карты на глобусе и плоскости эквивалентны.
Действительно, в случае карты на сфере можно вырезать кусок внутренней области какой-либо страны; продырявленную сферу можно деформировать (растянуть) в плоскую область - представим, что карта сделана из тонкой резины. На плоской карте отверстие превратится в "океан", омывающий со всех сторон одну страну. Разумеется, длины границ, их форма, размеры стран подвергнутся при растяжении значительным изменениям, но сетка границ останется, добавится лишь растянутая граница прорезанного отверстия, внешняя граница океана. Её можно убрать, то есть раскрасить океан так же, как и окруженную им страну. Такие деформации стран и их границ, очевидно, не меняют задачи раскраски. Ниже рассматривается плоская карта.

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

Опр.: Полным графом с n вершинами (или коротко полным n-графом или n-полным графом) называется такой граф, у которого каждые (или любые) две вершины соединены ребром. Такой граф принято обозначать Kn, где n - количество вершин полного графа.

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

Опр.: Подграфом называется граф G|(V|,E|), где V| ⊆ V и/или E| ⊆ E.

Примечание: Отметим, что в плоском графе не допускаются петли (ребро, имеющие началом и концом одну и ту же вершину).

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

Примечание: На самом деле задача о раскраске плоской карты это всего лишь вершина айсберга задач о раскраске, ведь раскрашивать можно не только плоские фигуры, но и отрезки (ребра графа), и объемные фигуры (тела) и даже n-мерные фигуры. Причем n-мерные фигуры можно раскрашивать на поверхности n+k-мерной фигуры, также как грани в многограннике. Более того, вся сложность данного класса задач о раскраске заключается скорее в определении свойств графов, получаемых при переходе к эквивалентной задачи, то есть непосредственно от карты к графу. На данный момент мы знаем, какие классы подграфов не должен содержать планарный граф, но для более изысканных графов доказательство аналогичное Теореме Понтрягина-Куратовского может быть на порядок сложнее.


Теорема Кёнига о двудольном графе

Формулировка: В графе все циклы четные тогда и только тогда, когда граф является двудольным.

Опр.: Двудольный Граф - это Граф, все вершины которого разбиты на две доли (части или непересекающиеся подмножества множества вершин V V1 V2 которые удовлетворяют условиям: V1 ∩ V2 = ∅ и V1 ∪ V2 = V), а ребра проходят только между вершинами из разных доль.

Опр.: Ребром (или кликой 2) в графе называется подграф K2.

Опр.: Говорят, что в графе вершина инцидентна ребру или наоборот, если данная вершина является подграфом данного ребра.

Опр.: Говорят, что в графе две вершины смежные, если они соеденины ребром.

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

Опр.: Маршрутом (путем) в графе называется чередующаяся последовательность вершин и ребер v0,e1,v1,e2,v2, ... ,ek,vk, где элементы vi из множества вершин V графа, а ei из множества ребер E графа, в которой любые два соседних элемента Инцидентны.

Опр.: Если v0 = vk, то Маршрут Замкнут, иначе Открыт.

Опр.: Если все ребра различны, то Маршрут называется Цепью.

Опр.: Если все вершины (а значит и ребра) различны, то Маршрут называется Простой Цепью.

Опр.: Замкнутая Цепь называется Циклом.

Опр.: Замкнутая Простая Цепь называется Простым Циклом.

Опр.: Граф без циклов называется Ацикличным.

Опр.: Связанный граф без циклов называется Деревом.


Доказательство теоремы Кёнига

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

Необходимость. Если граф несвязаный, то проведем доказательство отдельно для каждой компоненты. Пусть граф связаный и все циклы в нем четные. Выделим произвольную вершину v0 и найдем произвольные цепи между v0 и всеми остальными вершинами (например, самые короткие алгоритмом Дейкстра). Если одна цепь (v0,vi) нечетной длины, то и любая цепь (v0,vi) нечетная, иначе бы эти цепи образовали нечетный цикл. Аналогично, если (v0,vi) - четная, то и любая (v0,vi) - четная. Разобъем вершины на две доли: в одну войдет вершина v0 и все, находящиеся от v0 на четном расстоянии; в другую долю поместим все вершины, находящиеся от v0 на нечетном расстоянии. Если вершины u1 и u2 принадлежат одной доле, то между ними не может быть ребра, иначе это ребро вместе с цепями (v0,u1) и (v0,u2) образовали бы нечетный цикл. Ч.т.д.

Примечание: Поскольку данная теорема доказана, то можно изменить условие теоремы на равносильное, чтобы показать суть теоремы. Смысл данной теоремы сводится к тому, что для определения двудольности графа необходимо и достаточноопределить двудольность определенных классов подграфов, которые в данном случае являются циклами. То есть если в графе все циклы являются двудольными, то и сам граф тоже является двудольным. Также заметим, что циклы графа вполне однозначно могут быть раскрашены в два цвета при заданной начальной раскраске любого подграфа цикла K2 (полного графа с двумя вершинами), в случае если данный цикл двудольный. Подробнее об эквивалентности задач раскраски и дольности смотреть в Лемме №1 ниже.


5. Доказательство

Опр.: N-дольный Граф - это Граф, все вершины которого разбиты на n доль (частей или непересекающихся подмножест множества вершин V V1,V2, ... ,Vn, которые удовлетворяют условиям: Vi ∩ Vj = ∅, 1 ≤ i,j ≤ n, i ≠ j и V1 ∪ V2 ∪ ... ∪ Vn = V), а ребра проходят только между вершинами из разных доль.

Лемма №1: Задача раскраски графа в наименьшее количество цветов и задача определения наименьшей дольности графа являются эквивалентными. И действительно, пусть дан граф, у которого наименьшее количество доль равно n, тогда данный граф можно раскрасить в наименьшее количество цветов также равное n (то есть вершины в каждой доли можно раскрасить в один цвет, поскольку они не являются смежными). В противном случае, если раскраска в наименьшее количество цветов возможна, то есть в n-k цветов, где n,k ∈ N, тогда вершины данного графа можно разбить на доли в соответствии с цветами (вершины, раскрашенные в одинаковые цвета можно поместить в одну долю, а в разные цвета соответственно в разные доли). Поскольку вершины, раскрашенные в одинаковые цвета не смежные, то ребер между вершинами в одной доли не будет. И так как количество доль в графе уменьшилось на k, то это будет противоречить начальному условию, что данный граф емеет наименьшее количество доль равное n. В обратную сторону эквивалентность этих задач доказывается также легко, и не стоит пристального внимания.

Во многих случаях решению задачи способствует введение новых терминов. Единственное что необходимо для доказательства теоремы о n-дольном графе это соблюдать аналогию с теоремой Кенига. Как уже было описано выше, в примечании к теореме Кенига, для проверки графа на двудольность было необходимо и достаточно проверить лишь определённые классы подграфов (в теореме Кенига данные классы подграфов являются циклами), которые в случае положительного результата проверки можно однозначно раскрасить в два цвета при заданной начальной раскраске K2 подграфа. И так по аналогии с теоремой Кенига нам необходимо придумать некие классы подграфов после проверки, которых можно будет судить о n-дольности графа в целом. Также можно предположить, что данные классы пдграфов в случае положительного результата проверки на n-дольность будут однозначно раскрашивать в n-цветов и состоять из Kn. Попробуем развить данное предположение в описанной ниже терминологии.

Опр.: Если элементами множества E являются не обязательно двухэлементные, а любые подмножества множества V, то такие элементы множества E называются Гипердугами, а Граф называется Гиперграфом.

Опр.: Ребром, состоящим из Kn, просто Kn-ребром или Ребром Kn (или кликой n или гипердугой n) в Графе называется подграф Kn.

Опр.: Говорят, что в Графе вершина инциндентна ребру Kn (клика) или наоборот, если данная вершина является подграфом данного ребра Kn.

Опр.: Говорят, что в Графе ребро Kn (клика) инциндентно ребру Kn+1 (клике) или наоборот, если данная ребро Kn (клика) является подграфом данного ребра Kn+1 (клике).

Опр.: Говорят, что в Графе два Ребра Kn (клики) смежные, если у них есть общее Ребро Kn-1 (клика).

Опр.: Маршрутом Kn (Путем Kn) Графа называется чередующаяся последовательность ребер Kn и ребер Kn-1 kn,0,kn-1,1,kn,1,kn-1,2,kn,2, ... ,kn-1,l,kn,l, где элементы kn,i из множества Ребер Kn Графа, а kn-1,i из множества ребер Kn-1 Графа, в которой любые два соседних элемента Инцидентны.

Опр.: Если kn,0 ∩ kn,l ≠ ∅ (пересечение множества вершин из начального ребра Маршрута Kn и конечного ребра Маршрута Kn не пустое), то Маршрут Kn Замкнут, иначе Открыт.

Опр.: Если все наборы Ребер Kn+1 различны, то Маршрут Kn называется Цепью Kn.

Опр.: Если все наборы Ребер Kn различны (а значит и наборы Ребер Kn+1), то Маршрут Kn называется Простой Цепью Kn.

Опр.: Замкнутая Цепь Kn называется Циклом Kn.

Опр.: Замкнутая Простая Цепь Kn называется Простым Циклом Kn.

Опр.: Граф без Циклов Kn называется Ацикличным относительно Kn.

Опр.: Связанный Граф без Циклов Kn называется Деревом Kn.

Опр.: Сведением (или Склеиванием) Вершин Графа называется такая операция над исходным Графом, при котором Вершины v1,v2, ... ,vn удаляются из Графа вместе с инцидентными ребрами, а вместо них появляется вершина с названием <<v1,v2, ... ,vn>>, которая соединяется ребрами с бывшими смежными вершинами для удаленных вершин v1,v2, ... ,vn.

4koloro_p1

Примечание: В приведенном примере граф состоит из открытых маршрутов K3. При этом каждые/любые два соседних (смежных) ребра K3 имеют общий подграф - ребро K2. Более того, каждая/любая вершина в ребре K3 соединена ровно с двумя вершинами из соседнего ребра K3. По аналогии можно создать подобные примеры для графов, состоящих из маршрутов K4, K5, ..., Kn. Также заметим, что раз данный подграф состоит только из открытых маршрутов K3, то его можно однозначно раскрасить, используя наименьшее три цвета при заданной начальной раскраски одного из его ребер K3. И как следствие означает, что данный граф является трех-дольным, то есть разбивается наименьшее на три доли. Можно провести аналогию данного графа с деревом, также по аналогии можно дать название данному графу как дерево K3. Более подробно это будет описано при доказательстве теоремы о n-дольности графа.

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

По поводу операции склеивания вершин в графе, название склеенной вершины (то есть добавленной вместо удаленных вершин) является строкой, в которой через запятую перечисляются названия удаленных вершин, делается это только ради удобства. Поскольку данная операция будет применятся для склеивания вершин окрашенных в одинаковые цвета, чтобы не потерять информацию об изначальных вершинах их удобнее запоминать в названии новой созданной вершине в ходе операции преобравзования над графом. К тому же в определении графа нет явных указаний и ограничений на именование вершин графа. Правда, из практических соображений, принято вершины нумеровать натуральными числами. Таким образом, при выполнении операции склеивания над вершинами, раскрашенными в один цвет, с названиями <<4>>, <<7>>, <<47>> и <<13,1>> получаем новую вершину с названием <<4,7,47,13,1>>, а оперируемые вершины удаляем. Тогда новую вершину можно раскрасить в заданный цвет, не беспокоясь о том, что в последствии преобразований графа мы забудем в какой цвет нужно раскрасить вершины исходного графа.


Теорема о n-дольном графе

Формулировка: В графе все маршруты Kn сводятся к ребру Kn тогда и только тогда, когда граф является n-дольным.

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

Лемма №2. Пусть дан граф, задача заключается в том, чтобы определить на какое наименьшее количество доль его можно разбить. Соответственно, если в графе есть максимальная клика Kn, то данный граф разбить на меньшее чем n доль не получится. Поскольку по принципу Дирихле при любой разбивке на меньшее чем n доль две или более вершины максимальной клики Kn окажутся в одной доле, а так как эти вершины принадлежат подграфу Kn, то между ними должно быть ребро, чего не может быть в одной доле по определению n-дольного графа.

Примечание: Поскольку нам необходимо разбить граф на наименьшее количество доль, то применять данную теорему бессмысленно для маршрутов Kn, где n меньше чем у максимальной клике в графе. Другими словами, если дан граф, в котором заведомо известно, что максимальная клика равна 10 (K10), то бессмысленно в этом графе искать маршруты K2, K3, ..., K9, поскольку данные маршруты не будут сводится к соответствующим ребрам и соответственно теорема будет давать отридцательный ответ на вопрос 2-, 3-, ..., 9-дольности данного графа. Такого же результата можно добиться просто применив Лемму №2 и сразу же приступив к проверке графа на 10-дольность.

Для сравнения, если в данной формулировке теоремы о n-дольном графе заменить условие для двудольного графа, то получим: "В графе все маршруты сводятся к ребру тогда и только тогда, когда граф является двудольным". И действительно, открытые маршруты всегда будут сводится к ребру, а циклы только в случае четности количества их ребер, что в точности соответствует условию теоремы Кенига.


Доказательство теоремы о n-дольном графе

Достаточность. Рассмотрим n-дольный граф. Сведём вершины графа в каждой доле, получим n-дольный граф без петель. Следовательно, данный граф сводится к ребру Kn, а значит и любой его подграф, содержащий ребро Kn, в том числе и маршруты Kn, будут сводится к ребру Kn.

Необходимость. Пусть в графе все маршруты Kn сводятся к ребру Kn. Тогда сведем все эти маршруты Kn к ребрам Kn. Далее поскольку после проделанной операции над графом все маршруты Kn преобразовались в ребра Kn, то в полученном графе не найдется ни одной вершины (непринадлежащей ребру Kn) соединенной сразу с n-1 вершиной одного ребра Kn, поскольку такая вершина входила бы в маршрут Kn, который мы должны были бы свести к ребру Kn. На данном этапе мы уже свели часть вершин данного графа, осталось свести оставшиеся вершины изначально непринадлежащие маршрутам Kn.

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

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

Данная операция напоминает построение дерева, только в нашем случае дерево будет состоять из ребер Kn.

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

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

Итак, после добавления новых ребер выбранная вершина будет соединена маршрутом Kn с ребром Kn, следовательно, данную вершину можно свести к данному ребру Kn. После сведения данная вершина окажется в ребре Kn, и нам необходимо проверить, не стали ли смежные вершины для сведенной нами вершиныпрепятствовать дальнейшей работе.

Рассмотрим все смежные вершины, поскольку до преобразования (сведения вершины с ребром Kn, но после сведения маршрутов Kn к ребру Kn) они могли быть смежными наибольшее только n-2 вершинами с любым из ребер Kn, так как не входили в маршрут Kn, то после преобразования вершины могли стать смежными с n-1 вершиной из ребра Kn и как следствие образовывать маршрут Kn. Тогда сделаем сведение к данному ребру Kn для данных вершин. Получим картину, соответствующую графу со сведенными маршрутами Kn. В итоге будет уменьшаться количество вершин в графе, пока не закончатся вершины, непринадлежащие ребрам Kn.

Теперь по аналогии, данные ребра Kn соединить маршрутом Kn, и свести все к одному ребру Kn.

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

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

Следствие №1: Граф с наибольшей кликой n имеет наименьшее либо n-доль, либо (n+1) доль.

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

Примечание: На самом деле теорему Кёнига правильнее формулировать так:
В графе нет нечетных циклов тогда и только тогда, когда граф является двудольным.

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

Соответственно и формулировку теоремы о n-дольности необходимо скорректировать по аналогии следующим образом:
В графе нет маршрутов Kn, которые не сводятся к ребру Kn тогда и только тогда, когда граф является n-дольным.

Применим данную теорему о n-дольности к задаче о 4-х красках.


Задача о 4-х красках

Поскольку планарный граф, к раскраске которого сводится раскраска плоской карты не содержит клики K5, то данный граф по следствию из теоремы о n-дольнсти можно раскрасить либо в 5, либо в 4 цвета. Для того чтобы доказать возможность раскраски в четыре цвета для любого планарного графа, необходимо доказать, что все маршруты K4 планарных графов сводятся к ребру K4.

Итак, рассмотрим полный граф K4, маршрут K4 и дерево K4 на плокости.

Для начала рассмотрим единственное возможное изображение полного графа K4 на плоскости:

4koloro_p2

И маршрута K4:

4koloro_p3

Решение: Заметим, что в графе K4 на плоскости имеется центральная вершина, которая не может граничить ни с какой вершиной вне треугольника, иначе будет нарушение условия планарности. Тогда до всех вершин, находящихся внутри треугольника достроим маршрут K4. В итоге получим нечто наподобие Рисунка №3. Теперь начнем сводить данный маршрут K4, начиная с самой центральной вершины, поскольку данная вершина не смежна вершинам не из данного треугольника, то при сведении получение петли исключается полностью. Следовательно, в планарном графе все маршруты K4 сводятся к ребру K4, что как следствие означает 4-дольность всех планарных графов и возможность их раскраски в наименьшее количество цветов, используя максимум 4 цвета. Ч.т.д.

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


Тэги:
задача, теорема, доказательство, koloro

Комментариев нет:

Отправить комментарий