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

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

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

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

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

ОпределенияПравить

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

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

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

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

$R_G(u,v)={\sum <!--\; \sum \; -->}_{A\subseteq <!--\; \subseteq \; -->E}{u}^{r(E)-<!--\; -\; -->r(A)}{v}^{|A|-<!--\; -\; -->r(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).$$T_{G}(x,y)=R_{G}(x-1,y-1).$ 

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

$T_G(x,y)=(x-<!--\; -\; -->1{)}^{-<!--\; -\; -->k(G)}{Q}_G(x-<!--\; -\; -->1,y-<!--\; -\; -->1)$$T_{G}(x,y)=(x-1)^{-k(G)}Q_{G}(x-1,y-1)$ .

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

$T_G(x,y)={\sum <!--\; \sum \; -->}_{i,j}{t}_{ij}{x}^i{y}^j,$$T_{G}(x,y)=\sum \nolimits _{i,j}t_{ij}x^{i}y^{j},$ 

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

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

$T_G=T_{G-<!--\; -\; -->e}+T_{G/e}$$T_{G}=T_{G-e}+T_{G/e}$ ,

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

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

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

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

$Z_G(q,w)={\sum <!--\; \sum \; -->}_{F\subseteq <!--\; \subseteq \; -->E}{q}^{k(F)}{w}^{|F|}$$Z_{G}(q,w)=\sum \nolimits _{F\subseteq E}q^{k(F)}w^{|F|}$ 

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

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

СвойстваПравить

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

$T_G=T_H\cdot <!--\; \cdot \; -->T_{H^{\prime }}$$T_{G}=T_{H}\cdot T_{H'}$ .

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

$T_G(x,y)=T_{G^{\ast <!--\; \ast \; -->}}(y,x)$$T_{G}(x,y)=T_{G^{*}}(y,x)$ 

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

ПримерыПравить

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

Многочлены Татта часто публикуются в виде таблицы коэффициентов $t_{ij}$$t_{ij}$  членов $x^i{y}^j$$x^{i}y^{j}$  в строке $i$$i$  и столбце $j$$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. В работе 1972 года о модели случайных кластеров, обобщения модели Поттса^[en], Фортюэн и Кастелейн дали объединённое выражение, которое показало связь этой модели с многочленом Татта.

СпециализацииПравить

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

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

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

 

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

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

${\mathrm{\chi <!--\; \chi \; -->}}_G(\mathrm{\lambda <!--\; \lambda \; -->})=(-<!--\; -\; -->1{)}^{|V|-<!--\; -\; -->k(G)}{\mathrm{\lambda <!--\; \lambda \; -->}}^{k(G)}{T}_G(1-<!--\; -\; -->\mathrm{\lambda <!--\; \lambda \; -->},0),$$\chi _{G}(\lambda )=(-1)^{|V|-k(G)}\lambda ^{k(G)}T_{G}(1-\lambda ,0),$ 

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

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

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

${\mathrm{\chi <!--\; \chi \; -->}}_G(\mathrm{\lambda <!--\; \lambda \; -->})={\mathrm{\chi <!--\; \chi \; -->}}_{G\setminus <!--\; \setminus \; -->e}(\mathrm{\lambda <!--\; \lambda \; -->})-<!--\; -\; -->{\mathrm{\chi <!--\; \chi \; -->}}_{G/e}(\mathrm{\lambda <!--\; \lambda \; -->}).$$\chi _{G}(\lambda )=\chi _{G\setminus e}(\lambda )-\chi _{G/e}(\lambda ).$ 

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

$T_G(2,0)=(-<!--\; -\; -->1{)}^{|V|}{\mathrm{\chi <!--\; \chi \; -->}}_G(-<!--\; -\; -->1)$$T_{G}(2,0)=(-1)^{|V|}\chi _{G}(-1)$ 

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

Многочлен ДжонсаПравить

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

 

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

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

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

(2,1)Править

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

(1,1)Править

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

(1,2)Править

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

(2,0)Править

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

(0,2)Править

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

(0,−2)Править

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

$(-<!--\; -\; -->1{)}^{|V|+k(G)}{T}_G(0,-<!--\; -\; -->2)$$(-1)^{|V|+k(G)}T_{G}(0,-2)$ 

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

(3,3)Править

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

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

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

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

 

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

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

$H_2:(x-<!--\; -\; -->1)(y-<!--\; -\; -->1)=2$$H_{2}:\quad (x-1)(y-1)=2$ 

многочлен Татта сводится к статистической сумме $Z(\cdot <!--\; \cdot \; -->)$$Z(\cdot )$  модели Изинга, изучаемой в статистической физике. В частности, вдоль гиперболы $H_2$$H_2$  двойка связана с уравнением:

$Z(G)=2{\left(e^{-<!--\; -\; -->\mathrm{\alpha <!--\; \alpha \; -->}}\right)}^{|E|-<!--\; -\; -->r(E)}{\left(4\sinh <!--\; \; -->\mathrm{\alpha <!--\; \alpha \; -->}\right)}^{r(E)}{T}_G\left(\coth <!--\; \; -->\mathrm{\alpha <!--\; \alpha \; -->},e^{2\mathrm{\alpha <!--\; \alpha \; -->}}\right)$$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 <!--\; \; -->\mathrm{\alpha <!--\; \alpha \; -->}-<!--\; -\; -->1)\left(e^{2\mathrm{\alpha <!--\; \alpha \; -->}}-<!--\; -\; -->1\right)=2$$(\coth \alpha -1)\left(e^{2\alpha }-1\right)=2$ 

для всех комплексных $\mathrm{\alpha <!--\; \alpha \; -->}$$\alpha$ .

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

$H_q:(x-<!--\; -\; -->1)(y-<!--\; -\; -->1)=q$$H_{q}:\quad (x-1)(y-1)=q$ ,

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

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

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

Потоковый многочленПравить

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

 

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

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

$C_G(k)=k^{-<!--\; -\; -->1}{\mathrm{\chi <!--\; \chi \; -->}}_{G^{\ast <!--\; \ast \; -->}}(k)$$C_{G}(k)=k^{-1}\chi _{G^{*}}(k)$ .

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

$C_G(k)=(-<!--\; -\; -->1{)}^{|E|+|V|+k(G)}{T}_G(0,1-<!--\; -\; -->k)$$C_{G}(k)=(-1)^{|E|+|V|+k(G)}T_{G}(0,1-k)$ .

Многочлен живучестиПравить

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

 

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

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

$R_G(p)=(1-<!--\; -\; -->p{)}^{|V|-<!--\; -\; -->k(G)}{p}^{|E|-<!--\; -\; -->|V|+k(G)}{T}_G\left(1,\frac{1}{p}\right)$$R_{G}(p)=(1-p)^{|V|-k(G)}p^{|E|-|V|+k(G)}T_{G}\left(1,{\tfrac {1}{p}}\right)$ .

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

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

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

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

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

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

Связанные многочленыПравить

Многочлен МартинаПравить

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

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

$T_G(x,x)=m_{{\stackrel{\to <!--\; \to \; -->}{G}}_m}(x).$$T_{G}(x,x)=m_{{\vec {G}}_{m}}(x).$ 

АлгоритмыПравить

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

 

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

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

$T_G(x,y)=T_{G\setminus <!--\; \setminus \; -->e}(x,y)+T_{G/e}(x,y)$$T_{G}(x,y)=T_{G\setminus e}(x,y)+T_{G/e}(x,y)$ ,

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

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

$t(n+m)=t(n+m-<!--\; -\; -->1)+t(n+m-<!--\; -\; -->2)$$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).$$t(n+m)=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O\left(1,6180^{n+m}\right).$ 

Анализ может быть улучшен в величине полиномиального множителя числа $\mathrm{\tau <!--\; \tau \; -->}(G)$$\tau (G)$  остовных деревьев входного графа. Для разреженных графов с $m=O(n)$$m=O(n)$  время работы алгоритма равно $O(\exp <!--\; \; -->(n))$$O(\exp(n))$ . Для регулярных графов степени $k$$k$  число остовных деревьев можно ограничить величиной

$\mathrm{\tau <!--\; \tau \; -->}(G)=O\left({\mathrm{\nu <!--\; \nu \; -->}}_k^n{n}^{-<!--\; -\; -->1}\log <!--\; \; -->n\right)$$\tau (G)=O\left(\nu _{k}^{n}n^{-1}\log n\right)$ ,

где

${\mathrm{\nu <!--\; \nu \; -->}}_k=\frac{(k-<!--\; -\; -->1{)}^{k-<!--\; -\; -->1}}{(k^2-<!--\; -\; -->2k{)}^{\frac{k}{2}-<!--\; -\; -->1}}$$\nu _{k}={\frac {(k-1)^{k-1}}{(k^{2}-2k)^{{\frac {k}{2}}-1}}}$ .

Например:

${\mathrm{\nu <!--\; \nu \; -->}}_5\approx <!--\; \approx \; -->\mathrm{4,406}6$$\nu _{5}\approx 4{,}4066$ .

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

Исключение ГауссаПравить

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

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

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

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

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

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

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

Input

Граф $G$$G$ 

Output

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

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

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

Input

Граф $G$$G$ 

Output

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

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

Точное вычислениеПравить

 

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

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

Вычислительная сложность точного вычисления $T_G(x,y)$$T_{G}(x,y)$  распадается на два класса для $x,y\in <!--\; \in \; -->\mathbb{C}$$x,y\in \mathbb {C}$ . Задача #P-трудна, если только $(x,y)$$(x,y)$  не лежит на гиперболе $H_1$$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\},j=e^{\frac{2\mathrm{\pi <!--\; \pi \; -->}i}{3}}$$\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$$H_2$  задача становится вычисляемой за полиномиальное время. Все другие точки остаются #P-трудными даже для двудольных планарных графов. В своей статье по дихотомии планарных графов Вертиган утверждает, что тот же результат верен, если наложить дополнительные ограничения на графы (степень вершины не превосходит трёх), за исключением точки $T_G(0,-<!--\; -\; -->2)$$T_{G}(0,-2)$ , которая подсчитывает нигде не нулевые ${\mathbb{Z}}_3$$\mathbb{Z } _{3}$ -потоки и в которой задача разрешима за полиномиальное время.

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

АппроксимацияПравить

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

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

См. такжеПравить

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

ЛитератураПравить

• 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 imgning 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: [1] (недоступная ссылка)