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

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

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

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

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

• 1 Определения
  • 1.1 Свойства
  • 1.2 Примеры
• 2 История
• 3 специализации
  • 3.1 Хроматический полином
  • 3.2 Полином Джонса
  • 3.3 Индивидуальные очки
    • 3.3.1 (2,1)
    • 3.3.2 (1,1)
    • 3.3.3 (1,2)
    • 3.3.4 (2,0)
    • 3.3.5 (0,2)
    • 3.3.6 (2,2)
    • 3,3,7 (0, -2)
    • 3,3,8 (3,3)
  • 3.4 Модели Поттса и Изинга
  • 3.5 Полином потока
  • 3.6 Полином надежности
  • 3.7 Дихроматический полином
• 4 Связанные многочлены
  • 4.1 Полином Мартина
• 5 алгоритмов
  • 5.1 Удаление – сокращение
  • 5.2 Гауссово исключение
  • 5.3 Цепь Маркова Монте-Карло
• 6 Вычислительная сложность
  • 6.1 Точное вычисление
  • 6.2 Приближение
• 7 См. Также
• 8 Примечания
• 9 ссылки
• 10 Внешние ссылки

Определение. Для неориентированного графа можно определить многочлен Тутте как ${\ Displaystyle G = (V, E)}$

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

где обозначает количество компонент связности графа. В этом определении ясно, что определен и многочлен от и. ${\ Displaystyle к (А)}$ ${\ Displaystyle (В, А)}$${\ displaystyle T_ {G}}$${\ displaystyle x}$${\ displaystyle y}$

То же определение можно дать, используя несколько другие обозначения, позволяя обозначать ранг графа. Тогда производящая функция ранга Уитни определяется как ${\ Displaystyle г (А) = | В | -k (А)}$ ${\ Displaystyle (В, А)}$

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

Эти две функции эквивалентны при простой замене переменных:

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

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

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

Первоначальное определение Тутте эквивалентно, но его труднее сформулировать. Для подключенного устанавливаем ${\ displaystyle T_ {G}}$${\ displaystyle G}$

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

где обозначает число остовных деревьев по внутренней деятельности и внешней деятельности. ${\ displaystyle t_ {ij}}$ ${\ displaystyle i}$ ${\ displaystyle j}$

Третье определение использует повторение удаления-сокращения. Края сжатие графа является графом, полученным путем слияния вершин и и удаления края. Мы пишем для графа, в котором просто убирается ребро. Тогда многочлен Тутте определяется рекуррентным соотношением ${\ displaystyle G / uv}$${\ displaystyle G}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle uv}$${\ displaystyle G-uv}$${\ displaystyle uv}$

${\ displaystyle T_ {G} = T_ {Ge} + T_ {G / e},}$

если не является ни петлей, ни мостом, с базовым случаем ${\ displaystyle e}$

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

если содержит перемычки и петли и не содержит других ребер. Особенно, если не содержит ребер. ${\ displaystyle G}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle T_ {G} = 1}$${\ displaystyle G}$

Модель случайных кластеров из статистической механики, разработанная Fortuin amp; Kasteleyn (1972), дает еще одно эквивалентное определение. Сумма раздела

${\ Displaystyle Z_ {G} (д, ш) = \ сумма \ nolimits _ {F \ substeq E} д ^ {к (F)} ш ^ {| F |}}$

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

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

Свойства

Полином Тутте делится на компоненты связности. Если - объединение непересекающихся графов и тогда ${\ displaystyle G}$${\ displaystyle H}$${\ displaystyle H '}$

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

Если планарен и обозначает его двойственный граф, то ${\ displaystyle G}$${\ Displaystyle G ^ {*}}$

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

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

Примеры

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

Полиномы TUTTE часто дают в табличной форме путем перечисления коэффициентов из в строке и колонке. Например, многочлен Тутте графа Петерсена, ${\ displaystyle t_ {ij}}$${\ displaystyle x ^ {i} y ^ {j}}$${\ displaystyle i}$${\ displaystyle j}$

${\ displaystyle {\ begin {align} 36x amp; + 120x ^ {2} + 180x ^ {3} + 170x ^ {4} + 114x ^ {5} + 56x ^ {6} + 21x ^ {7} + 6x ^ { 8} + x ^ {9} \\ amp; + 36y + 84y ^ {2} + 75y ^ {3} + 35y ^ {4} + 9y ^ {5} + y ^ {6} \\ amp; + 168xy + 240x ^ {2} y + 170x ^ {3} y + 70x ^ {4} y + 12x ^ {5} y \\ amp; + 171xy ^ {2} + 105x ^ {2} y ^ {2} + 30x ^ { 3} y ^ {2} \\ amp; + 65xy ^ {3} + 15x ^ {2} y ^ {3} \\ amp; + 10xy ^ {4}, \ end {выравнивается}}}$

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

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

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

${\ displaystyle {\ begin {align} amp; 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} \\ amp; + 25 \, {x} ^ {2 } +29 \, {y} ^ {4} +15 \, {y} ^ {5} +5 \, {y} ^ {6} +6 \, {y} ^ {4} x \\ amp; + 39 \, y {x} ^ {2} +20 \, {x} ^ {3} + {y} ^ {7} +8 \, y {x} ^ {3} +7 \, {x} ^ {4} + {x} ^ {5} \ end {align}}}$

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

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

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

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

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

В полином Тутте специализируется на хроматическом полиноме, ${\ displaystyle y = 0}$

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

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

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

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

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

Три вышеуказанных условия позволяют нам вычислить, применяя последовательность удалений и сокращений ребер; но они не дают гарантии, что другая последовательность удалений и сокращений приведет к тому же значению. Гарантия исходит из того, что что- то учитывается, независимо от повторения. В частности, ${\ Displaystyle \ чи _ {G} (\ лямбда)}$${\ Displaystyle \ чи _ {G} (\ лямбда)}$

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

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

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

Основная статья: многочлен Джонса Многочлен Джонса, нарисованный на плоскости Тутта

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

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

(2,1)

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

(1,1)

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

(1,2)

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

(2,0)

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

(0,2)

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

(2,2)

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

(0, −2)

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

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

подсчитывает количество эйлеровых ориентаций в G. Вот это число компонент связности G. ${\ Displaystyle к (G)}$

(3,3)

Если G является м  ×  п сетки график, а затем подсчитывает количество способов плитки прямоугольника ширина 4 м и высоту 4 п с Т-тетромиными. ${\ displaystyle 2T_ {G} (3,3)}$

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

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

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

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

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

полином Tutte специализируется на статсумму, в модели Изинга изученной в статистической физике. В частности, вдоль гиперболы эти два отношения связаны уравнением: ${\ Displaystyle Z (\ cdot),}$ ${\ displaystyle H_ {2}}$

${\ Displaystyle Z (G) = 2 \ влево (е ^ {- \ альфа} \ вправо) ^ {| E | -r (E)} \ влево (4 \ sinh \ альфа \ вправо) ^ {г (E) } T_ {G} \ left (\ coth \ alpha, e ^ {2 \ alpha} \ right).}$

В частности,

${\ Displaystyle (\ coth \ альфа -1) \ влево (е ^ {2 \ альфа} -1 \ вправо) = 2}$

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

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

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

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

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

Модель Поттса	Полином Тутте
Ферромагнетик	Положительная ветвь ${\ displaystyle H_ {q}}$
Антиферромагнитный	Отрицательная ветвь с ${\ displaystyle H_ {q}}$${\ displaystyle ygt; 0}$
Высокая температура	Асимптота до ${\ displaystyle H_ {q}}$${\ displaystyle y = 1}$
Низкотемпературный ферромагнетик	Положительная ветвь асимптотики к ${\ displaystyle H_ {q}}$${\ displaystyle x = 1}$
Антиферромагнетик нулевой температуры	График q - раскраска, т. Е. ${\ displaystyle x = 1-q, y = 0}$

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

Основная статья: Нигде-нулевой поток Полином потока, нарисованный на плоскости Тутте

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

Теорема (Тутте).

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

Связь с полиномом Тутте задается формулой:

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

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

Основная статья: Связность (теория графов) Полином надежности, нарисованный на плоскости Тутте

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

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

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

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

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

где - количество компонент связности остовного подграфа ( V, A). Это связано с коранг-дефектности полинома от ${\ Displaystyle к (А)}$

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

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

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

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

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

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

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

Основная статья: Формула удаления – сжатия Алгоритм удаления-сжатия применяется к ромбовидному графу. Красные края удаляются в левом дочернем элементе и сокращаются в правом дочернем элементе. Полученный полином является суммой одночленов в листьях. По материалам Welsh amp; Merino (2000). ${\ displaystyle x ^ {3} + 2x ^ {2} + y ^ {2} + 2xy + x + y}$

Повторяемость удаления-сжатия для многочлена Тутте,

${\ displaystyle T_ {G} (x, y) = T_ {G \ setminus e} (x, y) + T_ {G / e} (x, y), \ qquad e {\ text {ни петля, ни мост.}}}$

немедленно дает рекурсивный алгоритм для его вычисления для данного графа: пока вы можете найти ребро e, которое не является циклом или мостом, рекурсивно вычислите многочлен Тутте, когда это ребро удалено, и когда это ребро сжимается. Затем сложите два подрезультата вместе, чтобы получить общий полином Тутте для графа.

Базовый случай - это моном, где m - количество мостов, а n - количество петель. ${\ Displaystyle х ^ {м} у ^ {п}}$

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

${\ Displaystyle т (п + т) = т (п + м-1) + т (п + м-2),}$

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

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

Анализ может быть улучшена с точностью до полиномиального множителя числа из остовных деревьев входного графа. Для разреженных графиков с этим временем работы составляет. Для регулярных графов степени k количество остовных деревьев можно ограничить величиной ${\ Displaystyle \ тау (G)}$ ${\ Displaystyle м = О (п)}$${\ Displaystyle О (\ ехр (п))}$

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

где

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

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

${\ displaystyle \ nu _ {5} \ приблизительно 4,4066.}$

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

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

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

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

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

Цепь Маркова Монте-Карло

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

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

Вход: график ${\ displaystyle G}$

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

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

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

Вход: график ${\ displaystyle G}$

Выход: значение ${\ Displaystyle T_ {G} (х, у)}$

Сложность этих проблем зависит от координат. ${\ Displaystyle (х, у)}$

Точное вычисление

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

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

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

${\ Displaystyle \ влево \ {(1,1), (- 1, -1), (0, -1), (- 1,0), (я, -i), (- я, я), \ left (j, j ^ {2} \ right), \ left (j ^ {2}, j \ right) \ right \}, \ qquad j = e ^ {\ frac {2 \ pi i} {3}}.}$

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

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

Приближение

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

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

• Полином Боллобаса – Риордана
• Tutte-Гротендик инвариант является любой оценкой полинома Татты

• Alon, N.; Frieze, A.; Уэлш, DJA (1995), "Полиномиальные схемы рандомизированной аппроксимации для инвариантов Тутте-Гретендика: плотный случай", Случайные структуры и алгоритмы, 6 (4): 459–478, doi : 10.1002 / rsa.3240060409.
• Аннан, JD (1994), "Рандомизированное Аппроксимация Алгоритм подсчета количества лесов в плотных графов", Комбинаторика, вероятности и вычислительной техники, 3 (3): 273-283, DOI : 10,1017 / S0963548300001188.
• Биггс, Норман (1993), алгебраическая теория графов (2-е изд.), Cambridge University Press, ISBN   0-521-45897-8.
• Бьёрклунд, Андреас; Хусфельдт, Тор; Каски, Петтери; Койвисто, Микко (2008), "Вычисление полинома Тутте за вершинно-экспоненциальное время", Proc. 47-го ежегодного симпозиума IEEE по основам компьютерных наук (FOCS 2008), стр. 677–686, arXiv : 0711.2585, doi : 10.1109 / FOCS.2008.40, ISBN   978-0-7695-3436-7.
• Боллобаш, Бела (1998), Современная теория графов, Springer, ISBN   978-0-387-98491-9.
• Чанг, Фань ; Яу, С.-Т. (1999), «Покрытия, тепловые ядра и остовные деревья», Электронный журнал комбинаторики, 6 : R12, MR   1667452.
• Крапо, Генри Х. (1969), "О Tutte Полином", Aequationes Mathematicae, 3 (3): 211-229, DOI : 10.1007 / bf01817442.
• Фарр, Грэм Э. (2007), «Многочлены Тутта-Уитни: некоторые истории и обобщения», в Grimmett, Geoffrey ; МакДиармид, Колин (ред.), Комбинаторика, сложность и случайность. Дань Доминику Уэлшу, Оксфордская серия лекций по математике и ее приложениям, 34, Oxford University Press, стр. 28–52, ISBN   978-0-19-857127-8, Zbl   1124,05020.
• Fortuin, Cees M.; Кастелейн, Питер В. (1972), "О модели случайных кластеров: I. Введение и связь с другими моделями", Physica, Elsevier, 57 (4): 536–564, Bibcode : 1972Phy.... 57.. 536F, DOI : 10,1016 / 0031-8914 (72) 90045-6, ISSN   0031-8914.
• Годсил, Крис ; Ройл, Гордон (2004), алгебраическая теория графов, Springer, ISBN   978-0-387-95220-8.
• Голдберг, Лесли Энн ; Джеррам, Марк (2008), «Неприближаемость полинома Тутте», Информация и вычисления, 206 (7): 908–929, arXiv : cs / 0605140, doi : 10.1016 / j.ic.2008.04.003.
• Хаггард, Гэри; Пирс, Дэвид Дж.; Ройл, Гордон (2010), «Вычисление полиномов Тутта», ACM Transactions on Mathematical Software, 37 (3): Art. 24, 17, DOI : 10,1145 / 1824801,1824802, МР   2738228.
• Jaeger, F.; Вертиган, DL; Уэлш, DJA (1990), «О вычислительной сложности многочленов Джонса и Тутте», Математические слушания Кембриджского философского общества, 108 (1): 35–53, Bibcode : 1990MPCPS.108... 35J, doi : 10.1017 / S0305004100068936.
• Джеррам, Марк ; Sinclair, Алистер (1993), "алгоритмы аппроксимации полиномиальные для модели Изинга" (PDF), SIAM журнал по вычислениям, 22 (5): 1087-1116, DOI : 10,1137 / 0222066.
• Корн, Майкл; Пак, Игорь (2003), Комбинаторные оценки полинома Тутте (PDF) (препринт).
• Корн, Майкл; Пак, Игорь (2004), "Замощения прямоугольников с T-тетромино", Теоретическая информатика, 319 (1–3): 3–27, DOI : 10.1016 / j.tcs.2004.02.023.
• Лас - Vergnas, Мишель (1980), "Выпуклость в ориентированных матроидах", Журнал комбинаторной теории, Series B, 29 (2): 231-243, DOI : 10,1016 / 0095-8956 (80) 90082-9, ISSN   0095-8956, MR   0586435.
• Лас - Vergnas, Мишель (1988), "Об оценке в (3, 3) Татта полинома графа", Журнал комбинаторной теории, Series B, 45 (3): 367-372, DOI : 10.1016 / 0095- 8956 (88) 90079-2, ISSN   0095-8956.
• Мартин, Пьер (1977), Enumérations Eulériennes dans les multigraphes et invariants de Tutte-Grothendieck [ Эйлеровы перечисления в мультиграфах и инварианты Тутте-Гротендика ] (докторская диссертация) (на французском языке), Университет Жозефа Фурье.
• Пирс, Дэвид Дж.; Хаггард, Гэри; Ройл, Гордон (2010), «Эвристика выбора ребер для вычисления многочленов Тутте» (PDF), Чикагский журнал теоретической информатики : статья 6, 14, MR   2659710.
• Сэкинэ, Кёко; Имаи, Хироши; Тани, Сейичиро (1995), "Вычисление полинома Тутте графа среднего размера", Алгоритмы и вычисления (Кэрнс, 1995), Лекционные заметки по компьютерным наукам, 1004, Springer, стр. 224–233, doi : 10.1007 / BFb0015427, MR   1400247.
• Сокал, Алан Д. (2005), «Многомерный многочлен Тутте (псевдоним модель Поттса) для графов и матроидов», в Уэббе, Бриджит С. (ред.), Surveys in Combinatorics, London Mathematical Society Lecture Note Series, 327, Cambridge University Press, стр. 173–226, arXiv : math / 0503607, doi : 10.1017 / CBO9780511734885.009.
• Тутт, В. Т. (2001), теория графов, Cambridge University Press, ISBN   978-0521794893.
• Tutte, WT (2004), "Граф-многочлены", Успехи прикладной математики, 32 (1-2): 5-9, DOI : 10.1016 / S0196-8858 (03) 00041-1.
• Вертиган, DL; Уэлш, DJA (1992), «Вычислительная сложность плоскости Тутта: двудольный случай», комбинаторика, вероятность и вычисления, 1 (2): 181–187, DOI : 10.1017 / S0963548300000195.
• Вертиган, Дирк (2005), «Вычислительная сложность инвариантов Тутте для плоских графов», SIAM Journal on Computing, 35 (3): 690–712, doi : 10.1137 / S0097539704446797.
• Валлийский, DJA (1976), Теория матроидов, Academic Press, ISBN   012744050X.
• Валлийский, Доминик (1993), Сложность: узлы, раскраски и подсчет, Серия лекций Лондонского математического общества, Cambridge University Press, ISBN   978-0521457408.
• Валлийский, Доминик (1999), "The TUTTE полиномиальные", Случайные структуры и алгоритмы, Wiley, 15 (3-4): 210-228, DOI : 10.1002 / (SICI) 1098-2418 (199910/12) 15: 3 / 4 lt;210:: AID-RSA2gt; 3.0.CO; 2-R, ISSN   1042-9832.
• Валлийский, DJA ; Мерино, К. (2000), «Модель Поттса и многочлен Тутте», Журнал математической физики, 41 (3): 1127–1152, Bibcode : 2000JMP.... 41.1127W, doi : 10.1063 / 1.533181.
• Уилф, Герберт С. (1986), Алгоритмы и сложность (PDF), Прентис Холл, ISBN   0-13-021973-8, Руководство по ремонту   0897317.

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