Многочле́н Та́тта (або многочлен Татта — Вітні) — многочлен від двох змінних, що відіграє значну роль у теорії графів; визначений для будь-якого неорієнтованого графа і містить інформацію, наскільки граф зв'язний. Стандартне позначення .
Спочатку вивчався в алгебричній теорії графів як конструкція для узагальнення задач підрахунку, пов'язаних з розфарбовуванням графів і ніде не нульовими потоками, згодом виявлено зв'язок із многочленом Джонса з теорії вузлів та статистичними сумами статистичної фізики. Многочлен є джерелом деяких інформатики.
Багаточлен має кілька еквівалентних визначень: він еквівалентний многочлену рангу Вітні, дихроматичному многочлену Татта та моделі випадкових кластерів Фортюена — Кастелейна (після незначного перетворення). Многочлен, по суті, є функцією для числа ребер множин заданого розміру і зв'язних компонент і має пряме узагальнення в теорії матроїдів. Многочлен є також для графів інваріантом найзагальнішого вигляду, який можна визначити рекурсією видалення стягування. Деякі книги з теорії графів і матроїдів присвячують цілі розділи цьому поняттю.
Визначення Для неорієнтованого графа многочлен Татта визначається як:
,
де — число компонент зв'язності графа . З визначення видно, що многочлен цілком визначений і поліноміальний за і за .
Те ж визначення можна дати в інших позначеннях, якщо позначити через ранг графа . Тоді твірна функція Вітні для рангу визначається як:
.
Дві функції еквівалентні, що можна показати простою заміною змінних:
Дихроматичний многочлен Татта є результатом іншого простого перетворення:
.
Оригінальне визначення Татта для зв'язного графа еквівалентне (але цю еквівалентність показати технічно складніше):
де означає кількість кістякових дерев «внутрішньої активності та зовнішньої активності ».
Третє визначення використовує рекурсію видалення — стягування. Стягування ребра графа — це граф, отриманий злиттям вершин і та видаленням ребра , а запись означає видалення тільки ребра . Тоді многочлен Татта визначається рекурсією:
,
якщо не є ні петлею, ні мостом, з базовим випадком:
,
якщо містить мостів та петель та жодних інших ребер. Зокрема , якщо не містить ребер.
Модель випадкових кластерів Фортюена — Кастелейна дає інше еквівалентне визначення:
еквівалентний при перетворенні:
Властивості Многочлен Татта розкладається на зв'язні компоненти — якщо є об'єднанням графів і , що не перетинаються, то:
.
Якщо — планарний, а позначає його двоїстий граф, то:
Зокрема, хроматичний многочлен планарного графа є потоковим многочленом його двоїстого.
Приклади Ізоморфні графи мають ті самі многочлени Татта, але протилежне хибне. Наприклад, многочлен Татта будь-якого дерева з ребрами дорівнює .
Многочлени Татта часто публікують у вигляді таблиці коефіцієнтів членів у рядку та стовпці . Наприклад, многочлен Татта графа Петерсена,
Записується у вигляді такої таблиці: 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 Інший приклад, многочлен Татта графа октаедра дорівнює:
Історія Інтерес Вільяма Татта до формули видалення-стягування виник у дні його студентства в Триніті-коледжі (Кембридж) і викликаний досконалими прямокутникамиДосконалий прямокутник — прямокутник, який можна розбити на квадрати і всі квадрати мають різні розміри й кістяковими деревами. Він часто використовував формулу в дослідженнях і «дивувався, коли виявляв інші цікаві функції на графах, інваріантні відносно ізоморфізмів, зі схожими рекурсивними формулами». Рональд Фостер зазначив, що хроматичний многочлен є однією з таких функцій, а Татт почав виявляти інші. Оригінальною термінологією для інваріантів графів, що задовольняють рекурсії видалення-стягування була W-функція, а термін V-функція він використав для множення компонент. Татт писав: «Бавлячись із W-функціями, я отримав многочлен від двох змінних, з якого можна було отримати хроматичний многочлен або потоковий многочлен, присвоївши одній змінній нуль та поправивши знаки». Татт назвав цю функцію дихроматичною і показав, що вона є узагальненням хроматичного многочлена на дві змінні, але цей многочлен зазвичай згадують як многочлен Татта. За словами Татта, «Це могло бути неприємно , який використовував аналогічні коефіцієнти і не пробував пристосувати їх для двох змінних». (Існує плутанинаWelsh. між терміном «біхромат» і дещо відмінним «біхроматичним многочленом», який Татт увів у іншій статті.) Узагальнення многочлена Татта для матроїдів опублікував Крапо, хоча воно вже з'являлося в тезах Татта.
Незалежно, працюючи в галузі алгебричної теорії графів, Поттс почав 1952 року вивчати статистичні суми деяких моделей статистичної механіки. У роботі 1972 року про модель випадкових кластерів, узагальнення , Фортюен і Кастелльон дали об'єднаний вираз, який показав зв'язок цієї моделі з многочленом Татта.
Спеціалізації У різних точках та прямих площини многочлен Татта дає значення, які окремо вивчаються в різних галузях математики і фізики. Частково привабливість многочлена Татта викликана поєднанням методу аналізу цих величин.
Хроматичний многочлен
При многочлен Татта перетворюється на хроматичний многочлен,
де позначає кількість зв'язних компонент графа .
Для цілого значення хроматичного многочлена дорівнює кількості розфарбувань вершин графа за використання кольорів. Зрозуміло, що не залежить від набору кольорів. Менш ясно, що функція є багаточленом від із цілими коефіцієнтами. Щоб це зрозуміти, зауважимо:
Якщо граф має вершин і не має ребер, то . Якщо граф містить петлю (ребро, що з'єднує вершину з тією самою вершиною), то . Якщо — ребро, яке не є петлею, то
Ці три умови дозволяють обчислити послідовними видаленнями та стягуваннями. Однак ці операції не дають гарантії, що різна послідовність операцій призведе до того ж результату. Єдиність гарантується фактом, що підраховує речі, незалежні від рекурсії. Зокрема,
дає кількість ациклічних орієнтацій.
Многочлен Джонса
Уздовж гіперболи многочлен Татта планарного графа зводиться до многочлена Джонса пов'язаного альтернованого вузла.
Індивідуальні точки
(2,1) підраховують кількість дерев, тобто число ациклічних підмножин ребер.
(1,1) підраховує кількість кістяків (ациклічних підграф з тим самим числом компонент зв'язності, що й у графа ). Якщо граф зв'язний, підраховує кількість кістякових дерев.
(1,2) підраховує кількість кістякових підграфів із таким самим числом компонент зв'язності, що й у графа .
(2,0) підраховує кількість ациклічних орієнтацій графа .
(0,2) підраховує число строго зв'язних орієнтацій графа .
(0,-2) Якщо граф є 4-регулярним графом, то
підраховує кількість ациклічних орієнтацій графа . Тут — число зв'язних компонент графа .
(3,3) Якщо граф є -решіткою, то підраховує кількість шляхів замощення прямокутника із шириною та всотою плитками T-тетраміноДив. статтю Корна і Пака про комбінаторну інтерпретацію багатьох інших точок..
Якщо граф планарний, то дорівнює сумі зважених ейлерових орієнтацій у серединному графі графа де вага дорівнює від 2 до числа сідлових вершин орієнтації (тобто число вершин з ребрами в циклічному порядку «in, out, in out»).
Моделі Поттса та Ізінга
Для гіперболи на площині :
многочлен Татта зводиться до статистичної суми моделі Ізінга, що вивчається в статистичній фізиці. Зокрема, вздовж гіперболи двійка пов'язана з рівнянням:
.
Зокрема:
для всіх комплексних .
Загальніше, якщо для будь-якого додатного визначити гіперболу:
,
то многочлен Татта зводиться до статистичної суми з станами. Різні фізичні величини, аналізовані за допомогою моделі Поттса, перетворюються на конкретні частини . +Відповідності між моделлю Поттса та площиною Татта Модель Поттса Многочлен Татта Феромагнетик Додатна гілка Антиферомагнетики Від'ємна гілка при Висока температура Асимптота до Низькотемпературні феромагнетики Асимптота додатної гілки до Ферромагентики нульової температури Розфарбування графа в q кольорів, тобто,
Потоковий многочлен
При многочлен Татта перетворюється на потоковий многочлен, що вивчається в комбінаториці. Для зв'язного неорієнтованого графа і цілого числа ніде не нульовий -потік є призначенням значень «потоку» ребрам довільної орієнтації графа , так що сума потоків входу та виходу в кожній вершині конгруентна за модулем . Потоковий многочлен означає число ніде не нульових -потоків. Це значення безпосередньо пов'язане з хроматичним многочленом. Фактично, якщо — планарний граф, хроматичний многочлен графа еквівалентний потоковому многочлену його двоїстого графа у тому сенсі, що має місце таке твердження (Татт):
.
Зв'язок із многочленом Татта дається рівністю:
.
Многочлен живучості
При многочлен Татта перетворюється на многочлен живучості, що вивчається в теорії мереж. У зв'язному графі видаляється будь-яке ребро з ймовірністю , що моделює випадкові випадання ребра. Тоді многочлен живучості — це функція , многочлен від , який дає ймовірність, що будь-яка пара вершин у залишається зв'язною після випадання ребра. Зв'язок із многочленом Татта описує рівність
.
Дихроматичний многочлен Татт визначив також близьке узагальнення від 2 змінних хроматичного многочлена, дихроматичний многочлен графа:
де — число зв'язних компонент кістякового підграфа . Він пов'язаний із ранговим многочленом Вітні рівністю:
.
Дихроматичний многочлен не узагальнюється для матроїдів, оскільки не є властивістю матроїдів — різні графи з тим самим матроїдом можуть мати різну кількість компонент зв'язності.
Пов'язані багаточлени
Многочлен Мартіна Многочлен Мартіна орієнтованого 4-регулярного графа визначив П'єр Мартін 1977 року. Він показав, що якщо — плоский граф та — його орієнтований серединний граф, то
Алгоритми
Формула видалення-стягування
Використання формули видалення-стягування для многочлена Татта
,
де не є ні петлею, ні мостом, дає рекурсивний алгоритм обчислення многочлена — вибирається будь-яке відповідне ребро і застосовується формула, доки не залишаться тільки петлі та мости. Одночлени, отриманеі в результаті виконання, легко обчислити.
З точністю до поліноміального множника час виконання цього алгоритму можна виразити в термінах числа вершин та числа ребер графа:
,
рекурентне відношення, яке зростає як числа Фібоначчі.
Аналіз можна покращити у величині поліноміального множника числа кістякових дерев вхідного графа. Для розріджених графів з час роботи алгоритму дорівнює . Для регулярних графів степеня число кістякових дерев можна обмежити величиною
,
де
.
Наприклад:
.
На практиці, щоб уникнути деяких рекурсивних викликів, використовується перевірка на ізоморфізм. Цей підхід добре працює для сильно розріджених графів і графів з багатьма симетріями, при цьому швидкість роботи алгоритму залежить від методу вибору ребра .
Виняток Гауса У деяких обмежених випадках многочлен Татта можна обчислити за поліноміальний час завдяки тому, що виняток Гауса ефективно обчислює визначник і пфаффіан. Ці алгоритми самі є важливим результатом алгебричної теорії графів і статистичної механіки.
дорівнює числу кістякових дерев зв'язного графа. Його можна обчислити за поліноміальний час як визначник максимальної головної підматриці матриці Кірхгофа графа — ранній результат алгебричної теорії графів, відомий як матрична теорема про дерева. Аналогічно, розмірність простору біциклів можна обчислити за поліноміальний час за допомогою методу винятків Гауса.
Для планарних графів функція розподілу моделі Ізінга, тобто многочлен Татта на гіперболі , можна виразити як пфаффіан і ефективно обчислити за допомогою алгоритму FKT. Цю ідею розробляли , і для обчислення числа покриттів плитками доміно планарної моделі ґратки.
Метод Монте-Карло для ланцюгів Маркова