Введение

Алгебраическое кодирование связности графа
Тютте-полином графа

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

(0,2)

подсчитывает количество сильно связных ориентаций графа G.

(2,2)

является числом, где — число ребер графа G.

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

При , полином Тютте специализируется на полиноме полной надежности, изучаемом в теории сетей. Для связного графа G удаляем каждое ребро с вероятностью p; это моделирует сеть, подверженную случайным отказам ребер. Тогда полином надежности – это функция , полином относительно p, который дает вероятность того, что любая пара вершин в G останется связанной после отказа ребер. Связь с полиномом Тютте определяется следующим образом:

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

Тутте также определил более близкое двумерное обобщение хроматического многочлена — дихроматический многочлен графа. Он определяется как

где — число связных компонент остовного подграфа (V, A). Он связан с полиномом кора́нка-нульпространства соотношением

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

Полиномиал Мартина

Полином Мартина ориентированного 4-регулярного графа был определен Пьером Мартином в 1977 году. Он показал, что если G – планарный граф, а M(G) – его направленный медиальный граф, то

Гауссовская устранение

В некоторых ограниченных случаях полином Тютте может быть вычислен за полиномиальное время, поскольку гауссово исключение эффективно вычисляет матричные операции – определитель и пфаффиан. Эти алгоритмы сами по себе являются важными результатами алгебраической теории графов и статистической механики. Число остовных деревьев связного графа равно количеству остовных деревьев. Это можно вычислить за полиномиальное время как определитель максимальной главной подматрицы матрицы Лапласа графа G, что является ранним результатом в алгебраической теории графов, известным как теорема Кирхгофа о матрице-дереве. Аналогично, размерность пространства велосипедов в можно вычислить за полиномиальное время с помощью гауссова исключения. Для планарных графов функция разделения модели Изинга, то есть полином Тютте на гиперболе , может быть выражена как пфаффиан и эффективно вычислена с помощью алгоритма FKT. Эта идея была разработана Фишером, Кастелейном и Темперли для вычисления числа покрытий димерами плоской решетки.

Марковская цепь Монте-Карло

Используя метод Монте-Карло на основе цепей Маркова, полином Тютте может быть сколь угодно точно приближен вдоль положительной ветви, что эквивалентно функции разделения ферромагнитной модели Изинга. Это основано на тесной связи между моделью Изинга и задачей подсчета паросочетаний в графе. Основная идея знаменитого результата Джеррума и Синклера заключается в построении цепи Маркова, состояниями которой являются паросочетания входного графа. Переходы определяются случайным выбором ребер и соответствующим изменением паросочетания. Полученная цепь Маркова быстро перемешивается и приводит к "достаточно случайным" паросочетаниям, которые можно использовать для восстановления функции разделения с помощью случайной выборки. В результате получается полностью полиномиальная рандомизированная схема аппроксимации (fpras).

Точный расчет

Если x и y – неотрицательные целые числа, задача относится к классу #P. Для общих пар целых чисел полином Тютте содержит отрицательные слагаемые, что помещает задачу в класс сложности GapP, являющийся замыканием #P относительно вычитания. Для учета рациональных координат можно определить рациональный аналог #P. Вычислительная сложность точного вычисления попадает в один из двух классов для любой задачи. Задача является #P-трудной, если она не лежит на гиперболе или не является одной из точек, в которых она вычислима за полиномиальное время. Если задача ограничена классом планарных графов, точки на гиперболе также становятся вычислимыми за полиномиальное время. Все остальные точки остаются #P-трудными, даже для бипартитных планарных графов. В своей работе о дихотомии для планарных графов Вертиган утверждает (в заключении), что тот же результат справедлив и для графов со степенью вершины не более трех, за исключением точки, которая подсчитывает потоки Z3 без нулевых значений и вычислима за полиномиальное время. Эти результаты содержат несколько заметных частных случаев. Например, задача вычисления разделяющей функции модели Изинга является #P-трудной в общем случае, хотя знаменитые алгоритмы Онзагера и Фишера решают ее для планарных решеток. Кроме того, многочлен Джонса #P-трудно вычислить. Наконец, вычисление числа четырех раскрасок планарного графа является #P-полным, хотя задача принятия решения тривиальна в силу теоремы о четырех цветах. В отличие от этого, легко увидеть, что подсчет числа трех раскрасок для планарных графов является #P-полным, поскольку задача принятия решения известна как NP-полная посредством парсимоничного сведения.

Приближение

Вопрос о том, для каких точек существует хороший алгоритм аппроксимации, был очень хорошо изучен. Помимо точек, которые можно вычислить точно за полиномиальное время, единственным известным алгоритмом аппроксимации является FPRAS Джеррума и Синклера, который работает для точек на гиперболе "Изинга" при y > 0. Если входные графы ограничены плотными экземплярами со степенью , то существует FPRAS при x ≥ 1, y ≥ 1. Хотя ситуация не так хорошо изучена, как в случае точных вычислений, известно, что аппроксимировать большие области плоскости сложно.