Многочле н Та тта або многочлен Татта Вітні многочлен від двох змінних що відіграє значну роль у теорії графів визначени

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

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

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

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

Визначення

Для неорієнтованого графа $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-функціями, я отримав многочлен від двох змінних, з якого можна було отримати хроматичний многочлен або потоковий многочлен, присвоївши одній змінній нуль та поправивши знаки». Татт назвав цю функцію дихроматичною і показав, що вона є узагальненням хроматичного многочлена на дві змінні, але цей многочлен зазвичай згадують як многочлен Татта. За словами Татта, «Це могло бути неприємно ^[en], який використовував аналогічні коефіцієнти і не пробував пристосувати їх для двох змінних». (Існує плутанина між терміном «біхромат» і дещо відмінним «біхроматичним многочленом», який Татт увів у іншій статті.) Узагальнення многочлена Татта для матроїдів опублікував Крапо, хоча воно вже з'являлося в тезах Татта.

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

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

У різних точках та прямих площини $(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$ із цілими коефіцієнтами. Щоб це зрозуміти, зауважимо:

Якщо граф $G$ має $n$ вершин і не має ребер, то $\chi _{G}(\lambda )=\lambda ^{n}$ .
Якщо граф $G$ містить петлю (ребро, що з'єднує вершину з тією самою вершиною), то $\chi _{G}(\lambda )=0$ .
Якщо $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

,

то многочлен Татта зводиться до статистичної суми ^[en] з $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}$ , можна виразити як пфаффіан і ефективно обчислити за допомогою . Цю ідею розробляли ^[ru], ^[en] і ^[en] для обчислення числа покриттів планарної .

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

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

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

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

Вхід: Граф $G$
Вихід: Коефіцієнти $T_{G}$

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

Значно більше уваги приділено сімейству задач, званих 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)$ належить до ^[en]. У випадку для цілих пар многочлен Татта містить від'ємні члени, що поміщає задачу в клас складності ^[en], замикання ^[en] за відніманням. Для раціональних координат $(x,y)$ можна визначити раціональний аналог ^[en].

Обчислювальна складність точного обчислення $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-повна згідно з ^[en].

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

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

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

Див. також

^[en]

Примітки

Bollobás, 1998, с. розділ 10.
Biggs, 1993, с. розділ 13.
Godsil, Royle, 2004, розд. 15.
Fortuin, Kasteleyn, 1972.
Sokal, 2005.
Sokal, 2005, с. рівн. (2.26).
Досконалий прямокутник — прямокутник, який можна розбити на квадрати і всі квадрати мають різні розміри
Tutte, 2004.
Welsh.
Farr, 2007.
Welsh, 1999.
Las Vergnas, 1980.
Korn, Pak, 2004.
Див. статтю Корна і Пака (Korn, Pak, 2003) про комбінаторну інтерпретацію багатьох інших точок.
Las Vergnas, 1988.
Welsh, 1993, с. 62.
Welsh, Merino, 2000.
Martin, 1977.
Wilf, 1986, с. 46.
Sekine, Imai, Tani, 1995.
Chung, Yau, 1999.
Björklund, Husfeldt, Kaski, Koivisto, 2008.
Haggard, Pearce, Royle, 2010.
Pearce, Haggard, Royle, 2010.
Jerrum, Sinclair, 1993.
Goldberg, Jerrum, 2008.
Jaeger, Vertigan, Welsh, 1990.
Vertigan, Welsh, 1992.
Vertigan, 2005.
Для випадку $x$ ≥ 1 і $y$ = 1 див. Аннана (Annan, 1994). Для випадку $x$ ≥ 1 і $y$ > 1, див. статтю Алона, Фріза і Велша (Alon, Frieze, Welsh, 1995).

Література

Alon N., Frieze A., Welsh D. J. A. Polynomial time randomized approximation schemes for Tutte-Gröthendieck invariants: The dense case // Random Structures and Algorithms. — 1995. — Т. 6, вип. 4. — С. 459–478. — DOI:10.1002/rsa.3240060409.
Annan J. D. A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs // . — 1994. — Т. 3, вип. 3. — С. 273–283. — DOI:10.1017/S0963548300001188.
Norman Biggs. Algebraic Graph Theory. — 2nd. — Cambridge University Press, 1993. — .
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. — . — DOI:10.1109/FOCS.2008.40.
Béla Bollobás. Modern Graph Theory. — Springer, 1998. — .
Fan Chung, S.-T. Yau. Coverings, heat kernels and spanning trees // . — 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) — .
Cees M. Fortuin, Pieter W. Kasteleyn. On the random-cluster model: I. Introduction and relation to other models. — ^[en]. — Elsevier, 1972. — Т. 57. — С. 536–564. — DOI:10.1016/0031-8914(72)90045-6.
Chris Godsil, Gordon Royle. Algebraic Graph Theory. — Springer, 2004. — .
Leslie Ann Goldberg, Mark Jerrum. Inapproximability of the Tutte polynomial // . — 2008. — Т. 206, вип. 7. — С. 908–929. — DOI:10.1016/j.ic.2008.04.003.
Gary Haggard, David J. Pearce, Gordon Royle. Computing Tutte polynomials // . — 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 // . — 1990. — Т. 108. — С. 35–53. — DOI:10.1017/S0305004100068936.
Mark Jerrum, Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model // . — 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 // ^[en]. — 2004. — Т. 319, вип. 1–3. — С. 3–27. — DOI:10.1016/j.tcs.2004.02.023.
Michel Las Vergnas. Convexity in oriented matroids // . — 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 // . — 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. — , 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. — () — 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.
. Graph Theory. — Cambridge University Press, 2001. — .
W. T. Tutte. Graph-polynomials // . — 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 // . — 1992. — Т. 1, вип. 2. — С. 181–187. — DOI:10.1017/S0963548300000195.
Dirk Vertigan. The Computational Complexity of Tutte Invariants for Planar Graphs // . — 2005. — Т. 35, вип. 3. — С. 690–712. — DOI:10.1137/S0097539704446797.
D. J. A. Welsh. Matroid Theory. — , 1976. — .
Dominic Welsh. Complexity: Knots, Colourings and Counting. — Cambridge University Press, 1993. — (London Mathematical Society Lecture Note Series) — .
Dominic Welsh. The Tutte polynomial. — Random Structures & Algorithms. — , 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. — .

Посилання

Hazewinkel, Michiel, ред. (2001), Tutte polynomial, Математична енциклопедія, , ISBN
Weisstein, Eric W. Многочлен Татта(англ.) на сайті Wolfram MathWorld.
PlanetMath
Steven R. Pagano:
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]}

[FOOTNOTEBollobás1998розділ_10-1] Bollobás, 1998, с. розділ 10.

[FOOTNOTEBiggs1993розділ_13-2] Biggs, 1993, с. розділ 13.

[FOOTNOTEGodsil,_Royle2004розд._15-3] Godsil, Royle, 2004, розд. 15.

[FOOTNOTEFortuin,_Kasteleyn1972-4] Fortuin, Kasteleyn, 1972.

[FOOTNOTESokal2005-5] Sokal, 2005.

[FOOTNOTESokal2005рівн._(2.26)-6] Sokal, 2005, с. рівн. (2.26).

[7] Досконалий прямокутник — прямокутник, який можна розбити на квадрати і всі квадрати мають різні розміри

[FOOTNOTETutte2004-8] Tutte, 2004.

[9] Welsh.

[FOOTNOTEFarr2007-10] Farr, 2007.

[FOOTNOTEWelsh1999-11] Welsh, 1999.

[FOOTNOTELas_Vergnas1980-12] Las Vergnas, 1980.

[FOOTNOTEKorn,_Pak2004-13] Korn, Pak, 2004.

[14] Див. статтю Корна і Пака (Korn, Pak, 2003) про комбінаторну інтерпретацію багатьох інших точок.

[FOOTNOTELas_Vergnas1988-15] Las Vergnas, 1988.

[FOOTNOTEWelsh199362-16] Welsh, 1993, с. 62.

[FOOTNOTEWelsh,_Merino2000-17] Welsh, Merino, 2000.

[FOOTNOTEMartin1977-18] Martin, 1977.

[FOOTNOTEWilf198646-19] Wilf, 1986, с. 46.

[FOOTNOTESekine,_Imai,_Tani1995-20] Sekine, Imai, Tani, 1995.

[FOOTNOTEChung,_Yau1999-21] Chung, Yau, 1999.

[FOOTNOTEBjörklund,_Husfeldt,_Kaski,_Koivisto2008-22] Björklund, Husfeldt, Kaski, Koivisto, 2008.

[FOOTNOTEHaggard,_Pearce,_Royle2010-23] Haggard, Pearce, Royle, 2010.

[FOOTNOTEPearce,_Haggard,_Royle2010-24] Pearce, Haggard, Royle, 2010.

[FOOTNOTEJerrum,_Sinclair1993-25] Jerrum, Sinclair, 1993.

[FOOTNOTEGoldberg,_Jerrum2008-26] Goldberg, Jerrum, 2008.

[FOOTNOTEJaeger,_Vertigan,_Welsh1990-27] Jaeger, Vertigan, Welsh, 1990.

[FOOTNOTEVertigan,_Welsh1992-28] Vertigan, Welsh, 1992.

[FOOTNOTEVertigan2005-29] Vertigan, 2005.

[30] Для випадку $x$ ≥ 1 і $y$ = 1 див. Аннана (Annan, 1994). Для випадку $x$ ≥ 1 і $y$ > 1, див. статтю Алона, Фріза і Велша (Alon, Frieze, Welsh, 1995).