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

Все неизоморфные графы с тремя вершинами и их хроматические полиномы по часовой стрелке сверху. Независимый тройной набор: k ³ . Ребро и одна вершина: k ² ( к – 1) . 3-й путь: k ( k – 1) ² . 3-клика: k ( k – 1)( k – 2) .

Хроматический полином — полином-график , изучаемый в алгебраической теории графов , разделе математики . Он подсчитывает количество раскрасок графа как функцию количества цветов и был первоначально определен Джорджем Дэвидом Биркгофом для изучения проблемы четырех цветов . Он был обобщен до полинома Тутта Хасслером Уитни и У. Таттом , связав его с моделью Поттса статистической физики .

История

Джордж Дэвид Биркгоф ввел хроматический полином в 1912 году, определив его только для плоских графов , в попытке доказать теорему о четырёх цветах . Если $P(G,k)$ обозначает количество правильных раскрасок G в k цветов, то можно было бы установить теорему о четырех цветах, показав $P(G,4)>0$для всех планарных графов G . Таким образом он надеялся применить мощные инструменты анализа и алгебры для изучения корней многочленов к задаче комбинаторной раскраски.

Хасслер Уитни обобщил полином Биркгофа с плоского случая на общие графы в 1932 году. В 1968 году Рональд К. Рид спросил, какие полиномы являются хроматическими полиномами некоторого графа (вопрос, который остается открытым), и ввел концепцию хроматически эквивалентных графов. Сегодня хроматические полиномы являются одним из центральных объектов алгебраической теории графов .

Определение

Все правильные раскраски вершин графов вершин с 3 вершинами с использованием k цветов для $k=0,1,2,3$. Хроматический полином каждого графа интерполируется по количеству правильных раскрасок.

графа G Для $P(G,k)$подсчитывает количество своих (собственных) вершин k -раскрасок . Другие часто используемые обозначения включают $P_{G}(k)$, $\chi _{G}(k)$, или $\pi _{G}(k)$. Существует уникальный многочлен $P(G,x)$ значение которого для любого целого числа k ≥ 0 совпадает с $P(G,k)$; называется хроматическим полиномом G он .

Например, чтобы раскрасить граф пути $P_{3}$ на 3 вершинах с k цветами можно выбрать любой из k цветов для первой вершины, любой из $k-1$ оставшиеся цвета для второй вершины и, наконец, для третьей вершины, любой из $k-1$цвета, которые отличаются от выбора второй вершины. Поэтому, $P(P_{3},k)=k\cdot (k-1)\cdot (k-1)$ — количество k -раскрасок $P_{3}$. Таким образом, для переменной x (не обязательно целой) мы имеем $P(P_{3},x)=x(x-1)^{2}=x^{3}-2x^{2}+x$. (Раскраски, которые отличаются только перестановкой цветов или автоморфизмами G, по -прежнему считаются разными.)

Удаление-сокращение

Основная статья: Формула удаления-сокращения

Тот факт, что число k -раскрасок является полиномом от k, следует из рекуррентного соотношения, называемого рекуррентностью удаления-сокращения или фундаментальной теоремой редукции . Он основан на сжатии ребер : для пары вершин $u$ и $v$ график $G/uv$получается путем слияния двух вершин и удаления ребер между ними. Если $u$ и $v$ смежны в G , пусть $G-uv$ обозначим граф, полученный удалением ребра $uv$. Тогда числа k -раскрасок этих графов удовлетворяют:

$P(G,k)=P(G-uv,k)-P(G/uv,k)$

Эквивалентно, если $u$ и $v$ не смежны в G и $G+uv$ это граф с ребром $uv$ добавил, тогда

$P(G,k)=P(G+uv,k)+P(G/uv,k)$

Это следует из наблюдения, что каждая k -раскраска G либо придает разные цвета $u$ и $v$, или тех же цветов. В первом случае это дает (правильную) k -раскраску $G+uv$, а во втором случае дает раскраску $G/uv$. И наоборот, каждая k -раскраска группы G может быть однозначно получена из k -раскраски группы G. $G+uv$ или $G/uv$ (если $u$ и $v$ не смежны в G ).

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

$P(G,x)=x^{n}$ для графа без ребер на n вершинах и

$P(G,x)=P(G-uv,x)-P(G/uv,x)$ для графа G с ребром $uv$ (выбирается произвольно).

Поскольку число k -раскрасок графа без ребер действительно равно $k^{n}$, то индукцией по числу ребер следует, что для всех G многочлен $P(G,x)$совпадает с количеством k -раскрасок в каждой целой точке x = k . В частности, хроматический полином — это единственный интерполяционный полином степени не выше n через точки

$\left\{(0,P(G,0)),(1,P(G,1)),\ldots ,(n,P(G,n))\right\}.$

Любопытство Тутте по поводу того, какие другие инварианты графа удовлетворяют таким повторениям, привело его к открытию двумерного обобщения хроматического многочлена — многочлена Тутте . $T_{G}(x,y)$.

Примеры

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

Треугольник $K_{3}$	$x(x-1)(x-2)$
Полный график $K_{n}$	$x(x-1)(x-2)\cdots (x-(n-1))$
Безграничный граф ${\overline {K}}_{n}$	$x^{n}$
Граф пути $P_{n}$	$x(x-1)^{n-1}$
Любое дерево на n вершинах	$x(x-1)^{n-1}$
Цикл $C_{n}$	$(x-1)^{n}+(-1)^{n}(x-1)$
график Петерсена	$x(x-1)(x-2)\left(x^{7}-12x^{6}+67x^{5}-230x^{4}+529x^{3}-814x^{2}+775x-352\right)$

Свойства

Для фиксированного G на n вершинах хроматический полином $P(G,x)$ — монический многочлен степени ровно n с целыми коэффициентами.

Хроматический полином включает в себя по крайней мере столько же информации о раскрашиваемости G , сколько и хроматическое число. Действительно, хроматическое число — это наименьшее целое положительное число, не являющееся нулем хроматического многочлена.

$\chi (G)=\min\{k\in \mathbb {N} :P(G,k)>0\}.$

Полином, оцененный в $-1$, то есть $P(G,-1)$, дает $(-1)^{|V(G)|}$ числа ациклических ориентаций G раз больше .

Производная, оцененная в 1, $P'(G,1)$ равен хроматическому инварианту $\theta (G)$ до подписи.

Если G имеет n вершин и c компонентов $G_{1},\ldots ,G_{c}$, затем

• Коэффициенты $x^{0},\ldots ,x^{c-1}$ являются нулями.
• Коэффициенты $x^{c},\ldots ,x^{n}$ все ненулевые и чередуются по знаку.
• Коэффициент $x^{n}$ равен 1 (многочлен является моническим ).
• Коэффициент $x^{n-1}$ является $-|E(G)|.$

Мы докажем это индукцией по числу ребер простого графа G с $n$ вершины и $k$края. Когда $k=0$, G — пустой граф. Следовательно, по определению $P(G,x)=x^{n}$. Таким образом, коэффициент $x^{n-1}$ является $0$, что означает, что утверждение верно для пустого графа. Когда $k=1$, как и в G , имеет только одно ребро, $P(G,x)=x^{n}-x^{n-1}$. Таким образом, коэффициент $x^{n-1}$ является $-1=-|E(G)|$. Таким образом, утверждение справедливо для k = 1. Используя сильную индукцию, предположим, что утверждение верно для $k=0,1,2,\ldots ,(k-1)$. Пусть G имеет $k$края. По принципу сокращения-удаления ,

$P(G,x)=P(G-e,x)-P(G/e,x),$

Позволять $P(G-e,x)=x^{n}-a_{n-1}x^{n-1}+a_{n-2}x^{n-2}-\cdots ,$ и $P(G/e,x)=x^{n-1}-b_{n-2}x^{n-2}+b_{n-3}x^{n-3}-\cdots .$
Следовательно $P(G,x)=x^{n}-(a_{n-1}+1)x^{n-1}+\cdots$.
С $G-e$ получается из G удалением всего лишь одного ребра e , $a_{n-1}=k-1$, так $a_{n-1}+1=k$ и, следовательно, утверждение верно для k .

• Коэффициент $x^{1}$ является $(-1)^{n-1}$ умноженное на количество ациклических ориентаций, имеющих уникальный сток в указанной, произвольно выбранной вершине.
• Абсолютные значения коэффициентов каждого хроматического полинома образуют логарифмически вогнутую последовательность .
• $\scriptstyle P(G,x)=P(G_{1},x)P(G_{2},x)\cdots P(G_{c},x)$

Последнее свойство обобщается тем фактом, что если G является k -кликовой суммой $G_{1}$ и $G_{2}$ (т. е. граф, полученный склейкой двух клик по k вершинам), то

$P(G,x)={\frac {P(G_{1},x)P(G_{2},x)}{x(x-1)\cdots (x-k+1)}}.$

Граф G с n вершинами является деревом тогда и только тогда, когда

$P(G,x)=x(x-1)^{n-1}.$

Хроматическая эквивалентность

Три графа с хроматическим полиномом, равным $(x-2)(x-1)^{3}x$.

Два графа называются хроматически эквивалентными , если они имеют одинаковый хроматический полином. Изоморфные графы имеют один и тот же хроматический полином, но неизоморфные графы могут быть хроматически эквивалентными. Например, все деревья с n вершинами имеют один и тот же хроматический полином. В частности, $(x-1)^{3}x$ является хроматическим полиномом как графа-клешни , так и графа путей на 4 вершинах.

Граф является хроматически уникальным, если он определяется своим хроматическим полиномом с точностью до изоморфизма. Другими словами, G хроматически единственна, тогда $P(G,x)=P(H,x)$означало бы, что G и H изоморфны. Все графы циклов хроматически уникальны.

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

Корень , (или ноль ) хроматического многочлена, называемый «хроматическим корнем», — это значение x где $P(G,x)=0$. Хроматические корни очень хорошо изучены. Фактически, первоначальная мотивация Биркгофа для определения хроматического полинома заключалась в том, чтобы показать, что для плоских графов $P(G,x)>0$ для x ≥ 4. Это установило бы теорему о четырех цветах .

Ни один граф не может быть окрашен в 0 цветов, поэтому 0 всегда является хроматическим корнем. Только графы без ребер могут быть одноцветными, поэтому 1 — это хроматический корень каждого графа, имеющего хотя бы одно ребро. С другой стороны, за исключением этих двух точек, ни один граф не может иметь хроматический корень в вещественном числе, меньшем или равном 32/27. Результат Тутте соединяет золотое сечение $\varphi$ с изучением хроматических корней, показав, что хроматические корни существуют очень близко к $\varphi ^{2}$: Если $G_{n}$ представляет собой плоскую триангуляцию сферы, тогда

$P(G_{n},\varphi ^{2})\leq \varphi ^{5-n}.$

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

Раскраски с использованием всех цветов

Для графа G с n вершинами пусть $e_{k}$обозначают количество раскрасок с использованием ровно k цветов вплоть до переименования цветов (поэтому раскраски, которые можно получить друг из друга перестановкой цветов, считаются за одну; раскраски, полученные автоморфизмами G , по -прежнему считаются отдельно). Другими словами, $e_{k}$подсчитывает количество разбиений множества вершин на k (непустые) независимые множества . Затем $k!\cdot e_{k}$подсчитывает количество раскрасок, используя ровно k цветов (с различимыми цветами). Для целого числа x все x -раскраски G могут быть однозначно получены путем выбора целого числа k ≤ x , выбора k цветов для использования из доступных x и раскраски с использованием именно этих k (различимых) цветов. Поэтому:

$P(G,x)=\sum _{k=0}^{x}{\binom {x}{k}}k!\cdot e_{k}=\sum _{k=0}^{x}(x)_{k}\cdot e_{k},$

где $(x)_{k}=x(x-1)(x-2)\cdots (x-k+1)$обозначает падающий факториал . Таким образом, числа $e_{k}$ являются коэффициентами многочлена $P(G,x)$ в основе $1,(x)_{1},(x)_{2},(x)_{3},\ldots$ падающих факториалов.

Позволять $a_{k}$ быть k -м коэффициентом $P(G,x)$ в стандартной базе $1,x,x^{2},x^{3},\ldots$, то есть:

$P(G,x)=\sum _{k=0}^{n}a_{k}x^{k}$

Числа Стирлинга дают изменение базиса между стандартным базисом и базисом падающих факториалов. Из этого следует:

$a_{k}=\sum _{j=0}^{n}(-1)^{j-k}{\begin{bmatrix}j\\k\end{bmatrix}}e_{j}$ и $e_{k}=\sum _{j=0}^{n}{\begin{Bmatrix}j\\k\end{Bmatrix}}a_{j}.$

Категоризация

Хроматический многочлен классифицируется теорией гомологии, тесно связанной с гомологиями Хованова .

Алгоритмы

Хроматический полином
Вход	Граф G с n вершинами.
Выход	Коэффициенты $P(G,x)$
Продолжительность	$O(2^{n}n^{r})$ для некоторой константы $r$
Сложность	#P -жесткий
Сокращение с	#3САТ

#k-раскраски
Вход	Граф G с n вершинами.
Выход	$P(G,k)$
Продолжительность	В P для $k=0,1,2$. $O(1.6262^{n})$ для $k=3$. В противном случае $O(2^{n}n^{r})$ для некоторой константы $r$
Сложность	#P -трудно, если только $k=0,1,2$
Аппроксимируемость	Нет FPRAS для $k>2$

Вычислительные проблемы, связанные с хроматическим полиномом, включают:

• нахождение хроматического многочлена $P(G,x)$ данного графа G ;
• оценивая $P(G,x)$ при фиксированном x для G. данного

Первая проблема более общая, поскольку если бы мы знали коэффициенты $P(G,x)$мы могли бы оценить его в любой момент полиномиального времени, потому что степень равна n . Сложность задач второго типа сильно зависит от значения x и интенсивно изучается в области вычислительной сложности . Когда x — натуральное число, эту задачу обычно рассматривают как вычисление количества x -раскрасок данного графа. Например, сюда входит задача #3-раскраска подсчёта количества 3-раскрасок, каноническая задача исследования сложности счёта, полная для счётного класса #P .

Эффективные алгоритмы

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

Известны алгоритмы полиномиального времени для вычисления хроматического полинома для более широких классов графов, включая хордальные графы. и графики ограниченной кликовой ширины . Последний класс включает кографы и графы ограниченной древовидной ширины , такие как внешнепланарные графы .

Удаление-сокращение

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

$\varphi ^{n+m}=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+m}\in O\left(1.62^{n+m}\right),$

на графе с n вершинами и m ребрами. Анализ можно улучшить с точностью до полиномиального коэффициента числа $t(G)$ остовных деревьев входного графа. На практике, ветвей и границ чтобы избежать некоторых рекурсивных вызовов, используются стратегии и отказ от изоморфизма графа. Время выполнения зависит от эвристики, используемой для выбора пары вершин.

Метод куба

Существует естественный геометрический взгляд на раскраски графов, если заметить, что при присвоении каждой вершине натуральных чисел раскраска графа представляет собой вектор в целочисленной решетке. Поскольку две вершины $i$ и $j$ получение одного и того же цвета эквивалентно $i$'й и $j$'-я координата в векторе раскраски равна, каждому ребру можно сопоставить гиперплоскость вида $\{x\in \mathbb {R} ^{d}:x_{i}=x_{j}\}$. Совокупность таких гиперплоскостей данного графа называется его графической компоновкой . Правильные раскраски графа — это те точки решетки, которые избегают запрещенных гиперплоскостей. Ограничиваясь набором $k$ цвета, точки решетки содержатся в кубе $[0,k]^{n}$. В этом контексте хроматический полином подсчитывает количество точек решетки в $[0,k]$-куб, избегающий графического расположения.

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

Задача вычисления количества 3-раскрасок данного графа является каноническим примером #P -полной задачи, поэтому задача вычисления коэффициентов хроматического полинома является #P-трудной. Аналогично, оценивая $P(G,3)$для данного G #P-полна. С другой стороны, для $k=0,1,2$ это легко вычислить $P(G,k)$, поэтому соответствующие задачи вычислимы за полиномиальное время. Для целых чисел $k>3$ проблема #P-hard, которая устанавливается аналогично случаю $k=3$. На самом деле известно, что $P(G,x)$ является #P-сложным для всех x (включая отрицательные целые числа и даже все комплексные числа ), за исключением трех «простых точек». Таким образом, с точки зрения #P-трудности полностью понятна сложность вычисления хроматического полинома.

В расширении

$P(G,x)=a_{1}x+a_{2}x^{2}+\cdots +a_{n}x^{n},$

коэффициент $a_{n}$всегда равен 1, и известны некоторые другие свойства коэффициентов. В связи с этим возникает вопрос, легко ли вычислить некоторые коэффициенты. Однако вычислительная задача вычисления a _r для фиксированного r ≥ 1 и заданного графа G является #P-сложной даже для двудольных плоских графов.

Никаких аппроксимирующих алгоритмов для вычислений $P(G,x)$известны для любого x, кроме трех простых точек. В целочисленных точках $k=3,4,\ldots$соответствующая проблема принятия решения о том, может ли данный граф быть k -цветным, является NP-трудной . Такие задачи не могут быть аппроксимированы каким-либо мультипликативным коэффициентом с помощью вероятностного алгоритма с ограниченной ошибкой, если только NP = RP, поскольку любое мультипликативное приближение будет различать значения 0 и 1, эффективно решая версию решения за вероятностное полиномиальное время с ограниченной ошибкой. В частности, при том же предположении это исключает возможность полностью полиномиальной схемы рандомизированной аппроксимации (FPRAS) . нет FPRAS Для вычислений $P(G,x)$ для любого x > 2, если только не выполняется NP = RP .

Ссылки

• Биггс, Н. (1993), Алгебраическая теория графов , издательство Кембриджского университета, ISBN  978-0-521-45897-9
• Чао, Южная Корея; Уайтхед, Э.Г. (1978), «О хроматической эквивалентности графов», Теория и приложения графов , Конспекты лекций по математике, том. 642, Спрингер, стр. 121–131, ISBN.  978-3-540-08666-6
• Донг, FM; Кох, КМ; Тео, К.Л. (2005), Хроматические полиномы и цветность графов , World Scientific Publishing Company, ISBN  978-981-256-317-0
• Эллис-Монаган, Джоанна А .; Мерино, Криэль (2011), «Полиномы в графах и их приложения I: Полином Тутте», в Демере, Маттиасе (ред.), Структурный анализ сложных сетей , arXiv : 0803.3079 , doi : 10.1007/978-0-8176-4789 -6_9 , ISBN  978-0-8176-4789-6 , S2CID   585250
• Хименес, О.; Хлинены, П.; Ной, М. (2005), «Вычисление полинома Тутте на графах ограниченной ширины клики», Proc. 31-й Международный. Воркш. Теоретико-графовые концепции в информатике (WG 2005) , Конспекты лекций по информатике, том. 3787, Springer-Verlag, стр. 59–68, CiteSeerX   10.1.1.353.6385 , doi : 10.1007/11604686_6 , ISBN  978-3-540-31000-6
• Голдберг, Луизиана ; Джеррам, М. (2008), «Неприближаемость полинома Тутта», Information and Computation , 206 (7): 908, arXiv : cs/0605140 , doi : 10.1016/j.ic.2008.04.003 , S2CID   53304001
• Хельме-Гизон, Лора; Ронг, Юнву (2005), «Категорификация хроматического полинома», Algebraic & Geometric Topology , 5 (4): 1365–1388, arXiv : math/0412264 , doi : 10.2140/agt.2005.5.1365 , S2CID   1339633
• Ха, июнь (2012 г.), «Числа Милнора проективных гиперповерхностей и хроматический полином графов», Журнал Американского математического общества , 25 (3): 907–927, arXiv : 1008.4749 , doi : 10.1090/S0894-0347-2012 -00731-0 , МР   2904577 , С2КИД   13523955
• Джексон, Б. (1993), «Интервал без нуля для хроматических полиномов графов», Combinatorics, Probability and Computing , 2 (3): 325–336, doi : 10.1017/S0963548300000705 , S2CID   39978844
• Джагер, Ф.; Вертиган, ДЛ; Уэлш, DJA (1990), «О вычислительной сложности полиномов Джонса и Тутта», Mathematical Proceedings of the Cambridge Philosophical Society , 108 (1): 35–53, Bibcode : 1990MPCPS.108...35J , doi : 10.1017 /S0305004100068936 , S2CID   121454726
• Линиал, Н. (1986), «Трудные задачи перечисления в геометрии и комбинаторике», SIAM J. Algebr. Дискретные методы , 7 (2): 331–335, doi : 10.1137/0607036.
• Маковский, Дж. А.; Ротикс, У.; Авербуш, И.; Годлин, Б. (2006), «Вычисление полиномов графа на графах ограниченной ширины клики», Proc. 32-й Международный Воркш. Теоретико-графовые концепции в информатике (WG 2006) , Конспекты лекций по информатике, том. 4271, Springer-Verlag, стр. 191–204, CiteSeerX   10.1.1.76.2320 , doi : 10.1007/11917496_18 , ISBN  978-3-540-48381-6
• Наор, Дж.; Наор, М.; Шаффер, А. (1987), "Быстрые параллельные алгоритмы для хордальных графов", Proc. 19-й симпозиум ACM. Теория вычислений (STOC '87) , стр. 355–364, doi : 10.1145/28395.28433 , ISBN  978-0897912211 , S2CID   12132229 .
• Оксли, Дж. Г.; Уэлш, DJA (2002), «Хроматические полиномы, полиномы потока и надежности: сложность их коэффициентов», Combinatorics, Probability and Computing , 11 (4): 403–426, doi : 10.1017/S0963548302005175 , S2CID   14918970
• Пеммараджу, С.; Скиена, С. (2003), Вычислительная дискретная математика: комбинаторика и теория графов с Mathematica , Cambridge University Press, раздел 7.4.2, ISBN  978-0-521-80686-2
• Рид, RC (1968), «Введение в хроматические полиномы» (PDF) , Журнал комбинаторной теории , 4 : 52–71, doi : 10.1016/S0021-9800(68)80087-0
• Секине, Кёко; Имаи, Хироши; Тани, Сейитиро (1995), «Вычисление полинома Тутте для графика среднего размера», в Стейплс, Джон; Идс, Питер; Като, Наоки; Моффат, Алистер (ред.), «Алгоритмы и вычисления», 6-й Международный симпозиум, ISAAC '95, Кэрнс, Австралия, 4–6 декабря 1995 г., Труды , конспекты лекций по информатике, том. 1004, Springer, стр. 224–233, doi : 10.1007/BFb0015427 , ISBN.  978-3-540-60573-7
• Сокал, А.Д. (2004), «Хроматические корни плотны во всей комплексной плоскости», Combinatorics, Probability and Computing , 13 (2): 221–261, arXiv : cond-mat/0012369 , doi : 10.1017/S0963548303006023 , S2CID   5549332
• Стэнли, Р.П. (1973), «Ациклические ориентации графов» (PDF) , Discrete Math. , 5 (2): 171–178, doi : 10.1016/0012-365X(73)90108-8
• Волошин, Виталий И. (2002), Раскраска смешанных гиперграфов: теория, алгоритмы и приложения. , Американское математическое общество, ISBN  978-0-8218-2812-0
• Уилф, HS (1986), Алгоритмы и сложность , Прентис-Холл, ISBN  978-0-13-021973-2

Внешние ссылки

• Вайсштейн, Эрик В. , «Хроматический полином» , MathWorld
• PlanetMath. Хроматический полином Архивировано 20 августа 2008 г. в Wayback Machine.
• Код для вычисления полиномов Тутте, хроматических и потоковых полиномов Гэри Хаггарда, Дэвида Дж. Пирса и Гордона Ройла: [1]