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

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

Введение

Для начала обсудим все необходимые понятия. ПустьV — это некоторое множество, а E — множество, состоящее из неупорядоченных пар\{v,w\} элементов множестваV. Тогда графом называется пара(V,E). При этом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\} \}. Все вершины у графа являются смежными. Удобно представить себе этот граф, изобразив его на плоскости.

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

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

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

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

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

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

где \varepsilon=\exp{\tfrac{2}{3}\pi i}. Это множество состоит из кубических корней из единицы, то есть таких комплексных чисел, которые при возведении их в третью степень дают 1 (в общем случае нужно рассматривать множество корнейn-ой степени). Будем считать, что каждая вершина 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).

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

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

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

0=x_k^3-x_l^3=(x_k-x_l)(x_k^2+x_kx_l+x_l^2).

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

x_k^2+x_kx_l+x_l^2=0

для каждого ребра\{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, мы приходим к графу, который нельзя раскрасить. В этом случае метод проб и ошибок бессилен.

Читайте так же:

  • Для Apple всё складывается просто сказочно: iPhone 13 улучшит рекорд бестселлера iPhone 12Для Apple всё складывается просто сказочно: iPhone 13 улучшит рекорд бестселлера iPhone 12 Согласно новому прогнозу аналитиков. Спрос на iPhone 13 будет ещё большим. Чем на iPhone 12. Информация из цепочки поставок Apple показывает. Что компания готовится выпустить больше устройств. Чем в прошлом году. Аналитик Wedbush Дэниел Айвз (Daniel Ives) заявил. Что первоначальный запас […]
  • МойОфис обновил облачные продукты: более 200 улучшений в релизе 2021.04МойОфис обновил облачные продукты: более 200 улучшений в релизе 2021.04 МойОфис, российская компания-разработчик офисного программного обеспечения для совместной работы с документами и коммуникаций, объявляет о выпуске четвертого обновления в 2021 году. Основные изменения коснулись продукта «МойОфис Частное Облако», функциональность которого была существенно […]
  • Смартфоны Apple iPhone 13 получат значительно улучшенные камерыСмартфоны Apple iPhone 13 получат значительно улучшенные камеры Как сообщает DigiTimes. Компания Apple реализовала улучшенную технологию камеры во всех моделях iPhone. Которые будут выпущены в 2021 году. Пока что точно неизвестно. Будут ли они они относиться к линейке iPhone 13 или iPhone 12s. Во-первых, речь идёт о технологии оптической стабилизации […]
  • Как быстро наполнить интернет магазин товарами opencartКак быстро наполнить интернет магазин товарами opencart Независимо от того. Переходите ли вы в OpenCart впервые или пытаетесь заполнить существующий магазин OpenCart фактическими данными. Импорт CSV-это отличный способ сделать это массово. Читайте дальше. Чтобы узнать. Как перенести продукты из вашего текущего решения электронной коммерции […]