Многочлен Татта

Многочлен Татта (многочлен Татта — Уитни) — многочлен от двух переменных, играющий большую роль в теории графов; определён для любого неориентированного графа и содержит информацию, насколько граф связен. Стандартное обозначение — ${\displaystyle T_{G}}$.

Многочлен ${\displaystyle x^{4}+x^{3}+x^{2}y}$ является многочленом Татта графа «голова быка». Красная линия показывает пересечение с плоскостью ${\displaystyle y=0}$ и эквивалентна хроматическому многочлену.

Первоначально изучался в алгебраической теории графов как конструкция для обобщения задач подсчёта, связанных с раскраской графов и нигде не нулевыми потоками, впоследствии обнаружена связь с многочленом Джонса из теории узлов и статистическими суммами модели Поттса^[англ.] из статистической физики. Многочлен является источником некоторых вычислительных задач^[англ.] теоретической информатики.

Многочлен имеет несколько эквивалентных определений: он эквивалентен многочлену ранга Уитни➤, дихроматическому многочлену Татта➤ и модели случайных кластеров Фортюэна — Кастелейна (после небольшого преобразования)➤. Многочлен, по существу, является производящей функцией для числа рёбер множеств заданного размера и связных компонент и имеет прямое обобщение в теории матроидов. Многочлен является также для графов инвариантом наиболее общего вида, который может быть определён рекурсией удаления — стягивания➤. Некоторые книги по теории графов и матроидам посвящают целые главы этому понятию^[1][2][3].

Определения

Для неориентированного графа ${\displaystyle G=(V,E)}$ многочлен Татта определяется как:

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

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

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

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

Две функции эквивалентны, что показывается простой заменой переменных:

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

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

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

Оригинальное определение Татта ${\displaystyle T_{G}}$ для связного графа ${\displaystyle G}$ эквивалентно (но это эквивалентность показывается технически сложнее):

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

где ${\displaystyle t_{ij}}$ означает число остовных деревьев «внутренней активности ${\displaystyle i}$ и внешней активности ${\displaystyle j}$».

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

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

если ${\displaystyle e}$ не является ни петлёй, ни мостом, с базовым случаем:

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

если ${\displaystyle G}$ содержит ${\displaystyle i}$ мостов и ${\displaystyle j}$ петель и никаких других рёбер. В частности ${\displaystyle T_{G}=1}$, если ${\displaystyle G}$ не содержит рёбер.

Модель случайных кластеров Фортюэна — Кастелейна^[4] даёт другое эквивалентное определение^[5]:

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

эквивалентен ${\displaystyle T_{G}}$ при преобразовании^[6]:

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

Свойства

Многочлен Татта разлагается на связные компоненты — если ${\displaystyle G}$ является объединением непересекающихся графов ${\displaystyle H}$ и ${\displaystyle H'}$, то:

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

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

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

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

Примеры

Изоморфные графы имеют те же самые многочлены Татта, но обратное не верно. Например, многочлен Татта любого дерева с ${\displaystyle m}$ рёбрами равен ${\displaystyle x^{m}}$.

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

${\displaystyle {\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

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

${\displaystyle {\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}}}$

История

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

Независимо, при работе с алгебраической теорией графов, Поттс начал изучать статистические суммы некоторых моделей статистической механики в 1952. В работе 1972 года о модели случайных кластеров, обобщения модели Поттса^[англ.], Фортюэн и Кастелейн^[4] дали объединённое выражение, которое показало связь этой модели с многочленом Татта^[10].

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

В различных точках и прямых плоскости ${\displaystyle (x,y)}$ многочлен Татта даёт значения, которые изучаются сами по себе в различных областях математики и физики. Частично привлекательность многочлена Татта вызвана объединением метода анализа этих величин.

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

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

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

При ${\displaystyle y=0}$ многочлен Татта превращается в хроматический многочлен,

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

где ${\displaystyle k(G)}$ обозначает число связных компонент графа ${\displaystyle G}$.

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

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

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

Эти три условия позволяют нам вычислить ${\displaystyle \chi _{G}(\lambda )}$ путём последовательности удалений и стягиваний. Однако эти операции не дают гарантии, что различная последовательность операций приведёт к тому же результату. Единственность гарантируется фактом, что ${\displaystyle \chi _{G}(\lambda )}$ подсчитывает вещи, независимые от рекурсии. В частности,

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

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

Многочлен Джонса

Основная статья: Многочлен Джонса

Множество аргументов, при которых многочлен Татта сводится к многочлену Джонса

Вдоль гиперболы ${\displaystyle xy=1}$ многочлен Татта планарного графа сводится к многочлену Джонса связанного альтернированного узла.

Индивидуальные точки

(2,1)

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

(1,1)

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

(1,2)

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

(2,0)

${\displaystyle T_{G}(2,0)}$ подсчитывает число ациклических ориентаций графа ${\displaystyle G}$^[11].

(0,2)

${\displaystyle T_{G}(0,2)}$ подсчитывает число строго связные ориентаций графа ${\displaystyle G}$ ^[12].

(0,−2)

Если граф ${\displaystyle G}$ является 4-регулярным графом, то

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

подсчитывает число ациклических ориентаций графа ${\displaystyle G}$. Здесь ${\displaystyle k(G)}$ — число связных компонент графа ${\displaystyle G}$^[11].

(3,3)

Если граф ${\displaystyle G}$ является ${\displaystyle m\times n}$-решёткой, то ${\displaystyle 2T_{G}(3,3)}$ подсчитывает число путей замощения прямоугольника с шириной ${\displaystyle 4m}$ и высотой ${\displaystyle 4n}$ плитками T-тетрамино^[13][14]

Если граф ${\displaystyle G}$ является планарным, то ${\displaystyle 2T_{G}(3,3)}$ равен сумме взвешенных эйлеровых ориентаций в срединном графе графа ${\displaystyle G}$, где вес равен от 2 до числа седловых вершин ориентации (то есть число вершин с рёбрами в циклическом порядке «in, out, in out»)^[15].

Модели Поттса и Изинга

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

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

Для гиперболы на плоскости ${\displaystyle xy}$:

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

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

${\displaystyle 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)}$.

В частности:

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

для всех комплексных ${\displaystyle \alpha }$.

Более общо, если для любого положительного ${\displaystyle q}$ определить гиперболу:

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

то многочлен Татта сводится к статистической сумме модели Поттса^[англ.] с ${\displaystyle q}$ состояниями. Различные физические величины, анализируемые с помощью модели Поттса, переходят в конкретные части ${\displaystyle H_{q}}$.

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

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

Потоковый многочлен

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

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

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

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

Связь с многочленом Татта даётся равенством:

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

Многочлен живучести

Основная статья: Связный граф

Многочлен живучести, нарисованный на плоскости Татта

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

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

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

Татт определил также близкое обобщение от 2 переменных хроматического многочлена, дихроматический многочлен графа:

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

где ${\displaystyle k(A)}$ — число связных компонент остовного подграфа ${\displaystyle (V,A)}$. Он связан с ранговым многочленом Уитни равенством:

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

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

Связанные многочлены

Многочлен Мартина

Основная статья: Многочлен Мартина

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

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

Алгоритмы

Формула удаления — стягивания

Алгоритм удаления — стягивания, применённый к алмазу. Красные рёбра удалены в левом потомке и стянуты в правом. Результирующий многочлен является суммой одночленов листьев, ${\displaystyle x^{3}+2x^{2}+y^{2}+2xy+x+y}$^[17].

Применение формулы удаления — стягивания для многочлена Татта:

${\displaystyle T_{G}(x,y)=T_{G\setminus e}(x,y)+T_{G/e}(x,y)}$,

где ${\displaystyle e}$ не является ни петлёй, ни мостом, даёт рекурсивный алгоритм вычисления многочлена — выбирается любое подходящее ребро ${\displaystyle e}$ и применяется формула, пока не останутся только петли и мосты. Получившиеся в результате выполнения одночлены легко вычислить.

С точностью до полиномиального множителя время выполнения ${\displaystyle t}$ этого алгоритма можно выразить в терминах числа вершин ${\displaystyle n}$ и числа рёбер ${\displaystyle m}$ графа:

${\displaystyle t(n+m)=t(n+m-1)+t(n+m-2)}$,

рекуррентное отношение, которое определяет числа Фибоначчи с решением^[19].

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

Анализ может быть улучшен в величине полиномиального множителя числа ${\displaystyle \tau (G)}$ остовных деревьев входного графа^[20]. Для разреженных графов с ${\displaystyle m=O(n)}$ время работы алгоритма равно ${\displaystyle O(\exp(n))}$. Для регулярных графов степени ${\displaystyle k}$ число остовных деревьев можно ограничить величиной

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

где

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

Например^[21][22]:

${\displaystyle \nu _{5}\approx 4{,}4066}$.

На практике во избежание некоторых рекурсивных вызовов используется проверка на изоморфизм. Этот подход работает хорошо для сильно разреженных графов и графов с множеством симметрий, при этом скорость работы алгоритма зависит от метода выбора ребра ${\displaystyle e}$^[20][23][24].

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

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

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

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

Метод Монте-Карло для цепей Маркова

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

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

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

Input

Граф ${\displaystyle G}$

Output

Коэффициенты ${\displaystyle T_{G}}$

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

Много больше внимания было уделено семейству задач, называемых Tutte${\displaystyle (x,y)}$, определённых для любой комплексной пары ${\displaystyle (x,y)}$:

Input

Граф ${\displaystyle G}$

Output

Значение ${\displaystyle T_{G}(x,y)}$

Трудность этой задачи меняется в зависимости от координат ${\displaystyle (x,y)}$.

Точное вычисление

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

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

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

${\displaystyle \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}}}$.

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

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

Аппроксимация

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

Хотя в случае аппроксимации ситуация не так хорошо изучена, как для точных вычислений, известно, что большие области плоскости трудно аппроксимировать^[26].

См. также

• Многочлен Боллобаша — Риордана

Примечания

1. Bollobás, 1998, с. chapter 10.
2. Biggs, 1993, с. chapter 13.
3. Godsil, Royle, 2004, chap. 15.
4. Fortuin, Kasteleyn, 1972.
5. Sokal, 2005.
6. Sokal, 2005, с. eq. (2.26).
7. Совершенный прямоугольник — это прямоугольник, который можно разбить на квадраты и все квадраты имеют различные размеры
8. Tutte, 2004.
9. Welsh.
10. Farr, 2007.
11. Welsh, 1999.
12. Las Vergnas, 1980.
13. Korn, Pak, 2004.
14. См. статью Корна и Пака (Korn, Pak 2003) о комбинаторной интерпретации многих других точек.
15. Las Vergnas, 1988.
16. Welsh, 1993, с. 62.
17. Welsh, Merino, 2000.
18. Martin, 1977.
19. Wilf, 1986, с. 46.
20. Sekine, Imai, Tani, 1995.
21. Chung, Yau, 1999.
22. Björklund, Husfeldt, Kaski, Koivisto, 2008.
23. Haggard, Pearce, Royle, 2010.
24. Pearce, Haggard, Royle, 2010.
25. Jerrum, Sinclair, 1993.
26. Goldberg, Jerrum, 2008.
27. Jaeger, Vertigan, Welsh, 1990.
28. Vertigan, Welsh, 1992.
29. Vertigan, 2005.
30. Для случая ${\displaystyle x}$ ≥ 1 и ${\displaystyle y}$ = 1 см. Аннана (Annan 1994). Для случая ${\displaystyle x}$ ≥ 1 и ${\displaystyle y}$ > 1, см. стать. Алона, Фриза и Уэлша (Alon, Frieze, Welsh 1995).

Литература

• Alon N., Frieze A., Welsh D. J. A. Polynomial time randomized approximation schemes for Tutte-Gröthendieck invariants: The dense case // Random Structures and Algorithms. — 1995. — Т. 6, вып. 4. — С. 459–478. — doi:10.1002/rsa.3240060409.
• Annan J. D. A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs // Combinatorics, Probability and Computing. — 1994. — Т. 3, вып. 3. — С. 273–283. — doi:10.1017/S0963548300001188.
• Norman Biggs. Algebraic Graph Theory. — 2nd. — Cambridge University Press, 1993. — ISBN 0-521-45897-8.
• Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto. Proc. of the 47th annual IEEE Symposium on Foundations of Computer Science (FOCS 2008). — 2008. — С. 677–686. — ISBN 978-0-7695-3436-7. — doi:10.1109/FOCS.2008.40.
• Béla Bollobás. Modern Graph Theory. — Springer, 1998. — ISBN 978-0-387-98491-9.
• Fan Chung, S.-T. Yau. Coverings, heat kernels and spanning trees // Electronic Journal of Combinatorics. — 1999. — Т. 6. — С. R12.
• Henry H. Crapo. The Tutte polynomial // Aequationes Mathematicae. — 1969. — Т. 3, вып. 3. — С. 211–229. — doi:10.1007/bf01817442.
• Graham E. Farr. Combinatorics, complexity, and chance. A tribute to Dominic Welsh / Geoffrey Grimmett, Colin McDiarmid. — Oxford University Press, 2007. — Т. 34. — С. 28–52. — (Oxford Lecture Series in Mathematics and its Applications). — ISBN 0-19-857127-5.
• Cees M. Fortuin, Pieter W. Kasteleyn. On the random-cluster model: I. Introduction and relation to other models. — Physica. — Elsevier, 1972. — Т. 57. — С. 536–564. — doi:10.1016/0031-8914(72)90045-6.
• Chris Godsil, Gordon Royle. Algebraic Graph Theory. — Springer, 2004. — ISBN 978-0-387-95220-8.
• Leslie Ann Goldberg, Mark Jerrum. Inapproximability of the Tutte polynomial // Information and Computation. — 2008. — Т. 206, вып. 7. — С. 908–929. — doi:10.1016/j.ic.2008.04.003.
• Gary Haggard, David J. Pearce, Gordon Royle. Computing Tutte polynomials // ACM Transactions on Mathematical Software. — 2010. — Т. 37, вып. 3. — С. Art. 24, 17. — doi:10.1145/1824801.1824802.
• F. Jaeger, D. L. Vertigan, D. J. A. Welsh. On the computational complexity of the Jones and Tutte polynomials // Mathematical Proceedings of the Cambridge Philosophical Society. — 1990. — Т. 108. — С. 35–53. — doi:10.1017/S0305004100068936.
• Mark Jerrum, Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model // SIAM Journal on Computing. — 1993. — Т. 22, вып. 5. — С. 1087–1116. — doi:10.1137/0222066.
• Michael Korn, Igor Pak. Combinatorial evaluations of the Tutte polynomial. — 2003.
• Michael Korn, Igor Pak. Tilings of rectangles with T-tetrominoes // Theoretical Computer Science. — 2004. — Т. 319, вып. 1–3. — С. 3–27. — doi:10.1016/j.tcs.2004.02.023.
• Michel Las Vergnas. Convexity in oriented matroids // Journal of Combinatorial Theory. — 1980. — Т. 29, вып. 2. — С. 231–243. — ISSN 0095-8956. — doi:10.1016/0095-8956(80)90082-9.
• Michel Las Vergnas. On the evaluation at (3, 3) of the Tutte polynomial of a graph // Journal of Combinatorial Theory. — 1988. — Т. 45, вып. 3. — С. 367–372. — ISSN 0095-8956. — doi:10.1016/0095-8956(88)90079-2.
• Pierre Martin. Enumérations Eulériennes dans les multigraphes et invariants de Tutte-Grothendieck (фр.). — Joseph Fourier University, 1977. — (Ph.D. thesis).
• David J. Pearce, Gary Haggard, Gordon Royle. Edge-selection heuristics for computing Tutte polynomials // Chicago Journal of Theoretical Computer Science. — 2010. — С. Article 6, 14.
• Kyoko Sekine, Hiroshi Imai, Seiichiro Tani. Algorithms and computations (Cairns, 1995). — Springer, 1995. — Т. 1004. — С. 224–233. — (Lecture Notes in Computer Science). — doi:10.1007/BFb0015427.
• Alan D. Sokal. Surveys in Combinatorics / Bridget S. Webb. — Cambridge University Press, 2005. — Т. 327. — С. 173–226. — (London Mathematical Society Lecture Note Series). — doi:10.1017/CBO9780511734885.009.
• W. T. Tutte. Graph Theory. — Cambridge University Press, 2001. — ISBN 978-0521794893.
• W. T. Tutte. Graph-polynomials // Advances in Applied Mathematics. — 2004. — Т. 32, вып. 1–2. — С. 5–9. — doi:10.1016/S0196-8858(03)00041-1.
• D. L. Vertigan, D. J. A. Welsh. The Computational Complexity of the Tutte Plane: the Bipartite Case // Combinatorics, Probability and Computing. — 1992. — Т. 1, вып. 2. — С. 181–187. — doi:10.1017/S0963548300000195.
• Dirk Vertigan. The Computational Complexity of Tutte Invariants for Planar Graphs // SIAM Journal on Computing. — 2005. — Т. 35, вып. 3. — С. 690–712. — doi:10.1137/S0097539704446797.
• D. J. A. Welsh. Matroid Theory. — Academic Press, 1976. — ISBN 012744050X.
• Dominic Welsh. Complexity: Knots, Colourings and Counting. — Cambridge University Press, 1993. — (London Mathematical Society Lecture Note Series). — ISBN 978-0521457408.
• Dominic Welsh. The Tutte polynomial. — Random Structures & Algorithms. — Wiley, 1999. — Т. 15. — С. 210–228. — doi:10.1002/(SICI)1098-2418(199910/12)15:3/4<210::AID-RSA2>3.0.CO;2-R.
• Welsh D. J. A., Merino C. The Potts model and the Tutte polynomial // Journal of Mathematical Physics. — 2000. — Т. 41, вып. 3. — doi:10.1063/1.533181.
• Herbert S. Wilf. Algorithms and complexity. — Prentice Hall, 1986. — ISBN 0-13-021973-8.

Ссылки

• Hazewinkel, Michiel, ed. (2001), "Tutte polynomial", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
• Weisstein, Eric W. Tutte polynomial (англ.) на сайте Wolfram MathWorld.
• PlanetMath Chromatic polynomial
• Steven R. Pagano: Matroids and Signed Graphs
• Sandra Kingan: Matroid theory. Lots of links.
• Code for computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle:  (недоступная ссылка)