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

Алгебраическое кодирование связности графа

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

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

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

Полином Тутта имеет несколько эквивалентных определений. Он по существу эквивалентен ранговому полиному Уитни , собственному дихроматическому полиному Тутта и случайной кластерной модели Фортуина–Кастелейна при простых преобразованиях. По существу, это производящая функция для числа наборов ребер заданного размера и связных компонентов с непосредственными обобщениями на матроиды . Это также наиболее общий инвариант графа , который может быть определен с помощью рекуррентного удаления–сокращения . Несколько учебников по теории графов и теории матроидов посвящают ему целые главы. ^{[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}$

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

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

эквивалентно при преобразовании ^[5] ${\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)}$

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

Примеры

Изоморфные графы имеют одинаковый полином Тутте, но обратное неверно. Например, полином Тутте любого дерева на ребрах равен . ${\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}}}$

приведена в следующей таблице.

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

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

История

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

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

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

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

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

Хроматический многочлен, изображенный на плоскости Тутте

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

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

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

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

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

${\displaystyle \chi _{G}(\lambda )=\chi _{G-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)}$подсчитывает количество остовных лесов (подмножества ребер без циклов и с тем же количеством связных компонентов, что и у G ). Если граф связный, подсчитывает количество остовных деревьев. ${\displaystyle T_{G}(1,1)}$

(1,2)

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

(2,0)

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

(0,2)

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

(2,2)

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

(0,−2)

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

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

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

(3,3)

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

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

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

Функции распределения для модели Изинга и моделей Поттса с 3 и 4 состояниями, изображенные на плоскости Тутте.

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

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

полином Тутте специализируется на функции распределения модели Изинга , изучаемой в статистической физике . В частности, вдоль гиперболы они связаны уравнением: ^[15] ${\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}$

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

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

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

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

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

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

В , полином Тутта специализируется на потоке полинома, изучаемого в комбинаторике. Для связного и неориентированного графа G и целого числа k , нигде не нулевой k -поток - это присвоение значений "потока" ребрам произвольной ориентации G таким образом, что полный поток, входящий и выходящий из каждой вершины, конгруэнтен по модулю k . Полином потока обозначает количество нигде не нулевых k -потоков. Это значение тесно связано с хроматическим полиномом, фактически, если G - планарный граф , хроматический полином G эквивалентен потоку полинома его двойственного графа в том смысле, что ${\displaystyle x=0}$ ${\displaystyle 1,2,\dots ,k-1}$ ${\displaystyle C_{G}(k)}$ ${\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).}$

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

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

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

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

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

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

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

где - число связных компонент остовного подграфа ( V , A ). Это связано с полиномом коранг-нуля следующим образом: ${\displaystyle k(A)}$

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

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

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

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

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

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

Алгоритмы

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

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

Повторение делеции-контракции для полинома Тутте,

${\displaystyle 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 , которое не является петлей или мостом , рекурсивно вычислить полином Тутте для случая, когда это ребро удалено, и когда это ребро сжато . Затем сложите два подрезультата вместе, чтобы получить общий полином Тутте для графа.

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

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

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

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

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

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

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

поэтому алгоритм удаления-сжатия работает в пределах полиномиального множителя этой границы. Например: ^[20]

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

На практике тестирование изоморфизма графа используется для избежания некоторых рекурсивных вызовов. Этот подход хорошо работает для графов, которые довольно разрежены и демонстрируют много симметрий; производительность алгоритма зависит от эвристики, используемой для выбора ребра e . ^{[19] [21] [22]}

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

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

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

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

Марковская цепь Монте-Карло

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

Сложность вычислений

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

Входные данные: График ${\displaystyle G}$

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

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

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

Входные данные: График ${\displaystyle G}$

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

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

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

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

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

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

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

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

Приближение

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

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

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

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

Примечания

1. Боллобаш 1998, глава 10.
2. Биггс 1993, глава 13.
3. Годсил и Ройл 2004, глава 15.
4. Сокаль 2005.
5. Сокаль 2005, уравнение (2.26).
6. Tutte 2004.
7. Валлийский.
8. Farr 2007.
9. Фортуин и Кастелейн 1972.
10. Welsh 1999.
11. Лас-Верньяс 1980.
12. Корн и Пак 2004.
13. См. Korn & Pak 2003 для комбинаторных интерпретаций многих других положений.
14. Лас-Верньяс 1988.
15. Уэлш 1993, стр. 62.
16. Уэльский и мериносовый 2000.
17. Мартин 1977.
18. Вильф 1986, стр. 46.
19. Секин, Имаи и Тани 1995.
20. Chung & Yau 1999, по данным Björklund et al. 2008.
21. Хаггард, Пирс и Ройл 2010.
22. Пирс, Хаггард и Ройл 2010.
23. Джеррум и Синклер 1993.
24. Goldberg & Jerrum 2008.
25. Йегер, Вертиган и Уэлш 1990.
26. Вертиган и Уэлш 1992.
27. Вертиган 2005.
28. Для случая x ≥ 1 и y = 1 см. Annan 1994. Для случая x ≥ 1 и y > 1 см. Alon, Frieze & Welsh 1995.

Ссылки

• Алон, Н.; Фриз, А.; Уэлш, Д. Дж. А. (1995), «Схемы рандомизированной аппроксимации с полиномиальным временем для инвариантов Тутте-Грётендика: плотный случай», Случайные структуры и алгоритмы , 6 (4): 459–478, doi :10.1002/rsa.3240060409.
• Аннан, Дж. Д. (1994), «Алгоритм рандомизированного приближения для подсчета количества лесов в плотных графах», Комбинаторика, вероятность и вычисления , 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, doi :10.37236/1444, MR  1667452.
• Крапо, Генри Х. (1969), «Полином Тутте», Aequationes Mathematicae , 3 (3): 211–229, doi : 10.1007/bf01817442.
• Farr, Graham E. (2007), "Полиномы Тутта-Уитни: некоторая история и обобщения", в Grimmett, Geoffrey ; McDiarmid, Colin (ред.), Combinatorics, difficulty, and chance. Посвящение Доминику Уэлшу , Oxford Lecture Series in Mathematics and its Applications, т. 34, Oxford University Press , стр. 28–52, ISBN 978-0-19-857127-8, ЗБЛ  1124.05020.
• Fortuin, Cees M.; Kasteleyn, Pieter W. (1972), «О модели случайных кластеров: I. Введение и связь с другими моделями», Physica , 57 (4), Elsevier : 536–564, Bibcode : 1972Phy....57..536F, doi : 10.1016/0031-8914(72)90045-6, ISSN  0031-8914.
• Годсил, Крис ; Ройл, Гордон (2004), Алгебраическая теория графов , Springer , ISBN 978-0-387-95220-8.
• Голдберг, Лесли Энн ; Джеррум, Марк (2008), «Неприближенность полинома Тутте», Информация и вычисления , 206 (7): 908–929, arXiv : cs/0605140 , doi : 10.1016/j.ic.2008.04.003.
• Хаггард, Гэри; Пирс, Дэвид Дж.; Ройл, Гордон (2010), «Вычисление полиномов Тутта», ACM Transactions on Mathematical Software , 37 (3): Статья 24, 17, doi :10.1145/1824801.1824802, MR  2738228.
• Jaeger, F.; Vertigan, DL; Welsh, DJA (1990), "О вычислительной сложности полиномов Джонса и Тутта", Математические труды Кембриджского философского общества , 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), «Замощения прямоугольников T-тетромино», Теоретическая информатика , 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, MR  0586435.
• Лас Верньяс, Мишель (1988), «О вычислении в точке (3, 3) полинома Тутте графа», Журнал комбинаторной теории , Серия B, 45 (3): 367–372, doi : 10.1016/0095-8956(88)90079-2 , ISSN  0095-8956.
• Мартин, Пьер (1977), Enumérations Eulériennes dans les multigraphes et invariants de Tutte-Grothendieck [ Эйлеровы перечисления в мультиграфах и инвариантах Тутте-Гротендика ] (докторская диссертация) (на французском языке), Университет Жозефа Фурье.
• Пирс, Дэвид Дж.; Хаггард, Гэри; Ройл, Гордон (2010), «Эвристика выбора ребер для вычисления полиномов Тутте» (PDF) , Чикагский журнал теоретической компьютерной науки : статья 6, 14, MR  2659710.
• Секинэ, Кёко; Имаи, Хироши; Тани, Сейитиро (1995), «Вычисление полинома Тутте для графа умеренного размера», Алгоритмы и вычисления (Кэрнс, 1995) , Lecture Notes in Computer Science , т. 1004, Springer , стр. 224–233, doi :10.1007/BFb0015427, ISBN 978-3-540-60573-7, МР  1400247.
• Sokal, Alan D. (2005), «Многомерный полином Тутта (он же модель Поттса) для графов и матроидов», в Webb, Bridget S. (ред.), Surveys in Combinatorics , London Mathematical Society Lecture Note Series, т. 327, Cambridge University Press , стр. 173–226, arXiv : math/0503607 , doi :10.1017/CBO9780511734885.009, ISBN 978-0-521-61523-5.
• Тутте, У. Т. (2001), Теория графов , Cambridge University Press , ISBN 978-0521794893.
• Тутте, В. Т. (2004), «Граф-полиномы», Успехи в прикладной математике , 32 (1–2): 5–9, doi : 10.1016/S0196-8858(03)00041-1.
• Vertigan, DL; Welsh, DJA (1992), «Вычислительная сложность плоскости Тутте: двудольный случай», Комбинаторика, вероятность и вычисления , 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), Сложность: узлы, раскраски и подсчет , Серия лекций Лондонского математического общества, Издательство Кембриджского университета , ISBN 978-0521457408.
• Уэлш, Доминик (1999), «Многочлен Тутта», Случайные структуры и алгоритмы , 15 (3–4), Wiley : 210–228, doi :10.1002/(SICI)1098-2418(199910/12)15:3/4<210::AID-RSA2>3.0.CO;2-R, ISSN  1042-9832.
• Welsh, DJA ; Merino, C. (2000), «Модель Поттса и полином Тутта», Журнал математической физики , 41 (3): 1127–1152, Bibcode : 2000JMP....41.1127W, doi : 10.1063/1.533181.
• Уилф, Герберт С. (1986), Алгоритмы и сложность (PDF) , Prentice Hall , ISBN 0-13-021973-8, МР  0897317.

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

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