Честно говоря, я не могу поверить, что об этом еще не спрашивали, но вот оно

Фон

Учитывая простой неориентированный планарный (граф может быть нарисован на плоскости без пересечений) граф, это доказанная теорема, что граф является 4-раскрашиваемым, термин, который мы рассмотрим чуть позже. Тем не менее, намного легче 5-цветный график, на котором мы сосредоточим нашу задачу сегодня.

Допустимая k-раскраска графа - это присвоение «цветов» узлам графа со следующими свойствами

1. Если два узла соединены ребром, узлы окрашиваются в разные цвета.
2. На графике максимум 5 цветов.

Учитывая это, я представлю вам довольно простой алгоритм 5-цветного любого простого неориентированного плоского графа. Этот алгоритм требует следующих определений

Достижимость : если узел 1 доступен из узла 2, это означает, что существует последовательность узлов, каждый из которых соединен со следующим ребром, так что первый узел является узлом 2, а последний - узлом 1. Обратите внимание, что поскольку неориентированные графы симметричны, если узел 1 доступен из узла 2, узел 2 доступен из узла 1.

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

Пусть Color (N) - функция для раскраски плоских графов с N узлами в 5 цветов. Определим функцию ниже

1. Найдите узел с наименьшим количеством подключенных к нему узлов. К этому узлу будет подключено не более 5 узлов.
2. Удалить этот узел из графика.
3. Назовите Color (N-1) на этом новом графике, чтобы раскрасить его.
4. Добавьте удаленный узел обратно на график.
5. Если возможно, закрасьте добавленный узел цветом, который не имеет ни один из его связанных узлов.
6. Если это невозможно, то все 5 соседних узлов к добавленному узлу имеют 5 разных цветов, поэтому мы должны попробовать следующий процесс.
7. Пронумеруйте узлы, окружающие добавленный узел n1 ... n5
8. Рассмотрим подграф всех узлов в исходном графе, окрашенный в тот же цвет, что и n1 или n3.
9. Если в этом подграфе n3 недоступен из n1, в наборе узлов, достижимых из n1 (включая n1), замените все вхождения цвета n1 на n3 и наоборот. Теперь раскрасьте исходный цвет добавленной вершины n1.
10. Если n3 был доступен из n1 в этом новом графике, выполните процесс, начиная с шага 9, на узлах n2 и n4, а не n1 и n3.

Вызов

Учитывая ввод списка краев (представляющего график), раскрасьте график, назначив каждому узлу значение.

Входные данные : список ребер в графе (т. Е. [('a','b'),('b','c')...])

Обратите внимание, что входной край списка будет таким, что если (a, b) находится в списке, то (b, a) НЕ в списке.

Вывод : Объект , содержащий пары значений, где первый элемент каждой пары является узлом, а второй его цвет, то есть, [('a',1),('b',2)...]или{'a':1,'b':2,...}

Вы можете использовать все, что угодно для представления цветов, от цифр до символов и всего остального.

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

правила

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

Тестовые случаи

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

Некоторые случайные (и довольно глупые) тесты :

Тестовый пример 2: График Кайтхардта Кайта [(0, 1), (0, 2), (0, 3), (0, 5), (1, 3), (1, 4), (1, 6), (2, 3), (2, 5), (3, 4), (3, 5), (3, 6), (4, 6), (5, 6), (5, 7), (6, 7), (7, 8), (8, 9)]

Действительный вывод: {0: 4, 1: 3, 2: 3, 3: 2, 4: 4, 5: 1, 6: 0, 7: 4, 8: 3, 9: 4}

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

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

Примечание 3 : я не упустил алгоритмы случайного окрашивания, которые были представлены, что так здорово в PPCG! Однако, если бы кто-нибудь мог сыграть в более детерминистический алгоритм, это было бы очень здорово.

Python 2 , 96 байт

i=0
g=input()
while 1:i+=1;c={k:i/4**k%4for k in sum(g,())};all(c[s]^c[t]for s,t in g)>0<exit(c)

Попробуйте онлайн!

$g$$i$$c$$c$$c$ является допустимой раскраской.

Ввод плоский, поэтому всегда можно найти 4-цветную раскраску.

(Таким образом: в некотором смысле это находит самую раннюю лексикографическую окраску и делает это очень неэффективно.)

$k$$\Big\lfloor \frac{i}{4^k} \Big\rfloor \bmod 4$$k$$i$

JavaScript (ES7), 80 76 74 байта

Сохранено 2 байта благодаря @Neil

Тот же подход, что и у Линн . Решает в 4 цветах, пронумерованных от 0 до 3 .

a=>{for(x=0;a.some(a=>a.map(n=>z=c[n]=x>>n*2&3)[0]==z,c={});x++);return c}

Попробуйте онлайн!

Брахилог , 38 байт

cd{∧4>ℕ}ᶻ.g;?z{tT&h⊇ĊzZhpT∧Zt≠}ᵐ∧.tᵐ≜∧

Попробуйте онлайн!

объяснение

Example input: [["a","b"],["c","b"]]

cd                                       Concatenate and remove duplicates: ["a","b","c"]
  {∧4>ℕ}ᶻ.                               The output is this list zipped zith integers that
                                           are in [0..4]: [["a",I],["b",J],["c",K]]
         .g;?z                           Zip the output with the input:
                                           [[[["a",I],["b",J],["c",K]],["a","b"]],[["a",I],["b",J],["c",K]],["c","b"]]
              {               }ᵐ∧        Map for each element
               tT                        Call T the couple of nodes denoting an edge
                 &h⊇Ċ                    Take a subset of 2 elements in the head
                     zZ                  Zip and call it Z
                      ZhpT               The nodes in Z are T up to a permutation
                          ∧Zt≠           The integers in Z are all different color
                                 .tᵐ≜∧   Label the integers (i.e. colors) in the output so that
                                           it matches the set constraints

Python 2 , 211 байт

def f(g):
 g={k:[(a,b)[a==k]for a,b in g if k in(a,b)]for k in sum(g,())};c={k:0 for k in g}
 for a,b in sorted(g.iteritems(),key=lambda a:len(a[1])):c={k:(c[k],c[k]+1)[c[a]==c[k]and k in b]for k in c}
 return c

Попробуйте онлайн!

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

Чисто , 139 байт

import StdEnv,Data.List
$l#(a,b)=unzip l
#e=nub(a++b)
=hd[zip2 e c\\c<- ?e|all(\(a,b)=c!!a<>c!!b)l]
?[h:t]=[[n:m]\\n<-[0..4],m<- ?t]
?e=[e]

Попробуйте онлайн!

Создает все раскраски и возвращает первый действительный.

Желе , 23 байта

®iⱮⱮ³¤ịE€S
FQ©L4ṗÇÐḟḢ®ż

Попробуйте онлайн!

Грубая сила. Предполагается, что узлы помечены целыми числами.