Как раскрасить вершины графа

15.02.2022

В этой небольшой заметке я хочу показать, как с помощью алгебры можно решать классическую задачу о раскраске вершин графа. Об этом сюжете я узнал из книги W.W. Adams, P. Loustanau. An Introduction to Groebner Basis (параграф 2.7).

Введение

Для начала обсудим все необходимые понятия. Пусть Как раскрасить вершины графа — это некоторое множество, а — множество, состоящее из неупорядоченных пар $\{v,w\}$ элементов множества. Тогда графом называется пара (V,E). При этомназывается множеством вершин графа, а — множеством рёбер графа. Вершины $v, w\in V$ называются смежными, если они соединены ребром, то есть $\{v,w\}\in E$ .

Рассмотрим граф, состоящий из трех вершин, которые попарно соединены ребрами. Множество вершин такого графа имеет вид $V=\{x_1, x_2, x_3\}$ , а множество рёбер — $E=\{ \{x_1,x_2\}, \{x_1,x_3\}, \{x_2,x_3\} \}$ . Все вершины у графа являются смежными. Удобно представить себе этот граф, изобразив его на плоскости.

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

Пусть — множество изэлементов (множество красок). Тогда раскраской вершин графа (V,E) с помощью красок называется отображение $c:V\to C$ такое, что для любой пары v,w смежных вершин графа выполняется условие $c(v)\neq c(w)$ . Иными словами, каждой вершине мы однозначно сопоставляем один из цветов таким образом, чтобы соединенные ребром вершины были покрашены в разные цвета. Для простоты мы будем рассматривать только случай трёх красок ( n=3 ), хотя используемые методы годятся и для любого . Наш трехвершинный граф без труда можно раскрасить в три цвета.

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

Алгебра приходит на помощь

Пусть парой множеств $V=\{x_1,\ldots, x_n\}$ и задан граф. Основная идея состоит в том, чтобы сопоставить нашему графу систему алгебраических уравнений. В качестве множества красок будем использовать множество

$C=\{1, \varepsilon, \varepsilon^2\},$

где $\varepsilon=\exp{\tfrac{2}{3}\pi i}.$ Это множество состоит из кубических корней из единицы, то есть таких комплексных чисел, которые при возведении их в третью степень дают (в общем случае нужно рассматривать множество корней-ой степени). Будем считать, что каждая вершина $x_k,\ k=1,\ldots, m,$ является переменной. При раскраске каждая такая переменная x_k может принять одно из значений $1, \varepsilon, \varepsilon^2.$ Мы можем выразить этот факт в алгебраической форме следующим образом: при выборе одного из трех указанных значений переменного x_k должен занулиться многочлен

$x_k^3-1=(x-1)(x-\varepsilon)(x-\varepsilon^2).$

Таким образом, мы получаем систему из алгебраических уравнений

$x_k^3-1=0,\ k=1\ldots,m.$

Однако пока мы никак не учитываем то, что смежные вершины нельзя покрасить в один и тот же цвет. Пуст x_k и x_l являются смежными вершинами, то есть множество содержит ребро $\{x_k, x_l\}.$ Тогда справедливо равенство

Поскольку вершины являются смежными, то мы используем разные краски для них, а значит $x_k\neq x_l$ . Следовательно, первый сомножитель в указанном выше произведении не может быть равен нулю, а значит в ноль должна обращаться вторая скобка. Таким образом, к уже имеющимся уравнениям мы должны добавить уравнение вида

для каждого ребра $\{x_k, x_l\}\in E$ . Теперь вопрос о раскраске вершин графа превратился в вопрос о совместности системы алгебраических уравнений, то есть в вопрос о существовании решения у такой системы. Если у системы нет решений, то граф нельзя раскрасить. Если решения существуют, то каждое даёт способ раскраски вершин графа.

Знакомые с коммутативной алгеброй читатели знают, что этот вопрос о совместности системы алгебраическхи уравнений над алгебраически замкнутым полем решается с помощью так называемой слабой теоремы Гильберта о нулях и теории базисов Гребнера. Мы же в следующем пункте воспользуемся встроенной в модуль 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.")

В результате получаем одну из возможных раскрасок.

Впрочем раскраску для этого графа нетрудно получить без всякой науки, методом проб и ошибок. Однако добавив к графу ребро, соединяющее вершины x_2 и x_5 , мы приходим к графу, который нельзя раскрасить. В этом случае метод проб и ошибок бессилен.