Раскраска графика - Graph coloring

Не путать с Краска окраски.

Правильная раскраска вершин Граф Петерсена с 3 цветами, минимально возможное количество.

В теория графов, раскраска графика это частный случай маркировка графиков; это присвоение ярлыков, традиционно называемых «цветами», элементам график при соблюдении определенных ограничений. В простейшем виде это способ окраски вершины графа, у которого нет двух соседних вершин одного цвета; это называется раскраска вершин. Точно так же окраска края назначает цвет каждому краю, чтобы никакие два соседних края не были одного цвета, и окраска лица из планарный граф назначает цвет каждой грани или области, чтобы никакие две грани, имеющие общую границу, не имели одинаковый цвет.

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

Условие использования цветов происходит от раскрашивания стран карта, где буквально окрашено каждое лицо. Это было обобщено для раскраски граней графа встроенный в плоскости. Благодаря плоской двойственности он стал раскрашиванием вершин, и в таком виде он распространяется на все графы. В математических и компьютерных представлениях типично использовать первые несколько положительных или неотрицательных целых чисел в качестве «цветов». В общем, можно использовать любые конечный набор как «набор цветов». Характер проблемы окраски зависит от количества цветов, а не от того, какие они есть.

Раскраска графов имеет множество практических приложений, а также решает теоретические задачи. Помимо классических типов задач, различные ограничения также могут быть установлены на графике, или на способ назначения цвета, или даже на сам цвет. Он даже стал популярным среди широкой публики в виде популярной числовой головоломки. Судоку. Раскраска графиков - все еще очень активная область исследований.

Примечание. Многие термины, используемые в этой статье, определены в Глоссарий теории графов.

История

Смотрите также: История теоремы о четырех цветах и История теории графов

Первые результаты о раскраске графов касаются почти исключительно планарные графы в виде раскраски картыПытаясь раскрасить карту графств Англии, Фрэнсис Гатри постулировал четырехцветная гипотеза, отметив, что четырех цветов было достаточно для раскрашивания карты, так что ни одна область с общей границей не получила одинаковый цвет. Брат Гатри передал вопрос своему учителю математики. Август де Морган в университет колледж, который упомянул об этом в письме Уильям Гамильтон в 1852 г. Артур Кэли поднял проблему на заседании Лондонское математическое общество в 1879 году. В том же году, Альфред Кемпе опубликовал статью, в которой утверждал, что установил результат, и в течение десяти лет проблема четырех цветов считалась решенной. За свои достижения Кемпе был избран членом Королевское общество а позже президент Лондонского математического общества.^[1]

В 1890 г. Heawood указал, что аргумент Кемпе неверен. Однако в этой статье он доказал, что теорема пяти цветов, говоря, что каждую планарную карту можно раскрасить не более чем пять цвета, используя идеи Кемпе. В следующем столетии было разработано огромное количество работ и теорий по сокращению количества цветов до четырех, пока теорема о четырех цветах не была окончательно доказана в 1976 году. Кеннет Аппель и Вольфганг Хакен. Доказательство восходит к идеям Хивуда и Кемпе и в значительной степени игнорирует промежуточные разработки.^[2] Доказательство теоремы о четырех цветах также заслуживает внимания как первое крупное компьютерное доказательство.

В 1912 г. Джордж Дэвид Биркофф представил хроматический полином для изучения задачи раскраски, которая была обобщена на Полином Тутте к Тутте, важные структуры в алгебраическая теория графов. Кемпе уже обращал внимание на общий неплоской случай в 1879 г.^[3] и многие результаты по обобщению раскраски плоских графов на поверхности более высокого порядка, последовавшие в начале 20 века.

В 1960 г. Клод Берже сформулировал еще одну гипотезу о раскраске графов, сильная гипотеза о совершенном графе, изначально мотивированными теоретико-информационный концепция называется пропускная способность без ошибок графа, введенного Шеннон. Гипотеза оставалась неразрешенной в течение 40 лет, пока не была признана знаменитой. сильная теорема о совершенном графе к Чудновский, Робертсон, Сеймур, и Томас в 2002.

Раскраска графов изучается как алгоритмическая проблема с начала 1970-х годов: проблема хроматических чисел является одной из 21 NP-полная задача Карпа с 1972 года, и примерно в то же время были разработаны различные алгоритмы экспоненциального времени, основанные на отслеживании с возвратом и на повторении удаления-сокращения Зыков (1949). Одно из основных применений раскраски графов, распределение регистров в компиляторах, был представлен в 1981 году.

Определение и терминология

Этот график можно раскрасить 12 разными способами.

Раскраска вершин

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

Терминология использования цвета для меток вершин возвращается к раскраске карты. Ярлыки вроде красный и синий используются только тогда, когда количество цветов невелико, и обычно подразумевается, что метки строятся из целых чисел {1, 2, 3, ...}.

Раскраска с использованием не более k цвета называется (собственно) k-крашиваниеНаименьшее количество цветов, необходимое для раскрашивания графика. грамм называется его хроматическое число, и часто обозначают χ (грамм). Иногда γ (грамм), поскольку χ (грамм) также используется для обозначения Эйлерова характеристика графа, которому можно присвоить (собственно) k-раскрашивание kраскрашиваемый, и это k-хроматический если его хроматическое число точно kПодмножество вершин, которым назначен один и тот же цвет, называется цветовой класс, каждый такой класс образует независимый набор. Таким образом, k-раскрашивание аналогично разбиению вершины на k независимые множества, а условия k-partite и k-раскрашиваемый имеют то же значение.

Хроматический полином

Все неизоморфные графы с 3-мя вершинами и их хроматические многочлены. Пустой график E₃ (красный) допускает 1-раскраску; другие не допускают такой окраски. Зеленый граф допускает 12 раскрасок в 3 цвета.

Основная статья: Хроматический полином

В хроматический полином подсчитывает количество способов раскрасить график, используя не более заданного количества цветов. Например, используя три цвета, график на соседнем изображении можно раскрасить 12 способами. Имея только два цвета, его вообще нельзя раскрасить. С четырьмя цветами его можно раскрасить 24 + 4⋅12 = 72 способами: используя все четыре цвета, их четыре! = 24 допустимые раскраски (каждый присвоение четырех цветов любой 4-вершинный граф - правильная раскраска); и для каждого выбора трех из четырех цветов существует 12 допустимых трехцветных раскрасок. Итак, для графика в примере таблица количества допустимых раскрасок должна начинаться так:

Доступные цвета	1	2	3	4	…
Кол-во раскрасок	0	0	12	72	…

Хроматический полином - это функция п(грамм, т), который считает количество т-расцветкиграмм. Как видно из названия, для данного грамм функция действительно многочлен вт. Для примера графика п(грамм, т) = т(т − 1)²(т - 2), и действительноп(грамм, 4) = 72.

Хроматический полином включает в себя как минимум столько же информации о раскрашиваемости грамм как и хроматическое число. В самом деле, χ - наименьшее натуральное число, не являющееся корнем хроматического многочлена

${\displaystyle \chi (G)=\min\{k\,\colon \,P(G,k)>0\}.}$

Хроматические полиномы для некоторых графов

Треугольник K3	${\displaystyle t(t-1)(t-2)}$
Полный график Kп	${\displaystyle t(t-1)(t-2)\cdots (t-(n-1))}$
Дерево с п вершины	${\displaystyle t(t-1)^{n-1}}$
Цикл Cп	${\displaystyle (t-1)^{n}+(-1)^{n}(t-1)}$
Граф Петерсена	${\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)}$

Краска окраски

Основная статья: Краска окраски

An окраска края графа - это правильная раскраска края, что означает присвоение цвета ребрам так, чтобы ни одна вершина не инцидентна двум ребрам одного цвета. Окраска края с k цвета называется k-крат-раскраска и эквивалентна задаче разбиения множества ребер на k совпадения. Наименьшее количество цветов, необходимое для раскраски ребер графа грамм это хроматический индекс, или же краевое хроматическое число, χ′(грамм). А Раскраска таит является 3-краевой раскраской кубический граф. В теорема четырех цветов эквивалентно утверждению, что каждая плоская кубическая без моста граф допускает раскраску Тэйта.

Общая окраска

Основная статья: Общая окраска

Общая окраска это тип раскраски на вершинах и ребра графа. При использовании без каких-либо уточнений полная раскраска всегда считается правильной в том смысле, что никаким смежным вершинам, никаким смежным ребрам, никакому ребру и его конечным вершинам не назначается один и тот же цвет. Общее хроматическое число χ ″ (G) графа G - это наименьшее количество цветов, необходимое для любой полной раскраски графа G.

Раскраска без надписи

An немаркированная окраска графа является орбита окраски под действием группа автоморфизмов графа. Если интерпретировать раскраску графа на ${\displaystyle d}$ вершины как вектор в ${\displaystyle \mathbb {Z} ^{d}}$, действие автоморфизма есть перестановка коэффициентов раскраски. Есть аналоги хроматические полиномы которые подсчитывают количество непомеченных раскрасок графа из заданного конечного набора цветов.

Характеристики

Верхние границы хроматического числа

Назначение разных цветов различным вершинам всегда дает правильную раскраску, поэтому

${\displaystyle 1\leq \chi (G)\leq n.}$

Единственными графами, которые могут быть одноцветными, являются безреберные графы. А полный график ${\displaystyle K_{n}}$ из п вершины требует ${\displaystyle \chi (K_{n})=n}$ цвета. В оптимальной раскраске должен быть хотя бы один из графов м края между каждой парой цветовых классов, поэтому

${\displaystyle \chi (G)(\chi (G)-1)\leq 2m.}$

Если грамм содержит клика размера k, то хотя бы k цвета нужны, чтобы раскрасить эту клику; другими словами, хроматическое число - это как минимум кликовое число:

${\displaystyle \chi (G)\geq \omega (G).}$

За идеальные графики эта граница жесткая. Поиск клик известен как проблема клики.

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

А жадная окраска показывает, что каждый граф можно раскрасить на один цвет больше, чем максимальная вершина степень,

${\displaystyle \chi (G)\leq \Delta (G)+1.}$

Полные графики имеют ${\displaystyle \chi (G)=n}$ и ${\displaystyle \Delta (G)=n-1}$, и нечетные циклы имеют ${\displaystyle \chi (G)=3}$ и ${\displaystyle \Delta (G)=2}$, поэтому для этих графов эта оценка является наилучшей. Во всех остальных случаях оценка может быть немного улучшена; Теорема Брукса^[4] утверждает, что

Теорема Брукса: ${\displaystyle \chi (G)\leq \Delta (G)}$ для связного простого графа грамм, пока не грамм полный граф или нечетный цикл.

Нижние оценки хроматического числа

За прошедшие годы было обнаружено несколько нижних оценок хроматических границ:

Граница Хоффмана: Позволять ${\displaystyle W}$ - вещественная симметричная матрица такая, что ${\displaystyle W_{i,j}=0}$ в любое время ${\displaystyle (i,j)}$ не край в ${\displaystyle G}$. Определять ${\displaystyle \chi _{W}(G)=1-{\tfrac {\lambda _{\max }(W)}{\lambda _{\min }(W)}}}$, куда ${\displaystyle \lambda _{\max }(W),\lambda _{\min }(W)}$ - наибольшее и наименьшее собственные значения ${\displaystyle W}$. Определять ${\displaystyle \chi _{H}(G)=\max _{W}\chi _{W}(G)}$, с ${\displaystyle W}$ как указано выше. Потом:

${\displaystyle \chi _{H}(G)\leq \chi (G)}$.

Векторное хроматическое число: Позволять ${\displaystyle W}$ - положительная полуопределенная матрица такая, что ${\displaystyle W_{i,j}\leq -{\tfrac {1}{k-1}}}$ в любое время ${\displaystyle (i,j)}$ это край в ${\displaystyle G}$. Определять ${\displaystyle \chi _{V}(G)}$ быть наименьшим k, для которого такая матрица ${\displaystyle W}$ существуют. потом

${\displaystyle \chi _{V}(G)\leq \chi (G).}$

Число Ловаса: Число Ловаса дополнительного графа также является нижней границей хроматического числа:

${\displaystyle \vartheta ({\bar {G}})\leq \chi (G).}$

Дробное хроматическое число: Дробное хроматическое число графа также является нижней границей хроматического числа:

${\displaystyle \chi _{f}(G)\leq \chi (G).}$

Эти границы упорядочены следующим образом:

${\displaystyle \chi _{H}(G)\leq \chi _{V}(G)\leq \vartheta ({\bar {G}})\leq \chi _{f}(G)\leq \chi (G).}$

Графики с высоким хроматическим числом

Графы с большими кликами имеют высокое хроматическое число, но обратное неверно. В График Грёча является примером 4-хроматического графа без треугольника, и этот пример можно обобщить на Mycielskians.

Теорема Мицельского (Александр Зыков  1949, Ян Мыцельски  1955 ): Существуют графы без треугольников с произвольно высоким хроматическим числом.

Согласно теореме Брукса графы с высоким хроматическим числом должны иметь высокую максимальную степень. Еще одно локальное свойство, приводящее к высокому хроматическому числу, - это наличие большой клики. Но красочность - это не совсем локальное явление: график с высоким обхват локально выглядит как дерево, потому что все циклы длинные, но его хроматическое число не обязательно равно 2:

Теорема (Эрдеш): Существуют графики произвольно большого обхвата и хроматического числа.^[5]

Границы хроматического индекса

Краевая окраска грамм раскраска вершин своего линейный график ${\displaystyle L(G)}$, наоборот. Таким образом,

${\displaystyle \chi '(G)=\chi (L(G)).}$

Существует тесная взаимосвязь между окрашиваемостью ребер и максимальной степенью графа. ${\displaystyle \Delta (G)}$. Поскольку всем ребрам, инцидентным одной вершине, нужен свой цвет, мы имеем

${\displaystyle \chi '(G)\geq \Delta (G).}$

Более того,

Теорема Кёнига: ${\displaystyle \chi '(G)=\Delta (G)}$ если грамм двудольный.

В общем, связь даже сильнее, чем то, что дает теорема Брукса для раскраски вершин:

Теорема Визинга: График максимальной степени ${\displaystyle \Delta }$ имеет краевое хроматическое число ${\displaystyle \Delta }$ или же ${\displaystyle \Delta +1}$.

Другие свойства

Граф имеет k-раскрашивание тогда и только тогда, когда оно имеет ациклическая ориентация для чего самый длинный путь имеет длину не больше k; это Теорема Галлаи – Хассе – Роя – Витавера. (Нешетржил и Оссона де Мендес 2012 ).

Для плоских графов раскраски вершин по существу двойственны нигде-нулевые потоки.

О бесконечных графах известно гораздо меньше. Ниже приведены два из немногих результатов о раскраске бесконечных графов:

• Если все конечные подграфы графа бесконечный граф грамм находятся k-красивый, значит, тоже грамм, в предположении аксиома выбора. Это Теорема де Брейна – Эрдеша из де Брюйн и Эрдёш (1951).
• Если граф допускает полное п-раскраска для каждого п ≥ п₀, он допускает бесконечную полную раскраску (Фосетт 1978 ).

Открытые проблемы

Как указано выше, ${\displaystyle \omega (G)\leq \chi (G)\leq \Delta (G)+1.}$ Гипотеза Рида от 1998 г. заключается в том, что значение существенно ближе к нижней границе, ${\displaystyle \chi (G)\leq \left\lceil {\frac {\omega (G)+\Delta (G)+1}{2}}\right\rceil .}$

В хроматический номер плоскости, где две точки являются соседними, если они имеют единичное расстояние, неизвестно, хотя это одно из 5, 6 или 7. Другое открытые проблемы относительно хроматического числа графиков включают Гипотеза Хадвигера заявляя, что каждый граф с хроматическим числом k имеет полный график на k вершины как незначительный, то Гипотеза Эрдеша – Фабера – Ловаса ограничивая хроматическое число объединений полных графов, имеющих не более одной общей вершины для каждой пары, и Гипотеза Альбертсона что среди k-хроматические графы, полные графы - это графы с наименьшим номер перехода.

Когда Биркгоф и Льюис ввели хроматический полином в своей атаке на теорему о четырех цветах, они предположили, что для плоских графов грамм, многочлен ${\displaystyle P(G,t)}$ не имеет нулей в регионе ${\displaystyle [4,\infty )}$. Хотя известно, что такой хроматический многочлен не имеет нулей в области ${\displaystyle [5,\infty )}$ и это ${\displaystyle P(G,4)\neq 0}$, их гипотеза до сих пор не решена. Также остается нерешенной проблемой характеризовать графы, которые имеют один и тот же хроматический многочлен, и определять, какие многочлены являются хроматическими.

Алгоритмы

Раскраска графика
Решение
Имя	Раскраска графа, раскраска вершин, k-крашивание
Вход	График грамм с п вершины. Целое число k
Выход	Делает грамм допускают правильную раскраску вершин с k цвета?
Продолжительность	O (2 пп)[6]
Сложность	НП-полный
Снижение с	3-Удовлетворенность
Гэри-Джонсон	GT4
Оптимизация
Имя	Хроматическое число
Вход	График грамм с п вершины.
Выход	χ (грамм)
Сложность	NP-жесткий
Аппроксимируемость	O (п (бревно п)^−3(журнал журнала п)^2)
Неприблизимость	O (п^1 − ε) пока не P = NP
Проблема подсчета
Имя	Хроматический полином
Вход	График грамм с п вершины. Целое число k
Выход	Номер п (грамм,k) собственно k-расцветки грамм
Продолжительность	O (2 пп)
Сложность	# P-complete
Аппроксимируемость	FPRAS для ограниченных случаев
Неприблизимость	Нет PTAS если P = NP

Полиномиальное время

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

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

Точные алгоритмы

Перебор для k-колоринг учитывает каждый из ${\displaystyle k^{n}}$ задания k цвета для п вершины и проверяет для каждого, допустимо ли это. Чтобы вычислить хроматическое число и хроматический полином, эта процедура используется для каждого ${\displaystyle k=1,\ldots ,n-1}$, непрактично для всех входных графиков, кроме самых маленьких.

С помощью динамическое программирование и ограничение на количество максимальные независимые множества, k-крашиваемость может быть решена во времени и пространстве ${\displaystyle O(2.4423^{n})}$.^[7] Используя принцип включение – исключение и Йейтс Алгоритм быстрого дзета-преобразования,k- возможность окраски можно решить вовремя ${\displaystyle O(2^{n}n)}$^[6] для любого k. Известно, что более быстрые алгоритмы позволяют раскрашивать в 3 и 4 цвета, что можно решить вовремя. ${\displaystyle O(1.3289^{n})}$^[8] и ${\displaystyle O(1.7272^{n})}$,^[9] соответственно.

Сокращение

В сокращение ${\displaystyle G/uv}$ графа грамм это граф, полученный отождествлением вершин ты и vи удалив все края между ними. Остальные ребра, изначально инцидентные ты или же v теперь инциденты с их идентификацией. Эта операция играет важную роль при анализе раскраски графов.

Хроматическое число удовлетворяет отношение повторения:

${\displaystyle \chi (G)={\text{min}}\{\chi (G+uv),\chi (G/uv)\}}$

из-за Зыков (1949),куда ты и v несмежные вершины и ${\displaystyle G+uv}$ это граф с ребром УФ добавлен. Несколько алгоритмов основаны на оценке этой повторяемости, и результирующее дерево вычислений иногда называют деревом Зыкова. Время работы основано на эвристике выбора вершин. ты и v.

Хроматический многочлен удовлетворяет следующему рекуррентному соотношению

${\displaystyle P(G-uv,k)=P(G/uv,k)+P(G,k)}$

куда ты и v - смежные вершины, а ${\displaystyle G-uv}$ это граф с ребром УФ удаленный. ${\displaystyle P(G-uv,k)}$ представляет собой количество возможных правильных раскрасок графа, где вершины могут иметь одинаковый или разные цвета. Тогда правильные раскраски возникают из двух разных графов. Чтобы объяснить, если вершины ты и v имеют разные цвета, то мы могли бы также рассмотреть график, где ты и v смежные. Если ты и v того же цвета, мы могли бы также рассмотреть граф, где ты и v заключены контракты. Тутте Любопытство по поводу того, какие другие свойства графа удовлетворяют эту повторяемость, привело его к открытию двумерного обобщения хроматического полинома, Полином Тутте.

Эти выражения вызывают рекурсивную процедуру, называемую алгоритм удаления-сокращения, лежащий в основе многих алгоритмов раскраски графов. Время работы удовлетворяет тому же соотношению повторяемости, что и Числа Фибоначчи, поэтому в худшем случае алгоритм работает во времени с полиномиальным множителем ${\displaystyle \left({\tfrac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O(1.6180^{n+m})}$ за п вершины и м края.^[10] Анализ можно улучшить с точностью до полиномиального множителя числа ${\displaystyle t(G)}$ из остовные деревья входного графа.^[11]На практике, ветвь и переплет стратегии и изоморфизм графов отклонение используется, чтобы избежать некоторых рекурсивных вызовов. Время выполнения зависит от эвристики, используемой для выбора пары вершин.

Жадная раскраска

Основная статья: Жадная раскраска

Две жадные раскраски одного и того же графа с использованием разных порядков вершин.Правый пример обобщается на 2-раскрашиваемые графы с п вершины, где жадный алгоритм расходует ${\displaystyle n/2}$ цвета.

В жадный алгоритм рассматривает вершины в определенном порядке ${\displaystyle v_{1}}$,…,${\displaystyle v_{n}}$ и назначает ${\displaystyle v_{i}}$ наименьший доступный цвет, не используемый ${\displaystyle v_{i}}$Соседи среди ${\displaystyle v_{1}}$,…,${\displaystyle v_{i-1}}$, добавляя свежий цвет при необходимости. Качество полученной окраски зависит от выбранной вами расцветки. Существует упорядочение, которое приводит к жадной раскраске с оптимальным количеством ${\displaystyle \chi (G)}$ цвета. С другой стороны, жадные раскраски могут быть сколь угодно плохими; например, граф короны на п вершины могут быть двухцветными, но имеют порядок, приводящий к жадной раскраске с ${\displaystyle n/2}$ цвета.

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

Если вершины упорядочены в соответствии с их градусы, получившаяся жадная раскраска использует не более ${\displaystyle {\text{max}}_{i}{\text{ min}}\{d(x_{i})+1,i\}}$ цветов, максимум на один больше, чем максимальная степень графика. Эту эвристику иногда называют алгоритмом Уэлша – Пауэлла.^[12] Еще одна эвристика из-за Brélaz устанавливает порядок динамически, пока алгоритм продолжает работу, выбирая следующую вершину, смежную с наибольшим числом разных цветов.^[13] Многие другие эвристики раскраски графов аналогичным образом основаны на жадной раскраске для конкретной статической или динамической стратегии упорядочивания вершин, эти алгоритмы иногда называют последовательная окраска алгоритмы.

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

Параллельные и распределенные алгоритмы

В области распределенные алгоритмы, раскраска графа тесно связана с проблемой нарушение симметрии. Современные рандомизированные алгоритмы быстрее при достаточно большой максимальной степени Δ, чем детерминированные алгоритмы. Самые быстрые рандомизированные алгоритмы используют метод многократных испытаний Шнайдер и др.^[14]

В симметричный граф, а детерминированный распределенный алгоритм не может найти правильную раскраску вершин. Некоторая вспомогательная информация необходима, чтобы нарушить симметрию. Стандартное предположение состоит в том, что изначально каждый узел имеет уникальный идентификатор, например, из множества {1, 2, ..., п}. Иначе говоря, мы предполагаем, что нам дан п-раскрашивание. Задача состоит в том, чтобы уменьшать количество цветов от п к, например, Δ + 1. Чем больше цветов используется, например O (Δ) вместо Δ + 1, требуется меньше раундов связи.^[14]

Прямая распределенная версия жадного алгоритма (Δ + 1) -раскраски требует Θ (п) раунды связи в худшем случае - может потребоваться распространение информации с одной стороны сети на другую.

Самый простой интересный случай - это п-цикл. Ричард Коул и Узи Вишкин^[15] показать, что существует распределенный алгоритм, который уменьшает количество цветов от п к О(бревноп) за один синхронный шаг связи. Повторяя ту же процедуру, можно получить 3-раскраску п-цикл в О(бревно*  п) шаги связи (при условии, что у нас есть уникальные идентификаторы узлов).

Функция бревно*, повторный логарифм, является чрезвычайно медленно растущей функцией, «почти постоянной». Следовательно, результат Коула и Вишкина поднял вопрос о том, существует ли постоянное время распределенный алгоритм 3-раскраски п-цикл. Линиал (1992) показал, что это невозможно: любой детерминированный распределенный алгоритм требует Ω (бревно*  п) коммуникационные шаги для уменьшения п-раскрашивание в 3-раскраску в п-цикл.

Технику Коула и Вишкина можно применять и к произвольным графам ограниченной степени; время работы poly (Δ) + О(бревно*  п).^[16] Техника была распространена на графы единичного диска Шнайдер и др.^[17] Самые быстрые детерминированные алгоритмы (Δ + 1) -раскрашивания для малых Δ принадлежат Леониду Баренбойму, Майклу Элькину и Фабиану Куну.^[18] Алгоритм Баренбойма и др. бежит во времени О(Δ) +бревно* (п) / 2, что оптимально с точки зрения п поскольку постоянный множитель 1/2 не может быть улучшен из-за нижней оценки Линиала. Панконези и Шринивасан (1996) использовать сетевые разложения для вычисления раскраски Δ + 1 во времени ${\displaystyle 2^{O\left({\sqrt {\log n}}\right)}}$.

Проблема раскраски ребер также изучалась в распределенной модели. Панконези и Рицци (2001) добиться (2Δ - 1) -раскраски в О(Δ +бревно*  п) время в этой модели. Нижняя оценка распределенной раскраски вершин за счет Линиал (1992) относится и к проблеме распределенной окраски краев.

Децентрализованные алгоритмы

Децентрализованные алгоритмы - это алгоритмы, в которых передача сообщений не разрешена (в отличие от распределенных алгоритмов, в которых происходит локальная передача сообщений), и существуют эффективные децентрализованные алгоритмы, которые раскрашивают граф, если существует надлежащая раскраска. Они предполагают, что вершина способна определять, использует ли какой-либо из ее соседей тот же цвет, что и вершина, то есть существует ли локальный конфликт. Это умеренное предположение во многих приложениях, например. при распределении беспроводных каналов обычно разумно предположить, что станция сможет определить, используют ли другие мешающие передатчики тот же канал (например, путем измерения SINR). Этой сенсорной информации достаточно, чтобы позволить алгоритмам, основанным на обучающих автоматах, найти правильную раскраску графа с вероятностью единица.^[19]

Вычислительная сложность

Раскраска графа сложна в вычислительном отношении. это НП-полный чтобы решить, допускает ли данный граф k-раскрашивание по заданной k кроме случаев k ∈ {0,1,2}. В частности, вычислить хроматическое число NP-сложно.^[20]Проблема 3-раскраски остается NP-полной даже на 4-регулярных планарные графы.^[21] Однако для каждого k > 3, а k-раскраска плоского графа существует теорема четырех цветов, и найти такую ​​раскраску можно за полиномиальное время.

Самый известный алгоритм аппроксимации вычисляет раскраску размера не более чем с коэффициентом O (п(журнал журналап)²(журнал n)⁻³) хроматического числа.^[22] Для всех ε > 0, приближая хроматическое число в пределах п^1−ε является NP-жесткий.^[23]

Также NP-сложно раскрасить трехцветный график в 4 цвета.^[24] и kраскрашиваемый график с k^{(бревно k ) / 25} цвета для достаточно большой постоянной k.^[25]

Вычисление коэффициентов хроматического полинома: # P-hard. Фактически, даже вычисляя значение ${\displaystyle \chi (G,k)}$ # P-сложно в любом рациональная точка k кроме k = 1 и k = 2.^[26] Здесь нет FPRAS для вычисления хроматического полинома в любой рациональной точке k ≥ 1,5 за исключением k = 2, если НП  = RP.^[27]

Для окраски краев доказательство результата Визинга дает алгоритм, который использует не более Δ + 1 цвета. Однако выбор между двумя значениями-кандидатами для краевого хроматического числа является NP-полным.^[28] Что касается алгоритмов аппроксимации, алгоритм Визинга показывает, что хроматическое число края можно аппроксимировать с точностью до 4/3, а результат твердости показывает, что нет (4/3 -ε ) -алгоритм существует для любого ε> 0 пока не P = NP. Это одни из самых старых результатов в литературе по аппроксимационным алгоритмам, хотя ни в одной из статей это понятие явно не используется.^[29]

Приложения

Планирование

Модели раскраски вершин к ряду проблемы с расписанием.^[30] В наиболее чистой форме данный набор заданий должен быть назначен временным интервалам, каждое задание требует одного такого интервала. Задания можно планировать в любом порядке, но пары заданий могут быть в конфликт в том смысле, что они не могут быть назначены одному и тому же временному интервалу, например, потому что они оба полагаются на общий ресурс. Соответствующий граф содержит вершину для каждой работы и ребро для каждой конфликтующей пары работ. Хроматическое число графика ровно минимальное. сковорода, оптимальное время для завершения всех работ без конфликтов.

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

Размещение регистров

Основная статья: Размещение регистров

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

Учебный подход к этой проблеме заключается в моделировании ее как задачи раскраски графа.^[31] Компилятор создает график интерференции, где вершины являются переменными, а ребро соединяет две вершины, если они необходимы одновременно. Если график можно раскрасить k цветов, то любой набор переменных, необходимых одновременно, может быть сохранен не более чем в k регистры.

Другие приложения

Проблема раскраски графа возникает во многих практических областях, таких как сопоставление с образцом, составление расписания занятий спортом, составление расписания рассадки, расписание экзаменов, расписание такси и решение Судоку загадки.^[32]

Другие раскраски

Теория Рамсея

Основная статья: Теория Рамсея

Важный класс неподходящий задача раскраски изучается в Теория Рамсея, где ребрам графа присвоены цвета, и нет ограничений на цвета инцидентных ребер. Простой пример - теорема дружбы, который утверждает, что при любой раскраске ребер ${\displaystyle K_{6}}$, полный граф из шести вершин, получится одноцветный треугольник; часто иллюстрируется высказыванием, что в любой группе из шести человек есть либо три общих незнакомца, либо три общих знакомых. Теория Рамсея занимается обобщением этой идеи для поиска регулярности среди беспорядка, нахождения общих условий существования монохроматических подграфов с заданной структурой.

Другие раскраски

Общая окраска смежных вершин Полная раскраска с дополнительным ограничением, что любые две соседние вершины имеют разные наборы цветов Ациклическая окраска Каждый 2-хроматический подграф ацикличен B-раскраска раскраска вершин, где каждый цветовой класс содержит вершину, у которой есть сосед во всех других цветовых классах. Круговая окраска На основе системы задач, в которых производство осуществляется циклически Покраска Неправильная раскраска вершин, когда каждый цветовой класс индуцирует независимый набор или клику Полная окраска Каждая пара цветов появляется как минимум на одном краю Дефектная окраска Несобственная раскраска вершин, когда каждый цветовой класс индуцирует подграф ограниченной степени. Отличительная окраска Неправильная раскраска вершин, разрушающая все симметрии графа Справедливая окраска Размеры цветовых классов различаются не более чем на один Точная окраска Каждая пара цветов появляется ровно на одном краю Дробное окрашивание Вершины могут иметь несколько цветов, и на каждом ребре сумма цветовых частей каждой вершины не превышает единицы. Гамильтонова раскраска Использует длину самого длинного пути между двумя вершинами, также известную как расстояние объезда. Гармоничная окраска Каждая пара цветов появляется не более чем на одном крае Раскраска заболеваемости Каждая смежная встреча вершины и ребра раскрашена разными цветами. Интервальная окраска края Цвет ребер, пересекающихся в общей вершине, должен быть смежным. Раскраска списка Каждая вершина выбирает из списка цветов Раскраска по краям списка Каждое ребро выбирает из списка цветов L (h, k) -ракраска Разница цветов в соседних вершинах не менее час и разница цветов вершин на расстоянии два не менее k. Частный случай L (2,1) -ракраска.

Ориентированная окраска Учитывает ориентацию ребер графа Раскраска пути Моделирует проблему маршрутизации в графах Раскраска радио Сумма расстояния между вершинами и разницы их цветов больше k + 1, где k - целое положительное число. Раскраска рангов Если две вершины имеют одинаковый цвет я, то каждый путь между ними содержит вершину с цветом больше, чем я Подкраска Несобственная раскраска вершин, где каждый цветовой класс индуцирует объединение клик Раскраска суммы Критерий минимизации - сумма цветов Раскраска звезды Каждый 2-хроматический подграф представляет собой непересекающийся набор звезды Сильная окраска Каждый цвет появляется в каждом разделе одинакового размера ровно один раз. Сильная окраска кромок Края окрашены так, что каждый цветовой класс вызывает сопоставление (эквивалентно окрашиванию квадрата линейного графика) Т-раскраска Абсолютное значение разницы между двумя цветами соседних вершин не должно принадлежать фиксированному набору. Т Общая окраска Вершины и ребра раскрашены Центрированная окраска Каждый подключен индуцированный подграф имеет цвет, который используется ровно один раз Раскраска края без треугольников Края окрашены так, что каждый цветовой класс образует без треугольников подграф Слабая окраска Неправильная раскраска вершин, когда каждый неизолированный узел имеет хотя бы одного соседа с другим цветом

Окрашивание также можно рассматривать для подписанные графики и графики усиления.

Смотрите также

• Краска окраски
• Круговая окраска
• Критический график
• Гомоморфизм графов
• Строительство Hajós
• Математика судоку
• Многостраничный граф
• Уникально раскрашиваемый график
• Игра-раскраска графика
• Интервальная окраска края

Примечания

1. М. Кубале, История раскраски графов, в Кубале (2004)
2. ван Линт и Уилсон (2001, Гл. 33)
3. Дженсен и Тофт (1995), п. 2
4. Брукс (1941)
5. Эрдеш, Пол (1959), «Теория графов и вероятность», Канадский математический журнал, 11: 34–38, Дои:10.4153 / CJM-1959-003-9.
6. Бьёрклунд, Хусфельдт и Койвисто (2009)
7. Лоулер (1976)
8. Бейгель и Эппштейн (2005)
9. Фомин, Гасперс и Саураб (2007)
10. Уилф (1986)
11. Секин, Имаи и Тани (1995)
12. Валлийский и Пауэлл (1967)
13. Brélaz (1979)
14. Шнайдер (2010)
15. Коул и Вишкин (1986), смотрите также Кормен, Лейзерсон и Ривест (1990 г., Раздел 30.5)
16. Гольдберг, Плоткин и Шеннон (1988)
17. Шнайдер (2008)
18. Баренбойм и Элькин (2009); Кун (2009)
19. Например. видеть Лейт и Клиффорд (2006) и Даффи, О'Коннелл и Сапожников (2008).
20. Гэри, Джонсон и Стокмейер (1974); Гэри и Джонсон (1979).
21. Дэйли (1980)
22. Халльдорссон (1993)
23. Цукерман (2007)
24. Гурусвами и Кханна (2000)
25. Хот (2001)
26. Джагер, Вертиган и валлийский (1990)
27. Голдберг и Джеррам (2008)
28. Холиер (1981)
29. Крещенци и Канн (1998)
30. Маркс (2004)
31. Чайтин (1982)
32. Льюис, Р. Руководство по раскраске графиков: алгоритмы и приложения. Издательство Springer International, 2015.

Рекомендации

• Barenboim, L .; Елкин, М. (2009), "Распределенная (Δ + 1) -раскраска за линейное (по Δ) время", Труды 41-го Симпозиум по теории вычислений, стр. 111–120, arXiv:0812.1379, Дои:10.1145/1536414.1536432, ISBN  978-1-60558-506-2, S2CID  13446345
• Beigel, R .; Эппштейн, Д. (2005), «3-раскраска во времени O (1.3289^п)", Журнал алгоритмов, 54 (2)): 168–204, arXiv:cs / 0006046, Дои:10.1016 / j.jalgor.2004.06.008, S2CID  1209067
• Björklund, A .; Husfeldt, T .; Койвисто, М. (2009), "Разбиение множества посредством включения-исключения", SIAM Журнал по вычислениям, 39 (2): 546–563, Дои:10.1137/070683933
• Брелаз, Д. (1979), «Новые методы окраски вершин графа», Коммуникации ACM, 22 (4): 251–256, Дои:10.1145/359094.359101, S2CID  14838769
• Брукс, Р.Л. (1941), «О окраске узлов сети», Труды Кембриджского философского общества, 37 (2): 194–197, Bibcode:1941PCPS ... 37..194B, Дои:10.1017 / S030500410002168X
• де Брёйн, Н.Г.; Эрдеш, П. (1951), «Проблема цвета для бесконечных графов и проблема теории отношений» (PDF), Nederl. Акад. Wetensch. Proc. Сер. А, 54: 371–373, Дои:10.1016 / S1385-7258 (51) 50053-7, заархивировано из оригинал (PDF) на 2016-03-10, получено 2009-05-16 (= Indag. Математика. 13)
• Бысков, J.M. (2004), "Перечисление максимальных независимых множеств с приложениями к раскраске графов", Письма об исследованиях операций, 32 (6): 547–556, Дои:10.1016 / j.orl.2004.03.002

• Чайтин, Г. Дж. (1982), "Размещение регистров и разлив через раскрашивание графа", Proc. 1982 Симпозиум SIGPLAN по созданию компиляторов, стр. 98–105, Дои:10.1145/800230.806984, ISBN  0-89791-074-5, S2CID  16872867
• Cole, R .; Вишкин, У. (1986), "Детерминированное подбрасывание монеты с приложениями к оптимальному ранжированию в параллельном списке", Информация и контроль, 70 (1): 32–53, Дои:10.1016 / S0019-9958 (86) 80023-7
• Cormen, T. H .; Leiserson, C.E .; Ривест, Р. Л. (1990), Введение в алгоритмы (1-е изд.), MIT Press
• Crescenzi, P .; Канн В. (декабрь 1998 г.), "Как найти результаты наилучшего приближения - продолжение Гэри и Джонсона", Новости ACM SIGACT, 29 (4): 90, Дои:10.1145/306198.306210, S2CID  15748200
• Дейли, Д. П. (1980), "Единственность раскрашиваемости и раскрашиваемости плоских 4-регулярных графов NP-полна", Дискретная математика, 30 (3): 289–293, Дои:10.1016 / 0012-365X (80) 90236-8
• Даффи, К .; O'Connell, N .; Сапожников, А. (2008), «Анализ сложности децентрализованного алгоритма раскраски графа» (PDF), Письма об обработке информации, 107 (2): 60–63, Дои:10.1016 / j.ipl.2008.01.002
• Фосетт, Б. В. (1978), "О бесконечных полных раскрасках графов", Может. J. Math., 30 (3): 455–457, Дои:10.4153 / cjm-1978-039-8

• Фомин, Ф.; Гасперс, С .; Саураб, С. (2007), «Улучшенные точные алгоритмы для подсчета 3- и 4-раскрасок», Proc. 13-я ежегодная международная конференция COCOON 2007, Конспект лекций по информатике, 4598, Springer, стр. 65–74, Дои:10.1007/978-3-540-73545-8_9, ISBN  978-3-540-73544-1
• Гарей, М.; Джонсон, Д.С. (1979), Компьютеры и непреодолимость: руководство по теории NP-полноты, W.H. Фриман, ISBN  0-7167-1045-5
• Гарей, М.; Джонсон, Д.С.; Штокмейер, Л. (1974), "Некоторые упрощенные NP-полные задачи", Материалы шестого ежегодного симпозиума ACM по теории вычислений, стр. 47–63, Дои:10.1145/800119.803884, S2CID  207693360
• Гольдберг, Л.А.; Джеррам, М. (Июль 2008 г.), «Непроксимируемость полинома Тутте», Информация и вычисления, 206 (7): 908–929, arXiv:cs / 0605140, Дои:10.1016 / j.ic.2008.04.003, S2CID  53304001
• Гольдберг, А.В.; Плоткин, С. А .; Шеннон, Г. Э. (1988), «Параллельное нарушение симметрии в разреженных графах», Журнал SIAM по дискретной математике, 1 (4): 434–446, Дои:10.1137/0401044
• Гурусвами, V .; Ханна, С. (2000), "О сложности 4-раскраски 3-раскрашиваемого графа", Труды 15-й ежегодной конференции IEEE по вычислительной сложности, стр. 188–197, Дои:10.1109 / CCC.2000.856749, ISBN  0-7695-0674-7, S2CID  47551585
• Халлдорссон, М. М. (1993), «Еще лучшая гарантия производительности для приблизительной раскраски графа», Письма об обработке информации, 45: 19–23, Дои:10.1016/0020-0190(93)90246-6
• Холиер, I. (1981), "NP-полнота раскраски ребер", SIAM Журнал по вычислениям, 10 (4): 718–720, Дои:10.1137/0210055
• Jaeger, F .; Vertigan, D. L .; Уэлш, Д. Дж. А. (1990), "О вычислительной сложности многочленов Джонса и Тутте", Математические труды Кембриджского философского общества, 108 (1): 35–53, Bibcode:1990MPCPS.108 ... 35J, Дои:10.1017 / S0305004100068936
• Jensen, T. R .; Тофт, Б. (1995), Проблемы с раскраской графиков, Wiley-Interscience, Нью-Йорк, ISBN  0-471-02865-7
• Хот, С. (2001), «Улучшенные результаты неприемлемости MaxClique, хроматического числа и приблизительной окраски графа», Proc. 42-й ежегодный Симпозиум по основам информатики, стр. 600–609, Дои:10.1109 / SFCS.2001.959936, ISBN  0-7695-1116-3, S2CID  11987483
• Кубале, М. (2004), Раскраски графиков, Американское математическое общество, ISBN  0-8218-3458-4
• Кун, Ф. (2009), "Слабые раскраски графов: распределенные алгоритмы и приложения", Материалы 21-го Симпозиум по параллелизму в алгоритмах и архитектурах, стр. 138–144, Дои:10.1145/1583991.1584032, ISBN  978-1-60558-606-9, S2CID  8857534
• Лоулер, Э. (1976), "Замечание о сложности проблемы хроматического числа", Письма об обработке информации, 5 (3): 66–67, Дои:10.1016 / 0020-0190 (76) 90065-X
• Leith, D.J .; Клиффорд, П. (2006), "Самоуправляемый алгоритм выбора распределенного канала для WLAN", Proc. RAWNET 2006, Бостон, Массачусетс (PDF), получено 2016-03-03
• Льюис, R.M.R. (2016), Руководство по раскраске графиков: алгоритмы и приложения, Издательство Springer International Publishing, ISBN  978-3-319-25728-0
• Линиал, Н. (1992), "Локальность в алгоритмах распределенных графов", SIAM Журнал по вычислениям, 21 (1): 193–201, CiteSeerX  10.1.1.471.6378, Дои:10.1137/0221015
• van Lint, J. H .; Уилсон, Р. М. (2001), Курс комбинаторики (2-е изд.), Cambridge University Press, ISBN  0-521-80340-3
• Маркс, Даниэль (2004), "Проблемы раскраски графов и их приложения в составлении расписаний", Periodica Polytechnica, Электротехника, 48, стр. 11–16, CiteSeerX  10.1.1.95.4268
• Мыцельски, Дж. (1955), "Sur le coloriage des graphes" (PDF), Коллок. Математика., 3 (2): 161–162, Дои:10,4064 / см-3-2-161-162.
• Нешетржил, Ярослав; Оссона де Мендес, Патрис (2012), «Теорема 3.13», Разреженность: графики, структуры и алгоритмы, Алгоритмы и комбинаторика, 28, Гейдельберг: Springer, стр. 42, Дои:10.1007/978-3-642-27875-4, HDL:10338.dmlcz / 143192, ISBN  978-3-642-27874-7, МИСТЕР  2920058.
• Панконези, Алессандро; Рицци, Ромео (2001), «Некоторые простые распределенные алгоритмы для разреженных сетей» (PDF), Распределенных вычислений, Берлин, Нью-Йорк: Springer-Verlag, 14 (2): 97–100, Дои:10.1007 / PL00008932, ISSN  0178-2770, S2CID  17661948
• Panconesi, A .; Сринивасан, А. (1996), "О сложности декомпозиции распределенной сети", Журнал алгоритмов, 20
• Sekine, K .; Imai, H .; Тани, С. (1995), "Вычисление полинома Тутте графа среднего размера", Proc. 6-й Международный симпозиум по алгоритмам и вычислениям (ISAAC 1995), Конспект лекций по информатике, 1004, Springer, стр. 224–233, Дои:10.1007 / BFb0015427, ISBN  3-540-60573-8
• Шнайдер, Дж. (2010), «Новый метод нарушения распределенной симметрии» (PDF), Труды Симпозиум по принципам распределенных вычислений
• Шнайдер, Дж. (2008), «Алгоритм максимального независимого множества с лог-звездой для графов с ограниченным ростом» (PDF), Труды Симпозиум по принципам распределенных вычислений
• Валлийский, Д. Дж. А .; Пауэлл, М. Б. (1967), "Верхняя граница хроматического числа графа и его применение к задачам планирования времени", Компьютерный журнал, 10 (1): 85–86, Дои:10.1093 / comjnl / 10.1.85
• Уэст, Д. Б. (1996), Введение в теорию графов, Прентис-Холл, ISBN  0-13-227828-6
• Уилф, Х.С. (1986), Алгоритмы и сложность, Прентис – Холл
• Цукерман, Д. (2007), «Линейные экстракторы степени и непроксимируемость максимальной клики и хроматического числа», Теория вычислений, 3: 103–128, Дои:10.4086 / toc.2007.v003a006
• Зыков, А.А. (1949), "О некоторых свойствах линейных комплексов" [О некоторых свойствах линейных комплексов], Мат. Сборник Н.С. (на русском), 24 (66): 163–188, МИСТЕР  0035428. Переведено на английский язык Амер. Математика. Soc. Перевод, 1952, МИСТЕР0051516.

внешняя ссылка

• Высокопроизводительные алгоритмы раскраски графиков Набор из 8 различных алгоритмов (реализованных на C ++), используемых в книге Руководство по раскраске графиков: алгоритмы и приложения (Springer International Publishers, 2015).
• Раскраска График Джозеф Калберсон (программы раскраски графиков)
• КОЛОРАЦИЯ от Джима Эндрюса и Майка Феллоуза - это головоломка с раскраской граф
• Ссылки на исходные коды Graph Coloring
• Код для эффективного вычисления Tutte, Chromatic и Flow Polynomial Гэри Хаггард, Дэвид Дж. Пирс и Гордон Ройл
• Раскраска графа в веб-приложении Хосе Антонио Мартин Х.