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

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

Боже, какой беспорядок.

Этот граф плох для анализа, поскольку он состоит из двенадцати полных подмножеств. Подмножество {0, 1, 2, 3,} является кликой, как и {0, 1, 4, 5} и {0, 4, 8, 12}.

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

Хм.. Получилось не намного лучше.

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

{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 9, 10, 11}, {12, 13, 14, 15},
{0, 4, 8, 12}, {1, 5, 9, 13}, {2, 6, 10, 14}, {3, 7, 11, 15},
{0, 1, 4, 5}, {2, 3, 6, 7}, {8, 9, 12, 13}, {10, 11, 14, 15}

И преобразовать это в список вершин: {0, 1}, {0, 2}, {0, 3}, {1, 0}, {1, 2}, ...

И какая разница, если я пройдусь по одному и тому же ребру дважды. Я реализовал свой граф в виде массива Boolean, так что какие могут быть проблемы, если я дважды установлю в true какое-либо значение.

Это легко реализовать с помощью LINQ:

 public static IEnumerable<Tuple<int, int>> CliquesToEdges(IEnumerable<IEnumerable<int>> cliques)
{
return
from clique in cliques
from item1 in clique 
from item2 in clique 
where item1 != item2
select Tuple.Create(item1, item2);
}

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

В первой строке мы начинаем с {0, 1, 2, 3}. Затем мы прибавляем четыре к каждому элементу: {4, 5, 6, 7}. Затем прибавляем восемь: {8, 9, 10, 11}. Затем – двенадцать: {12, 13, 14, 15}.

Во второй строке, мы начнем с {0, 4, 8, 12}. Затем прибавим единицу: {1, 5, 9, 13}. Затем прибавим два. Затем три.

В третьей строке, мы начинаем с {0, 1, 4, 5}. Затем прибавляем два, восемь и десять.

Короче говоря, если мы хотим, мы можем написать генератор подмножеств следующим образом:

 var offsets = new[,] { 
/*строки*/    {new[] {0, 4, 8, 12}, new[] {0, 1, 2, 3 }},
/*столбцы*/ {new[] {0, 1, 2, 3},  new[] {0, 4, 8, 12}},
/*квадраты */{new[] {0, 2, 8, 10}, new[] {0, 1, 4, 5}}};
var cliques =
    from r in Enumerable.Range(0, 3)
    from i in offsets[r, 0]
    select (from j in offsets[r, 1] select i + j);
    var edges = CliquesToEdges(cliques);
    var graph = new Graph(16, edges);
    var solver = new Solver(graph, 4);

И если мы решим эту задачу, то получим цвета 0, 1, 2, 3, 2, 3, 0, 1, 1, 0, 3, 2, 3, 2, 1, 0 для 16 узлов:

И конечно же, каждое полное подмножество, окруженное элипсом не должно содержать два узла одного цвета. Здорово!

Но давайте на этом не остановимся! А что, если вместо 16 узлов у нас будет, скажем... 81! И что если вместо 12 полных подмножеств у нас будет ... 27!

И что если мы будем знать заранее некоторые цвета?

Прежде всего, мы легко можем изменить наш генератор подмножеств:

 var offsets = new[,] { 
/*строки*/ {new[] {0, 9, 18, 27, 36, 45, 54, 63, 72}, new[] {0, 1, 2, 3, 4, 5, 6, 7, 8}},
/*столбцы*/{new[] {0, 1, 2, 3, 4, 5, 6, 7, 8}, new[] {0, 9, 18, 27, 36, 45, 54, 63, 72}},
/*ячейки */ {new[] {0, 3, 6, 27, 30, 33, 54, 57, 60}, new[] {0, 1, 2, 9, 10, 11, 18, 19, 20}}};

Генератор клик и вершин один и тот же. Давайте создадим объект класса Solver для этого графа и заранее уберем некоторые цвета:

 Graph graph = new Graph(81, edges);
var solver = new Solver(graph, 9);
string puzzle =
"  8 274  " +
"         " +
" 6 38  52" +
"      32 " +
"1   7   4" +
" 92      " +
"78  62 1 " +
"         " +
"  384 5  ";

int node = -1;
foreach (char c in puzzle)
{
    ++node;
if (c == ' ') continue;
    solver = solver.SetColour(node, c - '1');
}
var result = solver.Solve();
int i = 0;
foreach (var r in result)
{
Console.Write(r + 1);
if (i % 9 == 8)
Console.WriteLine();
    ++i;
}

Результат выполнения:

358127469

279654831

461389752

847916325

135278694

692435187

784562913

516793248

923841576

Боже мой! Здесь я, мечтая о собственном бизнесе, пытаясь решить задачу из теории графов, случайно написал решение головоломок Судоку! Разве не забавно, какие повороты делает жизнь? Вот насколько невероятным является LINQ.

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

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