Раскраска графов. Часть 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.
И с этими удивительными результатами, я отбываю в родные земли, чтобы провести там несколько недель с моей семьей и друзьями. Мы вернемся к Невероятным приключениям в коде уже в сентябре.