Раскраска графов. Часть 4

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

 const int Brazil = 0;
const int FrenchGuiana = 1;
const int Suriname = 2;
const int Guyana = 3;
const int Venezuala = 4;
const int Colombia = 5;
const int Ecuador = 6;
const int Peru = 7;
const int Chile = 8;
const int Bolivia = 9;
const int Paraguay = 10;
const int Uruguay = 11;
const int Argentina = 12;
var SA = new Dictionary<int, int[]>()
{
    {Brazil, new[] { FrenchGuiana, Suriname, Guyana, Venezuala, Colombia, Peru, Bolivia, Paraguay, Uruguay, Argentina}},
    {FrenchGuiana, new[] { Brazil, Suriname }},
    {Suriname, new[] {Brazil, FrenchGuiana, Guyana}},
    {Guyana, new[] {Brazil, Suriname, Venezuala}},
    {Venezuala, new[] {Brazil, Guyana, Colombia}},
    {Colombia, new [] {Brazil, Venezuala, Peru, Ecuador}},
    {Ecuador, new[] {Colombia, Peru}},
    {Peru, new[] {Brazil, Colombia, Ecuador, Bolivia, Chile}},
    {Chile, new[] {Peru, Bolivia, Argentina}},
    {Bolivia, new[] {Chile, Peru, Brazil, Paraguay, Argentina}},
    {Paraguay, new[] {Bolivia, Brazil, Argentina}},
    {Argentina, new[] {Chile, Bolivia, Paraguay, Brazil, Uruguay}},
    {Uruguay, new[] {Brazil, Argentina}}
};

Мы можем преобразовать этот ассоциативный массив узлов и их соседей в список кортежей ребер и построить граф:

 var sagraph = new Graph(13, from x in SA.Keys
from y in SA[x]
select Tuple.Create(x, y));

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

В любом случае, теперь решение нашей задачи с четырьмя цветами весьма простое:

 var sasolver = new Solver(sagraph, 4);
var solution = sasolver.Solve();
foreach (var colour in solution )
Console.WriteLine(colour);

Мы получим 0, 1, 2, 1, 2, 1, 0, 2, 0, 1, 2, 1, 3. В виде графа это будет выглядеть следующим образом:

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

Обратите внимание на то, что граф Южной Америки плоский; он может быть изображен без пересечения ребер. Фактически все графы, которые взаимодействуют с соседними регионами на поверхности или сфере являются плоскими. (Интуитивно понимаете почему?) Однако ничего не мешает нашему алгоритму работать с более экзотическими графами. Давайте представим тор, он представляет собой форму пончика. Мы можем представить тор на плоском экране представив, что мы «свернули» представленный ниже квадрат и соединили левую и правую сторону, создавая цилиндр. А затем согните цилиндр в круг, чтобы верхняя сторона коснулась с нижней:

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

Обратите внимание, что на этой карте каждый регион касается другого и, таким образом, она не может быть раскрашена менее чем семью цветами. Теорема о четырех цветах не применима к торам! (А теорема о семи цветах – применима; вы можете раскрасить карту, которая закручена с двух сторон семью или меньшим количеством цветов.)

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

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

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

Оригинал статьи