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

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

Многочле́н Та́тта (або многочлен Татта — Вітні) — многочлен від двох змінних, що відіграє значну роль у теорії графів; визначений для будь-якого неорієнтованого графа і містить інформацію, наскільки граф зв'язний. Стандартне позначення $T_{G}$.

Спочатку вивчався в алгебричній теорії графів як конструкція для узагальнення задач підрахунку, пов'язаних з розфарбовуванням графів і ніде не нульовими потоками, згодом виявлено зв'язок із многочленом Джонса з теорії вузлів та статистичними сумами моделі Поттса статистичної фізики. Многочлен є джерелом деяких обчислювальних задач інформатики.

Багаточлен має кілька еквівалентних визначень: він еквівалентний многочлену рангу Вітні^[⇨], дихроматичному многочлену Татта^[⇨] та моделі випадкових кластерів Фортюена — Кастелейна (після незначного перетворення)^[⇨]. Многочлен, по суті, є функцією для числа ребер множин заданого розміру і зв'язних компонент і має пряме узагальнення в теорії матроїдів. Многочлен є також для графів інваріантом найзагальнішого вигляду, який можна визначити рекурсією видалення стягування^[⇨]. Деякі книги з теорії графів і матроїдів присвячують цілі розділи цьому поняттю.

Визначення

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

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

де $k(A)$ — число компонент зв'язності графа $(V,A)$. З визначення видно, що многочлен $T_{G}$ цілком визначений і поліноміальний за $x$ і за $y$.

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

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

Дві функції еквівалентні, що можна показати простою заміною змінних:

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

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

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

Оригінальне визначення Татта $T_{G}$ для зв'язного графа $G$ еквівалентне (але цю еквівалентність показати технічно складніше):

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

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

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

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

якщо $e$ не є ні петлею, ні мостом, з базовим випадком:

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

якщо $G$ містить $i$ мостів та $j$ петель та жодних інших ребер. Зокрема $T_{G}=1$, якщо $G$ не містить ребер.

Модель випадкових кластерів Фортюена — Кастелейна дає інше еквівалентне визначення:

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

еквівалентний $T_{G}$ при перетворенні:

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

Властивості

Многочлен Татта розкладається на зв'язні компоненти — якщо $G$ є об'єднанням графів $H$ і $H'$, що не перетинаються, то:

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

Якщо $G$ — планарний, а $G^{*}$ позначає його двоїстий граф, то:

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

Зокрема, хроматичний многочлен планарного графа є потоковим многочленом його двоїстого.

Приклади

Ізоморфні графи мають ті самі многочлени Татта, але протилежне хибне. Наприклад, многочлен Татта будь-якого дерева з $m$ ребрами дорівнює $x^{m}$.

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

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

Записується у вигляді такої таблиці:

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

Інший приклад, многочлен Татта графа октаедра дорівнює:

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

Історія

Інтерес Вільяма Татта до формули видалення-стягування виник у дні його студентства в Триніті-коледжі (Кембридж) і викликаний досконалими прямокутниками й кістяковими деревами. Він часто використовував формулу в дослідженнях і «дивувався, коли виявляв інші цікаві функції на графах, інваріантні відносно ізоморфізмів, зі схожими рекурсивними формулами». Рональд Фостер зазначив, що хроматичний многочлен є однією з таких функцій, а Татт почав виявляти інші. Оригінальною термінологією для інваріантів графів, що задовольняють рекурсії видалення-стягування була W-функція, а термін V-функція він використав для множення компонент. Татт писав: «Бавлячись із W-функціями, я отримав многочлен від двох змінних, з якого можна було отримати хроматичний многочлен або потоковий многочлен, присвоївши одній змінній нуль та поправивши знаки». Татт назвав цю функцію дихроматичною і показав, що вона є узагальненням хроматичного многочлена на дві змінні, але цей многочлен зазвичай згадують як многочлен Татта. За словами Татта, «Це могло бути неприємно Гасслеру Вітні, який використовував аналогічні коефіцієнти і не пробував пристосувати їх для двох змінних». (Існує плутанина між терміном «біхромат» і дещо відмінним «біхроматичним многочленом», який Татт увів у іншій статті.) Узагальнення многочлена Татта для матроїдів опублікував Крапо, хоча воно вже з'являлося в тезах Татта.

Незалежно, працюючи в галузі алгебричної теорії графів, Поттс почав 1952 року вивчати статистичні суми деяких моделей статистичної механіки. У роботі 1972 року про модель випадкових кластерів, узагальнення моделі Поттса, Фортюен і Кастелльон дали об'єднаний вираз, який показав зв'язок цієї моделі з многочленом Татта.

Спеціалізації

У різних точках та прямих площини $(x,y)$ многочлен Татта дає значення, які окремо вивчаються в різних галузях математики і фізики. Частково привабливість многочлена Татта викликана поєднанням методу аналізу цих величин.

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

Хроматичний многочлен, намальований на площині Татта

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

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

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

Для цілого $\lambda$ значення хроматичного многочлена $\chi _{G}(\lambda )$ дорівнює кількості розфарбувань вершин графа $G$ за використання $\lambda$ кольорів. Зрозуміло, що $\chi _{G}(\lambda )$ не залежить від набору кольорів. Менш ясно, що функція є багаточленом від $\lambda$ із цілими коефіцієнтами. Щоб це зрозуміти, зауважимо:

1. Якщо граф $G$ має $n$ вершин і не має ребер, то $\chi _{G}(\lambda )=\lambda ^{n}$.
2. Якщо граф $G$ містить петлю (ребро, що з'єднує вершину з тією самою вершиною), то $\chi _{G}(\lambda )=0$.
3. Якщо $e$ — ребро, яке не є петлею, то

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

Ці три умови дозволяють обчислити $\chi _{G}(\lambda )$ послідовними видаленнями та стягуваннями. Однак ці операції не дають гарантії, що різна послідовність операцій призведе до того ж результату. Єдиність гарантується фактом, що $\chi _{G}(\lambda )$ підраховує речі, незалежні від рекурсії. Зокрема,

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

дає кількість ациклічних орієнтацій.

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

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

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

Індивідуальні точки

(2,1)

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

(1,1)

$T_{G}(1,1)$ підраховує кількість кістяків (ациклічних підграф з тим самим числом компонент зв'язності, що й у графа $G$). Якщо граф зв'язний, $T_{G}(1,1)$ підраховує кількість кістякових дерев.

(1,2)

$T_{G}(1,2)$ підраховує кількість кістякових підграфів із таким самим числом компонент зв'язності, що й у графа $G$.

(2,0)

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

(0,2)

$T_{G}(0,2)$ підраховує число строго зв'язних орієнтацій графа $G$.

(0,-2)

Якщо граф $G$ є 4-регулярним графом, то

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

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

(3,3)

Якщо граф $G$ є $m\times n$-решіткою, то $2T_{G}(3,3)$ підраховує кількість шляхів замощення прямокутника із шириною $4m$ та всотою $4n$ плитками T-тетраміно.

Якщо граф $G$ планарний, то $2T_{G}(3,3)$ дорівнює сумі зважених ейлерових орієнтацій у серединному графі графа $G$ де вага дорівнює від 2 до числа сідлових вершин орієнтації (тобто число вершин з ребрами в циклічному порядку «in, out, in out»^{[прояснити]}).

Моделі Поттса та Ізінга

Статистична сума для моделі Ізінга та моделі Поттса з 3 та 4 станами, намальованими на площині Татта

Для гіперболи на площині $xy$ :

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

многочлен Татта зводиться до статистичної суми $Z(\cdot )$ моделі Ізінга, що вивчається в статистичній фізиці. Зокрема, вздовж гіперболи $H_{2}$ двійка пов'язана з рівнянням:

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

Зокрема:

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

для всіх комплексних $\alpha$.

Загальніше, якщо для будь-якого додатного $q$ визначити гіперболу:

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

то многочлен Татта зводиться до статистичної суми моделі Поттса з $q$ станами. Різні фізичні величини, аналізовані за допомогою моделі Поттса, перетворюються на конкретні частини $H_{q}$.

Відповідності між моделлю Поттса та площиною Татта

Модель Поттса	Многочлен Татта
Феромагнетик	Додатна гілка $H_{q}$
Антиферомагнетики	Від'ємна гілка $H_{q}$ при $y>0$
Висока температура	Асимптота $H_{q}$ до $y=1$
Низькотемпературні феромагнетики	Асимптота додатної гілки $H_{q}$ до $x=1$
Ферромагентики нульової температури	Розфарбування графа в q кольорів, тобто, $x=1-q,y=0$

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

Потоковий многочлен, намальований у площині Татта

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

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

Зв'язок із многочленом Татта дається рівністю:

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

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

Многочлен живучості, намальований на площині Татта

При $x=1$ многочлен Татта перетворюється на многочлен живучості, що вивчається в теорії мереж. У зв'язному графі $G$ видаляється будь-яке ребро з ймовірністю $p$, що моделює випадкові випадання ребра. Тоді многочлен живучості — це функція $R_{G}(p)$, многочлен від $p$, який дає ймовірність, що будь-яка пара вершин у $G$ залишається зв'язною після випадання ребра. Зв'язок із многочленом Татта описує рівність

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

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

Татт визначив також близьке узагальнення від 2 змінних хроматичного многочлена, дихроматичний многочлен графа:

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

де $k(A)$ — число зв'язних компонент кістякового підграфа $(V,A)$. Він пов'язаний із ранговим многочленом Вітні рівністю:

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

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

Пов'язані багаточлени

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

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

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

Алгоритми

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

Алгоритм видалення-стягування, застосований до алмаза. Червоні ребра видалено в лівому нащадку і стягнуто в правому. Отриманий многочлен є сумою одночленів листків, $x^{3}+2x^{2}+y^{2}+2xy+x+y$.

Використання формули видалення-стягування для многочлена Татта

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

де $e$ не є ні петлею, ні мостом, дає рекурсивний алгоритм обчислення многочлена — вибирається будь-яке відповідне ребро $e$ і застосовується формула, доки не залишаться тільки петлі та мости. Одночлени, отриманеі в результаті виконання, легко обчислити.

З точністю до поліноміального множника час виконання $t$ цього алгоритму можна виразити в термінах числа вершин $n$ та числа ребер $m$ графа:

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

рекурентне відношення, яке зростає як числа Фібоначчі.

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

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

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

де

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

Наприклад:

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

На практиці, щоб уникнути деяких рекурсивних викликів, використовується перевірка на ізоморфізм. Цей підхід добре працює для сильно розріджених графів і графів з багатьма симетріями, при цьому швидкість роботи алгоритму залежить від методу вибору ребра $e$.

Виняток Гауса

У деяких обмежених випадках многочлен Татта можна обчислити за поліноміальний час завдяки тому, що виняток Гауса ефективно обчислює визначник і пфаффіан. Ці алгоритми самі є важливим результатом алгебричної теорії графів і статистичної механіки.

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

Для планарних графів функція розподілу моделі Ізінга, тобто многочлен Татта на гіперболі $H_{2}$, можна виразити як пфаффіан і ефективно обчислити за допомогою алгоритму FKT. Цю ідею розробляли Фішер, Кастелейн і Темперлі для обчислення числа покриттів плитками доміно планарної моделі ґратки.

Метод Монте-Карло для ланцюгів Маркова

Використовуючи метод Монте-Карло для ланцюгів Маркова, можна довільно добре апроксимувати многочлен Татта вздовж гілки $H_{2}$, еквівалентно, функції розподілу феромагнітної моделі Ізінга. Цей підхід використовує тісний зв'язок між моделлю Ізінга та задачею підрахунку парувань у графі. Ідея цього підходу, що належить Джерраму і Синклеру, полягає в утворенні ланцюга Маркова, стан якого відповідає паруванням вхідного графа. Переходи визначаються вибором ребер випадковим чином і відповідно модифікуються пароування. Отриманий ланцюг Маркова швидко змішується і веде до «досить випадкових» парувань, які можна використати для виявлення функції розподілу, використовуючи випадкову вибірку. Отриманий алгоритм є схемою наближення до поліноміального часу (FPRAS).

Обчислювальна складність

Із многочленом Татта асоціюються деякі обчислювальні задачі. Найочевидніша:

Вхід

Граф $G$

Вихід

Коефіцієнти $T_{G}$

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

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

Вхід

Граф $G$

Вихід

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

Складність цієї задачі змінюється залежно від координат $(x,y)$.

Точне обчислення

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

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

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

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

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

Ці результати містять деякі важливі окремі випадки. Наприклад, задача обчислення функції розподілу моделі Ізінга в загальному випадку #P-складна, хоча алгоритми Онсангера та Фішера розв'язують її для плоских решіток. Також обчислення многочлена Джонса є #P-складною задачею. Нарешті, обчислення числа розфарбувань у чотири кольори планарного графа #P-повне, хоча задача розв'язності тривіальна, зважаючи на теорему про чотири фарби. Для контрасту, легко бачити, що підрахунок числа розфарбувань планарного графа в три кольори є #P-повним, оскільки відомо, що задача розв'язності NP-повна згідно з економному зниження.

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

Питання, які точки дозволяють алгоритми апроксимації, добре вивчене. Крім точок, які можна обчислити точно за поліноміальний час, єдиним апроксимаційним алгоритмом, відомим для $T_{G}(x,y)$, є (FPRAS) алгоритм Джеррама та Синклера, який працює для точок на гіперболі Ізінга $H_{2}$ для $y>0$. Якщо вхідний граф обмежено до щільних графів зі степенем $\Omega (n)$ існує FPRAS-алгоритм, якщо $x\geqslant 1,y\geqslant 1$.

Хоча в разі апроксимації ситуація не так добре вивчена, як для точних обчислень, відомо, що великі ділянки площини важко апроксимувати.

Див. також

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

Література

• 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. — (Series B). — 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. — (Series B). — 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, ред. (2001), Tutte polynomial, Математична енциклопедія, Springer, ISBN 978-1-55608-010-4
• Weisstein, Eric W. Многочлен Татта(англ.) на сайті 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]^{[недоступне посилання з мая 2021]}