Полином Тутте

Эта статья о полиноме Тутте графа. Чтобы узнать о полиноме Тутте матроида, см. Matroid .

Полином $x^{4}+x^{3}+x^{2}y$ – полином Тутте бычьего графа . Красной линией показано пересечение с плоскостью $y=0$, что по существу эквивалентно хроматическому многочлену.

Полином Тутта , также называемый дихроматом или полиномом Тутта-Уитни , является полиномом-графиком . Это полином от двух переменных, который играет важную роль в теории графов . Он определен для каждого неориентированного графа $G$ и содержит информацию о том, как связан граф. Это обозначается $T_{G}$.

Важность этого полинома обусловлена ​​содержащейся в нем информацией о $G$. Хотя первоначально она изучалась в алгебраической теории графов как обобщение задач счета, связанных с раскраской графов и потоком, не имеющим нигде нуля , она содержит несколько известных других специализаций из других наук, таких как полином Джонса из теории узлов и статистические суммы модели Поттса из статистической теории. физика . Это также источник нескольких центральных вычислительных проблем в теоретической информатике .

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

Определения

Определение. Для неориентированного графа $G=(V,E)$ можно определить полином Тутте как

$T_{G}(x,y)=\sum \nolimits _{A\subseteq E}(x-1)^{k(A)-k(E)}(y-1)^{k(A)+|A|-|V|},$

где $k(A)$ обозначает количество компонент связности графа $(V,A)$. Из этого определения ясно, что $T_{G}$ корректно определен и является полиномом по $x$ и $y$.

То же определение можно дать, используя несколько иные обозначения, полагая $r(A)=|V|-k(A)$ обозначаем ранг графа $(V,A)$. Тогда производящая функция ранга Уитни определяется как

$R_{G}(u,v)=\sum \nolimits _{A\subseteq E}u^{r(E)-r(A)}v^{|A|-r(A)}.$

Эти две функции эквивалентны при простой замене переменных:

$T_{G}(x,y)=R_{G}(x-1,y-1).$

Тутте Дихроматический полином $Q_{G}$ является результатом другого простого преобразования:

$T_{G}(x,y)=(x-1)^{-k(G)}Q_{G}(x-1,y-1).$

Первоначальное определение Тутте $T_{G}$ эквивалентно, но его труднее сформулировать. Для подключенных $G$ мы устанавливаем

$T_{G}(x,y)=\sum \nolimits _{i,j}t_{ij}x^{i}y^{j},$

где $t_{ij}$ обозначает количество связующих деревьев внутренней активности $i$ и внешняя деятельность $j$.

Третье определение использует повторение удаления-сокращения . Сокращение края $G/uv$ графа $G$ — граф, полученный слиянием вершин $u$ и $v$ и снимаем край $uv$. Мы пишем $G-uv$ для графа, где ребро $uv$ просто удаляется. Тогда полином Тутте определяется рекуррентным соотношением

$T_{G}=T_{G-e}+T_{G/e},$

если $e$ не является ни циклом , ни мостом , в базовом случае

$T_{G}(x,y)=x^{i}y^{j},$

если $G$ содержит $i$ мосты и $j$ петель и никаких других ребер. Особенно, $T_{G}=1$ если $G$ не содержит ребер.

Модель случайного кластера из статистической механики, предложенная Фортуином и Кастелейном (1972), дает еще одно эквивалентное определение. Сумма раздела

$Z_{G}(q,w)=\sum \nolimits _{F\subseteq E}q^{k(F)}w^{|F|}$

эквивалентно $T_{G}$ под трансформацией

$T_{G}(x,y)=(x-1)^{-k(E)}(y-1)^{-|V|}\cdot Z_{G}{\Big (}(x-1)(y-1),\;y-1{\Big )}.$

Свойства

Полином Тутте разлагается на компоненты связности. Если $G$ это объединение непересекающихся графов $H$ и $H'$ затем

$T_{G}=T_{H}\cdot T_{H'}$

Если $G$ является плоским и $G^{*}$ обозначает его двойственный граф, тогда

$T_{G}(x,y)=T_{G^{*}}(y,x)$

В частности, хроматический полином плоского графа является полиномом потока его двойственного графа. Тутте называет такие функции V-функциями .

Примеры

Изоморфные графы имеют один и тот же полином Тутте, но обратное неверно. Например, полином Тутте каждого дерева на $m$ края это $x^{m}$.

Полиномы Тутте часто задаются в табличной форме путем перечисления коэффициентов. $t_{ij}$ из $x^{i}y^{j}$ в ряд $i$ и столбец $j$. Например, полином Тутте графа Петерсена ,

${\begin{aligned}36x&+120x^{2}+180x^{3}+170x^{4}+114x^{5}+56x^{6}+21x^{7}+6x^{8}+x^{9}\\&+36y+84y^{2}+75y^{3}+35y^{4}+9y^{5}+y^{6}\\&+168xy+240x^{2}y+170x^{3}y+70x^{4}y+12x^{5}y\\&+171xy^{2}+105x^{2}y^{2}+30x^{3}y^{2}\\&+65xy^{3}+15x^{2}y^{3}\\&+10xy^{4},\end{aligned}}$

дается следующей таблицей.

0	36	84	75	35	9	1
36	168	171	65	10
120	240	105	15
180	170	30
170	70
114	12
56
21
6
1

Другой пример: полином Тутте графа октаэдра имеет вид

${\begin{aligned}&12\,{y}^{2}{x}^{2}+11\,x+11\,y+40\,{y}^{3}+32\,{y}^{2}+46\,yx+24\,x{y}^{3}+52\,x{y}^{2}\\&+25\,{x}^{2}+29\,{y}^{4}+15\,{y}^{5}+5\,{y}^{6}+6\,{y}^{4}x\\&+39\,y{x}^{2}+20\,{x}^{3}+{y}^{7}+8\,y{x}^{3}+7\,{x}^{4}+{x}^{5}\end{aligned}}$

История

У. Т. Тутта Интерес к формуле делеции-сокращения начался еще во время его учебы в Тринити-колледже в Кембридже , первоначально он был мотивирован идеальными прямоугольниками и связующими деревьями . Он часто применял эту формулу в своих исследованиях и «задавался вопросом, существуют ли другие интересные функции графов, инвариантные относительно изоморфизма , с подобными формулами рекурсии». Р. М. Фостер уже заметил, что хроматический полином является одной из таких функций, и Тутте начал открывать больше. Его исходной терминологией для инвариантов графа, удовлетворяющих рекурсии удаления-сжатия, была W-функция и V-функция , если она мультипликативна по компонентам. Татт пишет: «Играя со своими W-функциями , я получил полином с двумя переменными, из которого можно было получить либо хроматический полином, либо полином потока, установив одну из переменных равной нулю и подкорректировав знаки». Тутте назвал эту функцию дихроматом , так как видел в ней обобщение хроматического полинома на две переменные, но обычно ее называют полиномом Тутте. По словам Тутте: «Это может быть несправедливо по отношению к Хасслеру Уитни , который знал и использовал аналогичные коэффициенты, не удосужившись прикрепить их к двум переменным». (Имеется «заметная путаница» о терминах «дихромат» и «дихроматический полином» , введенных Тутте в разных статьях и которые различаются лишь незначительно.) Обобщение полинома Тутте на матроиды было впервые опубликовано Крапо , хотя оно появляется уже в диссертации Тутте.

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

Специализации

В различных точках и линиях $(x,y)$На плоскости полином Тутте оценивает величины, которые сами по себе изучались в различных областях математики и физики. Частично привлекательность полинома Тутте обусловлена ​​объединяющей структурой, которую он обеспечивает для анализа этих величин.

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

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

Хроматический полином, нарисованный на плоскости Тутте.

В $y=0$, полином Тутте специализируется на хроматическом многочлене,

$\chi _{G}(\lambda )=(-1)^{|V|-k(G)}\lambda ^{k(G)}T_{G}(1-\lambda ,0),$

где $k(G)$ обозначает количество компонент связности G .

Для целого числа λ значение хроматического многочлена $\chi _{G}(\lambda )$ равно количеству раскрасок вершин графа G с использованием набора цветов λ. Ясно, что $\chi _{G}(\lambda )$ не зависит от набора цветов. Менее ясно то, что это оценка в точке λ многочлена с целыми коэффициентами. Чтобы убедиться в этом, мы наблюдаем:

1. Если G имеет n вершин и не имеет ребер, то $\chi _{G}(\lambda )=\lambda ^{n}$.
2. Если G содержит петлю (единственное ребро, соединяющее вершину с самой собой), то $\chi _{G}(\lambda )=0$.
3. Если e — ребро, не являющееся петлей, то

$\chi _{G}(\lambda )=\chi _{G-e}(\lambda )-\chi _{G/e}(\lambda ).$

Три приведенных выше условия позволяют нам рассчитать $\chi _{G}(\lambda )$, применяя последовательность удалений и сокращений ребер; но они не дают гарантии, что другая последовательность делений и сокращений приведет к тому же значению. Гарантия исходит из того, что $\chi _{G}(\lambda )$ что-то считает, независимо от повторения. В частности,

$T_{G}(2,0)=(-1)^{|V|}\chi _{G}(-1)$

дает количество ациклических ориентаций.

Полином Джонса

Основная статья: полином Джонса

Полином Джонса, нарисованный на плоскости Тутте.

Вдоль гиперболы $xy=1$полином Тутте плоского графа специализируется на полиноме Джонса соответствующего знакопеременного узла .

Индивидуальные баллы

(2,1)

$T_{G}(2,1)$ подсчитывает количество лесов , т. е. количество ациклических подмножеств ребер.

(1,1)

$T_{G}(1,1)$ подсчитывает количество связующих лесов (реберных подмножеств без циклов и того же количества связных компонентов, что и G ). Если граф связен, $T_{G}(1,1)$ подсчитывает количество связующих деревьев.

(1,2)

$T_{G}(1,2)$ подсчитывает количество охватывающих подграфов (реберных подмножеств с тем же количеством связных компонентов, что и G ).

(2,0)

$T_{G}(2,0)$ подсчитывает количество ориентаций G . ациклических

(0,2)

$T_{G}(0,2)$ подсчитывает количество сильно связных G . ориентаций

(2,2)

$T_{G}(2,2)$ это число $2^{|E|}$ где $|E|$ количество ребер графа G. —

(0,−2)

Если G — 4-регулярный граф, то

$(-1)^{|V|+k(G)}T_{G}(0,-2)$

подсчитывает количество ориентаций G . эйлеровых Здесь $k(G)$ — количество компонент связности G .

(3,3)

Если G — m × n сеточный граф размера , то $2T_{G}(3,3)$ подсчитывает количество способов замостить прямоугольник шириной 4 м и высотой 4 n Т -тетромино .

Если G — планарный граф , то $2T_{G}(3,3)$ равно сумме по взвешенным эйлеровым ориентациям в медиальном графе G в , где вес ориентации равен 2 числу седловых вершин ориентации (то есть количеству вершин с инцидентными ребрами, циклически упорядоченными «внутри, наружу, вне").

и

Основные статьи: модель Изинга и модель Поттса

Статистические суммы для модели Изинга и моделей Поттса с 3 и 4 состояниями, нарисованные на плоскости Тутте.

Определите гиперболу в плоскости xy :

$H_{2}:\quad (x-1)(y-1)=2,$

полином Тутте специализируется на статистической сумме, $Z(\cdot ),$ модели Изинга, изучаемой в статистической физике . В частности, вдоль гиперболы $H_{2}$ эти два связаны уравнением:

$Z(G)=2\left(e^{-\alpha }\right)^{|E|-r(E)}\left(4\sinh \alpha \right)^{r(E)}T_{G}\left(\coth \alpha ,e^{2\alpha }\right).$

В частности,

$(\coth \alpha -1)\left(e^{2\alpha }-1\right)=2$

для всех комплексных α.

В более общем смысле, если для любого положительного целого числа q мы определяем гиперболу:

$H_{q}:\quad (x-1)(y-1)=q,$

тогда полином Татта специализируется на статистической сумме с q -состоянием модели Поттса . Различные физические величины, анализируемые в рамках модели Поттса, передаются конкретным частям модели. $H_{q}$.

Соответствия между моделью Поттса и плоскостью Тутте

Модель Поттса	Полином Тутте
Ферромагнитный	Положительная ветвь $H_{q}$
антиферромагнитный	Отрицательная ветвь $H_{q}$ с $y>0$
Высокая температура	Асимптота $H_{q}$ к $y=1$
Низкотемпературный ферромагнитный	Положительная ветвь $H_{q}$ асимптотический к $x=1$
Антиферромагнетик при нулевой температуре	Граф q -раскраска , т.е. $x=1-q,y=0$

Полином потока

Основная статья: Нигде-нулевой поток

Полином потока, нарисованный на плоскости Тутте

В $x=0$, полином Тутте специализируется на полиноме потока, изучаемом в комбинаторике. Для связного и неориентированного графа G и целого числа k нигде ненулевой k -поток представляет собой присвоение значений «потока». $1,2,\dots ,k-1$ к ребрам произвольной ориентации графа G таким, что полный поток, входящий и выходящий из каждой вершины, конгруэнтен по модулю k . Полином потока $C_{G}(k)$ обозначает число нигде ненулевых k -потоков. Это значение тесно связано с хроматическим полиномом: фактически, если G — планарный граф , хроматический полином G эквивалентен полиному потока его двойственного графа. $G^{*}$ в том смысле, что

Теорема (Все).

$C_{G}(k)=k^{-1}\chi _{G^{*}}(k).$

Связь с полиномом Тутте определяется следующим образом:

$C_{G}(k)=(-1)^{|E|-|V|+k(G)}T_{G}(0,1-k).$

Полином надежности

Основная статья: Связность (теория графов)

Полином надежности, нарисованный на плоскости Тутте

В $x=1$, полином Тутте специализируется на полиноме всетерминальной надежности, изучаемом в теории сетей. Для связного графа G удалите каждое ребро с вероятностью p ; это моделирует сеть, подверженную случайным сбоям на краях. Тогда полином надежности является функцией $R_{G}(p)$, полином от p , который дает вероятность того, что каждая пара вершин в G останется соединенной после выхода из строя ребер. Связь с полиномом Тутте определяется выражением

$R_{G}(p)=(1-p)^{|V|-k(G)}p^{|E|-|V|+k(G)}T_{G}\left(1,{\tfrac {1}{p}}\right).$

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

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

$Q_{G}(u,v)=\sum \nolimits _{A\subseteq E}u^{k(A)}v^{|A|-|V|+k(A)},$

где $k(A)$ — количество связных компонентов охватывающего подграфа ( V , A ). Это связано с полиномом недействительности коранга соотношением

$Q_{G}(u,v)=u^{k(G)}\,R_{G}(u,v).$

Дихроматический полином не обобщается на матроиды, потому что k ( A ) не является свойством матроида: разные графы с одним и тем же матроидом могут иметь разное количество компонентов связности.

Связанные полиномы

Полином Мартина

Полином Мартина $m_{\vec {G}}(x)$ ориентированного 4-регулярного графа ${\vec {G}}$ был определен Пьером Мартеном в 1977 году. Он показал, что если G — плоский граф и ${\vec {G}}_{m}$ является его направленным медиальным графом , тогда

$T_{G}(x,x)=m_{{\vec {G}}_{m}}(x).$

Алгоритмы

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

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

Алгоритм удаления-сокращения, примененный к ромбовидному графу . Красные края удаляются у левого дочернего элемента и сжимаются у правого дочернего элемента. Полученный полином представляет собой сумму мономов на листьях: $x^{3}+2x^{2}+y^{2}+2xy+x+y$. На основе Welsh & Merino (2000) .

Рекуррентность удаления-сжатия для полинома Тутте,

$T_{G}(x,y)=T_{G\setminus e}(x,y)+T_{G/e}(x,y),\qquad e{\text{ not a loop nor a bridge.}}$

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

Базовый случай – моном $x^{m}y^{n}$ где m — количество мостов, а n — количество петель.

В пределах полиномиального коэффициента время работы t этого алгоритма можно выразить через количество вершин n и количество ребер m графа:

$t(n+m)=t(n+m-1)+t(n+m-2),$

рекуррентное соотношение, которое масштабируется как числа Фибоначчи с решением

$t(n+m)=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O\left(1.6180^{n+m}\right).$

Анализ можно улучшить с точностью до полиномиального коэффициента числа $\tau (G)$ остовных деревьев входного графа. Для разреженных графов с $m=O(n)$ это время работы $\exp(O(n))$. Для регулярных графов степени k количество остовных деревьев может быть ограничено величиной

$\tau (G)=O\left(\nu _{k}^{n}n^{-1}\log n\right),$

где

$\nu _{k}={\frac {(k-1)^{k-1}}{(k^{2}-2k)^{{\frac {k}{2}}-1}}}.$

поэтому алгоритм удаления-сокращения работает в пределах полиномиального коэффициента этой границы. Например:

$\nu _{5}\approx 4.4066.$

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

Исключение по Гауссу

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

$T_{G}(1,1)$ равно числу $\tau (G)$ остовных деревьев связного графа. Этовычислимая за полиномиальное время как определитель максимальной главной подматрицы матрицы Лапласа G дереве , ранний результат в алгебраической теории графов, известный как теорема Кирхгофа о матрице- . Аналогичным образом, размер велосипедного пространства в $T_{G}(-1,-1)$ может быть вычислено за полиномиальное время методом исключения Гаусса.

Для плоских графов статистическая сумма модели Изинга, т. е. полином Тутте на гиперболе $H_{2}$, может быть выражено как пфаффиан и эффективно вычислено с помощью алгоритма FKT . Эта идея была развита Фишером , Кастелином и Темперли для вычисления числа димерных покрытий модели плоской решетки .

Цепь Маркова

Используя метод Монте-Карло с использованием цепей Маркова , полином Тутте можно сколь угодно хорошо аппроксимировать вдоль положительной ветви $H_{2}$, что эквивалентно статистической сумме ферромагнитной модели Изинга. При этом используется тесная связь между моделью Изинга и проблемой подсчета совпадений в графе. Идея, лежащая в основе этого знаменитого результата Джеррама и Синклера заключается в создании цепи Маркова , состояния которой являются соответствиями входного графа. Переходы определяются случайным выбором ребер и соответствующим изменением сопоставления. Полученная цепь Маркова быстро перемешивается и приводит к «достаточно случайным» сопоставлениям, которые можно использовать для восстановления статистической суммы с использованием случайной выборки. Полученный алгоритм представляет собой полностью полиномиальную схему рандомизированной аппроксимации (fpras).

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

С полиномом Тутте связано несколько вычислительных проблем. Самый простой из них

Входные данные: график $G$

Выходные данные: коэффициенты $T_{G}$

В частности, выходные данные позволяют оценить $T_{G}(-2,0)$ что эквивалентно подсчету количества 3-раскрасок G . Этот последний вопрос #P-полный , даже если он ограничен семейством плоских графов , поэтому проблема вычисления коэффициентов полинома Тутта для данного графа является #P-трудной даже для плоских графов.

Гораздо больше внимания было уделено семейству задач под названием Тутте. $(x,y)$ определено для каждой комплексной пары $(x,y)$:

Входные данные: график $G$

Выход: значение $T_{G}(x,y)$

Сложность этих задач зависит от координат $(x,y)$.

Точный расчет

Самолет Тутте. Каждая точка $(x,y)$ в реальной плоскости соответствует вычислительной задаче $T_{G}(x,y)$. В любой красной точке задача вычислима за полиномиальное время; в любой синей точке проблема в целом #P-сложна, но вычислима за полиномиальное время для плоских графов; и в любой точке белых областей проблема #P-трудна даже для двудольных плоских графов.

Если и x, и y — целые неотрицательные числа, проблема $T_{G}(x,y)$ принадлежит #P . Для общих пар целых чисел полином Тутта содержит отрицательные члены, что помещает проблему в класс сложности GapP , замыкание #P при вычитании. Для размещения рациональных координат $(x,y)$, можно определить рациональный аналог #P .

Вычислительная сложность точных вычислений $T_{G}(x,y)$ попадает в один из двух классов для любого $x,y\in \mathbb {C}$. Проблема #P-сложная, если только $(x,y)$ лежит на гиперболе $H_{1}$ или это один из пунктов

$\left\{(1,1),(-1,-1),(0,-1),(-1,0),(i,-i),(-i,i),\left(j,j^{2}\right),\left(j^{2},j\right)\right\},\qquad j=e^{\frac {2\pi i}{3}}.$

в этих случаях оно вычислимо за полиномиальное время. Если задача ограничена классом плоских графов, точки гиперболы $H_{2}$ также станут вычислимыми за полиномиальное время. Все остальные точки остаются #P-трудными даже для двудольных планарных графов. В своей статье о дихотомии плоских графов Вертиган утверждает (в своем заключении), что тот же результат справедлив и при дальнейшем ограничении графов со степенью вершины не более трех, за исключением точки $T_{G}(0,-2)$, который считает нигде ненулевые Z _​​3 -потоки и вычислим за полиномиальное время.

Эти результаты содержат несколько примечательных частных случаев. Например, задача вычисления статистической суммы модели Изинга вообще #P-трудна, хотя знаменитые алгоритмы Онзагера и Фишера решают ее для плоских решеток. Кроме того, полином Джонса #P-трудно вычислить. Наконец, вычисление количества четырехраскрасок плоского графа является #P-полным, хотя проблема решения тривиальна согласно теореме о четырех цветах . Напротив, легко увидеть, что подсчет количества трехраскрасок для плоских графов является #P-полным, поскольку известно, что проблема решения является NP-полной посредством экономной редукции .

Приближение

Вопрос, какие точки допускают хороший алгоритм аппроксимации, очень хорошо изучен. Помимо точек, которые можно вычислить точно за полиномиальное время, единственный известный алгоритм аппроксимации $T_{G}(x,y)$ это FPRAS Джеррама и Синклера, которая работает для точек на гиперболе «Изинга» $H_{2}$ для y > 0. Если входные графы ограничены плотными экземплярами со степенью $\Omega (n)$, существует FPRAS, если x ≥ 1, y ≥ 1.

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

См. также

• Полином Боллобаса – Риордана
• Инвариант Тутте – Гротендика - это любая оценка полинома Тутте.

Ссылки

• Алон, Н.; Фриз, А.; Уэлш, DJA (1995), «Схемы аппроксимации, рандомизированные по полиномиальному времени для инвариантов Тутте-Гретендика: плотный случай», Случайные структуры и алгоритмы , 6 (4): 459–478, doi : 10.1002/rsa.3240060409 .
• Аннан, JD (1994), «Алгоритм рандомизированной аппроксимации для подсчета количества лесов в плотных графах», Combinatorics, Probability and Computing , 3 (3): 273–283, doi : 10.1017/S0963548300001188 .
• Биггс, Норман (1993), Алгебраическая теория графов (2-е изд.), Cambridge University Press , ISBN  0-521-45897-8 .
• Бьёрклунд, Андреас; Хусфельдт, Тор; Каски, Петтери; Койвисто, Микко (2008), «Вычисление полинома Тутте за вершинно-экспоненциальное время», Proc. 47-го ежегодного симпозиума IEEE по основам компьютерных наук (FOCS 2008) , стр. 677–686, arXiv : 0711.2585 , doi : 10.1109/FOCS.2008.40 , ISBN  978-0-7695-3436-7 .
• Боллобас, Бела (1998), Современная теория графов , Springer , ISBN  978-0-387-98491-9 .
• Чанг, Фан ; Яу, С.-Т. (1999), «Покрытия, тепловые ядра и остовные деревья» , Электронный журнал комбинаторики , 6 : R12, MR   1667452 .
• Крапо, Генри Х. (1969), «Полином Тутте», Mathematical Equations , 3 (3): 211–229, doi : 10.1007/bf01817442 .
• Фарр, Грэм Э. (2007), «Полиномы Тутта-Уитни: немного истории и обобщений», в Гримметте, Джеффри ; МакДиармид, Колин (ред.), Комбинаторика, сложность и случайность. Дань уважения Доминику Уэлшу , Серия оксфордских лекций по математике и ее приложениям, том. 34, Oxford University Press , стр. 28–52, ISBN.  978-0-19-857127-8 , Збл   1124.05020 .
• Фортуин, Сис М.; Кастелейн, Питер В. (1972), «О модели случайных кластеров: I. Введение и связь с другими моделями», Physica , 57 (4), Elsevier : 536–564, Bibcode : 1972Phy....57.. 536F , номер документа : 10.1016/0031-8914(72)90045-6 , ISSN   0031-8914 .
• Годсил, Крис ; Ройл, Гордон (2004), Алгебраическая теория графов , Springer , ISBN  978-0-387-95220-8 .
• Голдберг, Лесли Энн ; Джеррум, Марк (2008), «Неприближаемость полинома Тутте», Information and Computation , 206 (7): 908–929, arXiv : cs/0605140 , doi : 10.1016/j.ic.2008.04.003 .
• Хаггард, Гэри; Пирс, Дэвид Дж.; Ройл, Гордон (2010), «Вычисление полиномов Тутте», Транзакции ACM в математическом программном обеспечении , 37 (3): Ст. 24, 17, дои : 10.1145/1824801.1824802 , МР   2738228 .
• Джагер, Ф.; Вертиган, ДЛ; Уэлш, DJA (1990), «О вычислительной сложности полиномов Джонса и Тутта», Mathematical Proceedings of the Cambridge Philosophical Society , 108 (1): 35–53, Bibcode : 1990MPCPS.108...35J , doi : 10.1017 /S0305004100068936 .
• Джеррам, Марк ; Синклер, Алистер (1993), «Алгоритмы аппроксимации с полиномиальным временем для модели Изинга» (PDF) , SIAM Journal on Computing , 22 (5): 1087–1116, doi : 10.1137/0222066 .
• Корн, Майкл; Пак, Игорь (2003), Комбинаторные оценки полинома Тутте (PDF) (препринт) .
• Корн, Майкл; Пак, Игорь (2004), «Разбиение прямоугольников с Т-тетромино», Theoretical Computer Science , 319 (1–3): 3–27, doi : 10.1016/j.tcs.2004.02.023 .
• Лас Верньяс, Мишель (1980), «Выпуклость в ориентированных матроидах», Журнал комбинаторной теории , серия B, 29 (2): 231–243, doi : 10.1016/0095-8956(80)90082-9 , ISSN   0095-8956 , МР   0586435 .
• Лас Верньяс, Мишель (1988), «Об оценке в точке (3, 3) полинома Тутте графа», Журнал комбинаторной теории , серия B, 45 (3): 367–372, doi : 10.1016/0095- 8956(88)90079-2 , ISSN   0095-8956 .
• Мартин, Пьер (1977), мультиграфах и инварианты Тутте-Гротендика ( Эйлеровы перечисления в докторская диссертация) (на французском языке), Университет Жозефа Фурье .
• Пирс, Дэвид Дж.; Хаггард, Гэри; Ройл, Гордон (2010), «Эвристика выбора ребер для вычисления полиномов Тутте» (PDF) , Чикагский журнал теоретической информатики : статьи 6, 14, MR   2659710 .
• Секине, Кёко; Имаи, Хироши; Тани, Сейичиро (1995), «Вычисление полинома Тутте для графа среднего размера», Алгоритмы и вычисления (Кэрнс, 1995) , Конспекты лекций по информатике , том. 1004, Springer , стр. 224–233, doi : 10.1007/BFb0015427 , MR   1400247 .
• Сокал, Алан Д. (2005), «Многомерный полином Тутта (псевдоним модели Поттса) для графов и матроидов», в Уэбб, Бриджит С. (ред.), Обзоры по комбинаторике , Серия лекций Лондонского математического общества, том. 327, Cambridge University Press , стр. 173–226, arXiv : math/0503607 , doi : 10.1017/CBO9780511734885.009 .
• Тутт, WT (2001), Теория графов , Издательство Кембриджского университета , ISBN  978-0521794893 .
• Тутте, WT (2004), «Граф-полиномы», « Достижения в области прикладной математики» , 32 (1–2): 5–9, doi : 10.1016/S0196-8858(03)00041-1 .
• Вертиган, ДЛ; Уэлш, DJA (1992), «Вычислительная сложность всей плоскости: двудольный случай», Combinatorics, Probability and Computing , 1 (2): 181–187, doi : 10.1017/S0963548300000195 .
• Вертиган, Дирк (2005), «Вычислительная сложность всех инвариантов для планарных графов», SIAM Journal on Computing , 35 (3): 690–712, doi : 10.1137/S0097539704446797 .
• Валлийский, DJA (1976), Теория матроидов , Academic Press , ISBN  012744050X .
• Уэлш, Доминик (1993), Сложность: узлы, раскраски и счет , Серия лекций Лондонского математического общества, Cambridge University Press , ISBN  978-0521457408 .
• Уэлш, Доминик (1999), «Полином Тутта», Случайные структуры и алгоритмы , 15 (3–4), Уайли : 210–228, doi : 10.1002/(SICI)1098-2418(199910/12)15:3/ 4<210::AID-RSA2>3.0.CO;2-R , ISSN   1042-9832 .
• Валлийский, DJA ; Мерино, К. (2000), «Модель Поттса и полином Тутте», Журнал математической физики , 41 (3): 1127–1152, Бибкод : 2000JMP....41.1127W , doi : 10.1063/1.533181 .
• Уилф, Герберт С. (1986), Алгоритмы и сложность (PDF) , Прентис Холл , ISBN  0-13-021973-8 , МР   0897317 .

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

• «Полином Тутте» , Математическая энциклопедия , EMS Press , 2001 [1994]
• Вайсштейн, Эрик В. «Полином Тутте» . Математический мир .
• PlanetMath Хроматический полином
• Стивен Р. Пагано: Матроиды и знаковые графы
• Сандра Кинган: Теория матроидов . Много ссылок.
• Код для вычисления полиномов Тутте, хроматических и потоковых полиномов Гэри Хаггарда, Дэвида Дж. Пирса и Гордона Ройла: [1]