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

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

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

Определения

Для неориентированного графа ${\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}$ не содержит рёбер.

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

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

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

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

История

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

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

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

В различных точках и прямых плоскости ${\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}$ .

(0,2)

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

(0,−2)

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

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

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

(3,3)

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

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

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

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

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

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

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

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

Модель Поттса	Многочлен Татта
Ферромагнетик	Положительная ветвь ${\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 . Он показал, что если ${\displaystyle G}$ является плоским графом и ${\displaystyle {\vec {G}}_{m}}$ является его ориентированным срединным графом , то

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

Алгоритмы

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

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

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

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

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

Анализ может быть улучшен в величине полиномиального множителя числа ${\displaystyle \tau (G)}$ остовных деревьев входного графа . Для разреженных графов с ${\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}}}}$ .

Например :

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

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

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

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

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

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

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

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

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

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

Input

Граф ${\displaystyle G}$

Output

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

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

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

Input

Граф ${\displaystyle G}$

Output

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

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

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

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

Вычислительная сложность точного вычисления ${\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}}}$ .

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

Эти результаты содержат некоторые важные частные случаи. Например, задача вычисления функции распределения модели Изинга в общем случае #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}$ .

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

См. также

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

Примечания

Литература

• Alon N., Frieze A., Welsh D. J. A. // Random Structures and Algorithms. — 1995. — Т. 6 , вып. 4 . — С. 459–478 . — doi : .
• Annan J. D. A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs // . — 1994. — Т. 3 , вып. 3 . — С. 273–283 . — doi : .
• 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 : .
• Béla Bollobás. Modern Graph Theory. — Springer , 1998. — ISBN 978-0-387-98491-9 .
• Fan Chung, S.-T. Yau. // . — 1999. — Т. 6 . — С. R12 .
• Henry H. Crapo. The Tutte polynomial // Aequationes Mathematicae. — 1969. — Т. 3 , вып. 3 . — С. 211–229 . — doi : .
• 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. — . — Elsevier , 1972. — Т. 57. — С. 536–564. — doi : .
• 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 // . — 2008. — Т. 206 , вып. 7 . — С. 908–929 . — doi : .
• Gary Haggard, David J. Pearce, Gordon Royle. Computing Tutte polynomials // . — 2010. — Т. 37 , вып. 3 . — С. Art. 24, 17 . — doi : .
• F. Jaeger, D. L. Vertigan, D. J. A. Welsh. On the computational complexity of the Jones and Tutte polynomials // . — 1990. — Т. 108 . — С. 35–53 . — doi : .
• Mark Jerrum, Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model // . — 1993. — Т. 22 , вып. 5 . — С. 1087–1116 . — doi : .
• Michael Korn, Igor Pak. . — 2003.
• Michael Korn, Igor Pak. Tilings of rectangles with T-tetrominoes // . — 2004. — Т. 319 , вып. 1–3 . — С. 3–27 . — doi : .
• Michel Las Vergnas. // Journal of Combinatorial Theory . — 1980. — Т. 29 , вып. 2 . — С. 231–243 . — ISSN . — doi : .
• Michel Las Vergnas. // Journal of Combinatorial Theory . — 1988. — Т. 45 , вып. 3 . — С. 367–372 . — ISSN . — doi : .
• Pierre Martin. (фр.) . — , 1977. — (Ph.D. thesis).
• David J. Pearce, Gary Haggard, Gordon Royle. // 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. — ( ). — doi : .
• Alan D. Sokal. Surveys in Combinatorics / Bridget S. Webb. — Cambridge University Press , 2005. — Т. 327. — С. 173–226. — (London Mathematical Society Lecture Note Series). — doi : .
• W. T. Tutte . . — Cambridge University Press , 2001. — ISBN 978-0521794893 .
• W. T. Tutte. Graph-polynomials // . — 2004. — Т. 32 , вып. 1–2 . — С. 5–9 . — doi : .
• D. L. Vertigan, D. J. A. Welsh. // . — 1992. — Т. 1 , вып. 2 . — С. 181–187 . — doi : .
• Dirk Vertigan. // . — 2005. — Т. 35 , вып. 3 . — С. 690–712 . — doi : .
• D. J. A. Welsh. . — 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. . — Random Structures & Algorithms. — Wiley , 1999. — Т. 15. — С. 210–228. — doi : .
• Welsh D. J. A., Merino C. The Potts model and the Tutte polynomial // Journal of Mathematical Physics . — 2000. — Т. 41 , вып. 3 . — doi : .
• Herbert S. Wilf. . — Prentice Hall , 1986. — ISBN 0-13-021973-8 .

Ссылки

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