В этой небольшой заметке я хочу показать, как с помощью алгебры можно решать классическую задачу о раскраске вершин графа. Об этом сюжете я узнал из книги W.W. Adams, P. Loustanau. An Introduction to Groebner Basis (параграф 2.7).
Введение
Для начала обсудим все необходимые понятия. Пусть — это некоторое множество, а — множество, состоящее из неупорядоченных пар элементов множества. Тогда графом называется пара При этомназывается множеством вершин графа, а — множеством рёбер графа. Вершиныназываются смежными, если они соединены ребром, то есть.
Рассмотрим граф, состоящий из трех вершин, которые попарно соединены ребрами. Множество вершин такого графа имеет вид , а множество рёбер — . Все вершины у графа являются смежными. Удобно представить себе этот граф, изобразив его на плоскости.
Заметим, что при этом мы смогли нарисовать ребра так, что они не пересекаются вне вершин. Графы, для которых удаётся такое сделать, называются планарными или плоскими. Не всякий граф является планарным. Например, граф с пятью вершинами, у которого каждая пара различных вершин является смежной, не будет планарным.
Пусть — множество изэлементов (множество красок). Тогда раскраской вершин графас помощью красок называется отображение такое, что для любой пары смежных вершин графа выполняется условие . Иными словами, каждой вершине мы однозначно сопоставляем один из цветов таким образом, чтобы соединенные ребром вершины были покрашены в разные цвета. Для простоты мы будем рассматривать только случай трёх красок (), хотя используемые методы годятся и для любого . Наш трехвершинный граф без труда можно раскрасить в три цвета.
Итак, мы хотим определять по графу, можно ли раскрасить его вершины в три цвета, так чтобы смежные вершины не были раскрашены в один и тот же.
Алгебра приходит на помощь
Пусть парой множестви задан граф. Основная идея состоит в том, чтобы сопоставить нашему графу систему алгебраических уравнений. В качестве множества красок будем использовать множество
где Это множество состоит из кубических корней из единицы, то есть таких комплексных чисел, которые при возведении их в третью степень дают (в общем случае нужно рассматривать множество корней-ой степени). Будем считать, что каждая вершина является переменной. При раскраске каждая такая переменная может принять одно из значений Мы можем выразить этот факт в алгебраической форме следующим образом: при выборе одного из трех указанных значений переменного должен занулиться многочлен
Таким образом, мы получаем систему из алгебраических уравнений
Однако пока мы никак не учитываем то, что смежные вершины нельзя покрасить в один и тот же цвет. Пустиявляются смежными вершинами, то есть множество содержит ребро Тогда в правой части равенства
первый сомножитель не может обращаться в ноль, так как Следовательно должна зануляться вторая скобка. Таким образом, к уже имеющимся уравнениям мы должны добавить уравнение вида
для каждого ребра. Теперь вопрос о раскраске вершин графа превратился в вопрос о совместности системы алгебраических уравнений, то есть в вопрос о существовании решения у такой системы. Если у системы нет решений, то граф нельзя раскрасить. Если решения существуют, то каждое даёт способ раскраски вершин графа.
Знакомые с коммутативной алгеброй читатели знают, что этот вопрос о совместности системы алгебраическхи уравнений над алгебраически замкнутым полем решается с помощью так называемой слабой теоремы Гильберта о нулях и теории базисов Гребнера. Мы же в следующем пункте воспользуемся встроенной в модуль SciPy функцией решения систем уравнений для реализации разобранного метода на языке Python.
Реализация на Python
В качестве библиотеки, позволяющей работать с графами, будем использовать igraph.
Тестировать наш скрипт будем на следующем графе из восьми вершин. Отметим, что данный граф является планарным, хотя алгоритм Кавады и Каваи не смог уложить его на плоскость без пересечения ребер вне вершин.
from igraph import *
from sympy import solve, symbols
# Зададим количество вершин
NumberOfVertices = 8
# Перечислим все ребра нашего графа
EdgesList = [(0,1), (0,4), (0,5), (1,7), (1,2), (2,3), (2,7), (1,3), (3,4), (3,6), (4,5), (4,6),(5,6), (6,7)]
# Инициализируем граф, обозначив его вершины с помощью символов x1,...x8
TestGraph = Graph()
TestGraph.add_vertices(NumberOfVertices)
TestGraph.add_edges(EdgesList)
x1, x2, x3, x4, x5, x6, x7, x8 = symbols("x1 x2 x3 x4 x5 x6 x7 x8")
TestGraph.vs["name"] = [x1, x2, x3, x4, x5, x6, x7, x8]
TestGraph.vs["label"] = TestGraph.vs["name"]
# Генерируем уравнения для системы, определяющей раскраску
EquationList=[]
for edge in EdgesList:
EquationList.append("x%d^2 + x%d * x%d + x%d^2"%(edge[0]+1,edge[0]+1,edge[1]+1,edge[1]+1))
for vertice in range(NumberOfVertices):
EquationList.append("x%d^3-1"%(vertice+1))
# Сопоставляем кубическим корням из единицы красную, зеленую и синию краски
Roots = solve(x1**3-1)
RootsToColors = {Roots[0]: "red", Roots[1]: "green", Roots[2]: "blue"}
# Непосредственно решаем систему уравнений
Colorings = solve(EquationList, dict=True)
print("The number of colorings is %d."%len(Colorings))
# Если система совместна, то выводим k-ю раскраску.
# Если нет, то делаем вывод о том, что граф нельзя раскрасить в три цвета.
if(Colorings):
# Раскрашиваем вершины графа
k = 0
RawColors = [Colorings[k][vertice] for vertice in TestGraph.vs["name"]]
ColorDictionary = [RootsToColors[color] for color in RawColors]
TestGraph.vs["color"]=ColorDictionary
# Укладываем граф на плоскость и рисуем
Layout = TestGraph.layout_kamada_kawai()
visual_style = {}
visual_style["vertex_size"] = 40
visual_style["bbox"] = (300, 300)
plot(TestGraph, layout=Layout, **visual_style)
else:
print("The graph is non-colorable.")
В результате получаем одну из возможных раскрасок.
Впрочем раскраску для этого графа нетрудно получить без всякой науки, методом проб и ошибок. Однако добавив к графу ребро, соединяющее вершиныи, мы приходим к графу, который нельзя раскрасить. В этом случае метод проб и ошибок бессилен.
Комментарии (10)
Sergey_Kovalenko
16.02.2022 15:07Ох, ничего себе: Вы (автор статьи) говорите, что есть алгоритм, который позволяет точно определить, совместна ли система алгебраических уравнений или нет. А не вспомните случаем сложность этого алгоритма (в худшем случае) от числа переменных и степени уравнений?
wataru
16.02.2022 20:16Очевдино, оно экспоненциально, потому что задача раскраски графа NP-complete. Может работает быстрее полного перебора, но не ассимптотически.
third112
16.02.2022 19:45В статье ни слова о Теореме о пяти красках и о Теореме о четырёх красках. Это кажется неслучайным! В отношении предложенного алгоритма возникает подозрение, что автор тихой сапой хочет доказать им теорему о четырёх красках. BTW четкое описание алгоритма, как принято в CS, отсутствует его подменяет код реализации, что не является равноценной заменой, т.к. любую ошибку можно будет назвать багом реализации или багом ЯП.
third112
16.02.2022 20:05PS Вызывает удивление помещение статьи в хаб "Научно-популярное". Если бы речь была об известном знании, то его можно популяризировать. Нпр., теорему Пифагора можно попробовать популярно объяснить 6 летним детям. Но новый алгоритм помещать в "популярное", прежде описания в научных изданиях (можно и в других хабах на Хабре) — явно преждевременно.
bigcrush
Подскажите, почему справедливо равенство, когда множество E содержит ребро {xk, xl}?
radmath Автор
Дело в том, что мы красим с помощью кубических корней из единиц, поэтомуи, а разность этих величин тогда равна нулю.
bigcrush
Разве это не выполняется для двух произвольных вершин? Почему указанная разность кубов задаёт именно смежные вершины?
radmath Автор
Указанная разность всегда равна нулю, но для смежных вершин, поэтому
Постарался переписать абзац, чтобы он был более логичным. Спасибо!
bigcrush
Я, думаю, понял. Меня смущало, как равенство нулю последнего трёхчлена гарантирует, что xk!=xl? Но оба множителя в разложении разности кубов могут оказаться нулями, только если xk=xl=0, а это не так, поскольку xi - корень из 1. Спасибо. Простите, за занудство.