Как раскрасить связанные узлы разным цветом для каждого соседнего узла
Задача о раскраске графа — классическая задача в области математики.
Допустим, у нас есть граф, как на картинке выше, и проблема в том, что мы должны раскрасить каждый узел другим цветом для каждого соседнего узла. Мы знаем, что на этот счет существует теорема, теорема о четырех цветах или теорема о четырех цветах.
Теорема о четырех цветах утверждает, что для раскрашивания областей любой карты требуется не более четырех цветов, чтобы никакие две соседние области не были одного цвета.
Для получения дополнительной информации о теореме четырех цветов вы можете посмотреть эту ссылку:
Алгоритм жадной раскраски
Как жадный алгоритм раскраски решает проблему, вот этот алгоритм:
- Запустите все узлы.
- Установите узел для первой раскраски, приоритет имеет узел с наибольшей степенью.
- Выберите цвет-кандидат с помощью функции выбора цвета без соседнего узла, имеющего тот же цвет.
- Проверьте приемлемость цвета, если он может быть сохранен в наборе решений.
- Является ли решение полным? Перейдите к шагу 2, если это еще не сделано.
Скрипт Python
Прежде всего, я определил цвет раньше.
На основе теоремы о четырех цветах я выбираю 4 цвета ниже:
Шаг 1. Смежная матрица
Поскольку мы хотим решить проблему с помощью Python, мы должны представить граф с помощью смежной матрицы. Я не буду объяснять про соседнюю матрицу, вы можете найти ее по этой ссылке:
Вот соседняя матрица из графика выше.
# adjacent matrix
G = [[ 0, 1, 1, 0, 1, 0],
[ 1, 0, 1, 1, 0, 1],
[ 1, 1, 0, 1, 1, 0],
[ 0, 1, 1, 0, 0, 1],
[ 1, 0, 1, 0, 0, 1],
[ 0, 1, 0, 1, 1, 0]]
Затем мы начнем имя узла с букв:
node = "abcdef"
t_={}
for i in range(len(G)):
t_[node[i]] = i
Шаг 2. Подсчитайте степень и определите возможный цвет
# count degree of all node.
degree =[]
for i in range(len(G)):
degree.append(sum(G[i]))
# inisiate the posible color
colorDict = {}
for i in range(len(G)):
colorDict[node[i]]=["Blue","Red","Yellow","Green"]
Шаг 3. Сортировка узла
Я использую сортировку выбором для упорядочивания узлов от наибольшей степени к наименьшей.
# sort the node depends on the degree
sorted_node=[]
indeks = []
# use selection sort
for i in range(len(degree)):
_max = 0
j = 0
for j in range(len(degree)):
if j not in indeks:
if degree[j] > _max:
_max = degree[j]
idx = j
indeks.append(idx)
sorted_node.append(node[idx])
Шаг 4. Основной процесс
Этот основной процесс просматривает sortedNode и устанавливает цвет с возможными цветами в colorDict, а затем сохраняет в theSolution. После этого этот цвет будет удален из colorDict, поскольку он уже использовался.
# The main process
theSolution={}
for n in sortedNode:
setTheColor = colorDict[n]
theSolution[n] = setTheColor[0]
adjacentNode = G[t_[n]]
for j in range(len(adjacentNode)):
if adjacentNode[j]==1 and (setTheColor[0] in colorDict[node[j]]):
colorDict[node[j]].remove(setTheColor[0])
Шаг 5. Распечатайте решение
Распечатайте из theSolution Dict и отсортируйте их по имени узла.
# Print the solution
for t,w in sorted(theSolution.items()):
print("Node",t," = ",w)
Бонусный сценарий
Заставим вас лениться. Просто скопируйте и вставьте этот скрипт и запустите его.
Результат
После запуска скрипта вот результат:
Если мы снова представим график, то он будет таким:
Заключение
Вы знаете, что решение использует только 3 цвета. Это потому, что наша программа будет искать минимальное количество цветов для раскрашивания графика. Итак, на приведенном выше графике мы никогда не встретим 4-й цвет, потому что только с тремя цветами у нас есть решение.
Вы можете попробовать другой график с помощью этой программы, просто замените соседнюю матрицу и node = «abcdef» на свои.
Если ты узнаешь что-то сегодня, это здорово, чувак. Спасибо за прочтение.
Больше контента на plainenglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Получите эксклюзивный доступ к возможностям написания и советам в нашем сообществе Discord.
