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

Многочлен является многочленом Татта графа «голова быка». Красная линия показывает пересечение с плоскостью и эквивалентна хроматическому многочлену.

Многочлен Татта (многочлен Татта — Уитни) — многочлен от двух переменных, играющий большую роль в теории графов; определён для любого неориентированного графа и содержит информацию, насколько граф связен. Стандартное обозначение — .

Первоначально изучался в алгебраической теории графов как конструкция для обобщения задач подсчёта, связанных с раскраской графов и нигде не нулевыми потоками, впоследствии обнаружена связь с многочленом Джонса из теории узлов и статистическими суммами модели Поттса[англ.] из статистической физики. Многочлен является источником некоторых вычислительных задач[англ.] теоретической информатики.

Многочлен имеет несколько эквивалентных определений: он эквивалентен многочлену ранга Уитни, дихроматическому многочлену Татта и модели случайных кластеров Фортюэна — Кастелейна (после небольшого преобразования). Многочлен, по существу, является производящей функцией для числа рёбер множеств заданного размера и связных компонент и имеет прямое обобщение в теории матроидов. Многочлен является также для графов инвариантом наиболее общего вида, который может быть определён рекурсией удаления — стягивания. Некоторые книги по теории графов и матроидам посвящают целые главы этому понятию[1][2][3].

Определения

Для неориентированного графа многочлен Татта определяется как:

,

где означает число компонент связности графа . Из определения видно, что многочлен вполне определён и полиномиален по и по .

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

.

Две функции эквивалентны, что показывается простой заменой переменных:

Дихроматический многочлен Татта является результатом другого простого преобразования:

.

Оригинальное определение Татта для связного графа эквивалентно (но это эквивалентность показывается технически сложнее):

где означает число остовных деревьев «внутренней активности и внешней активности ».

Третье определение использует рекурсию удаления — стягивания. Стягивание ребра графа  — это граф, полученный слиянием вершин и и удалением ребра , а запись  означает удаление только ребра . Тогда многочлен Татта определяется рекурсией:

,

если не является ни петлёй, ни мостом, с базовым случаем:

,

если содержит мостов и петель и никаких других рёбер. В частности , если не содержит рёбер.

Модель случайных кластеров Фортюэна — Кастелейна[4] даёт другое эквивалентное определение[5]:

эквивалентен при преобразовании[6]:

Свойства

Многочлен Татта разлагается на связные компоненты — если является объединением непересекающихся графов и , то:

.

Если является планарным, а обозначает его двойственный граф, то:

В частности, хроматический многочлен планарного графа является потоковым многочленом его двойственного.

Примеры

Изоморфные графы имеют те же самые многочлены Татта, но обратное не верно. Например, многочлен Татта любого дерева с рёбрами равен .

Многочлены Татта часто публикуются в виде таблицы коэффициентов членов в строке и столбце . Например, многочлен Татта графа Петерсена,

Записывается в виде следующей таблицы:

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

Другой пример, многочлен Татта графа октаэдра равен:

История

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

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

Специализации

В различных точках и прямых плоскости многочлен Татта даёт значения, которые изучаются сами по себе в различных областях математики и физики. Частично привлекательность многочлена Татта вызвана объединением метода анализа этих величин.

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

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

При многочлен Татта превращается в хроматический многочлен,

где обозначает число связных компонент графа .

Для целого значение хроматического многочлена равно числу раскрасок вершин графа при использовании цветов. Ясно, что не зависит от набора цветов. Менее ясно, что функция является многочленом от с целыми коэффициентами. Чтобы это понять, заметим:

  1. Если граф имеет вершин и не имеет рёбер, то .
  2. Если граф содержит петлю (ребро, соединяющее вершину с той же вершиной), то .
  3. Если  — ребро, не являющееся петлёй, то

Эти три условия позволяют нам вычислить путём последовательности удалений и стягиваний. Однако эти операции не дают гарантии, что различная последовательность операций приведёт к тому же результату. Единственность гарантируется фактом, что подсчитывает вещи, независимые от рекурсии. В частности,

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

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

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

Вдоль гиперболы многочлен Татта планарного графа сводится к многочлену Джонса связанного альтернированного узла.

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

(2,1)

подсчитывают число деревьев, то есть число ацикличных подмножеств рёбер.

(1,1)

подсчитывает число остовов (ациклических подграфов с тем же числом компонент связности, что и у графа ). Если граф связен, подсчитывают число остовных деревьев.

(1,2)

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

(2,0)

подсчитывает число ациклических ориентаций графа [11].

(0,2)

подсчитывает число строго связные ориентаций графа [12].

(0,−2)

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

подсчитывает число ациклических ориентаций графа . Здесь  — число связных компонент графа [11].

(3,3)

Если граф является -решёткой, то подсчитывает число путей замощения прямоугольника с шириной и высотой плитками T-тетрамино[13][14]

Если граф является планарным, то равен сумме взвешенных эйлеровых ориентаций в срединном графе графа , где вес равен от 2 до числа седловых вершин ориентации (то есть число вершин с рёбрами в циклическом порядке «in, out, in out»)[15].

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

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

Для гиперболы на плоскости :

многочлен Татта сводится к статистической сумме модели Изинга, изучаемой в статистической физике. В частности, вдоль гиперболы двойка связана с уравнением[16]:

.

В частности:

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

Более общо, если для любого положительного определить гиперболу:

,

то многочлен Татта сводится к статистической сумме модели Поттса[англ.] с состояниями. Различные физические величины, анализируемые с помощью модели Поттса, переходят в конкретные части .

Соответствия между моделью Поттса и плоскостью Татта[17].
Модель Поттса Многочлен Татта
Ферромагнетик Положительная ветвь
Антиферромагнетики Отрицательная ветвь with
Высокая температура Асимптота к
Низкотемпературные ферромагнетики Асимптота положительной ветви к
Ферромагентики нулевой температуры Раскраска графа в q цветов, то есть,

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

Потоковый многочлен, нарисованный в плоскости Татта

При многочлен Татта превращается в потоковый многочлен, изучаемый в комбинаторике. Для связного неориентированного графа и целого числа нигде не нулевой -поток является назначением значений «потока» рёбрам произвольной ориентации графа , так что сумма потоков входа и выхода в каждой вершине конгруэнтна по модулю . Потоковый многочлен означает число нигде не нулевых -потоков. Это значение непосредственно связано с хроматическим многочленом. Фактически, если  — планарный граф, хроматический многочлен графа эквивалентен потоковому многочлену его двойственного графа в том смысле, что имеет место следующее утверждение (Татт):

.

Связь с многочленом Татта даётся равенством:

.

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

Многочлен живучести, нарисованный на плоскости Татта

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

.

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

Татт определил также близкое обобщение от 2 переменных хроматического многочлена, дихроматический многочлен графа:

где  — число связных компонент остовного подграфа . Он связан с ранговым многочленом Уитни равенством:

.

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

Связанные многочлены

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

Многочлен Мартина ориентированного 4-регулярного графа определил Пьер Мартин в 1977[18]. Он показал, что если является плоским графом и является его ориентированным срединным графом, то

Алгоритмы

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

Алгоритм удаления — стягивания, применённый к алмазу. Красные рёбра удалены в левом потомке и стянуты в правом. Результирующий многочлен является суммой одночленов листьев, [17].

Применение формулы удаления — стягивания для многочлена Татта:

,

где не является ни петлёй, ни мостом, даёт рекурсивный алгоритм вычисления многочлена — выбирается любое подходящее ребро и применяется формула, пока не останутся только петли и мосты. Получившиеся в результате выполнения одночлены легко вычислить.

С точностью до полиномиального множителя время выполнения этого алгоритма можно выразить в терминах числа вершин и числа рёбер графа:

,

рекуррентное отношение, которое определяет числа Фибоначчи с решением[19].

Анализ может быть улучшен в величине полиномиального множителя числа остовных деревьев входного графа[20]. Для разреженных графов с время работы алгоритма равно . Для регулярных графов степени число остовных деревьев можно ограничить величиной

,

где

.

Например[21][22]:

.

На практике во избежание некоторых рекурсивных вызовов используется проверка на изоморфизм. Этот подход работает хорошо для сильно разреженных графов и графов с множеством симметрий, при этом скорость работы алгоритма зависит от метода выбора ребра [20][23][24].

Исключение Гаусса

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

равен числу остовных деревьев связного графа. Он может быть вычислен за полиномиальное время как определитель максимальной главной подматрицы матрицы Кирхгофа графа , ранний результат из алгебраической теории графов, известный как матричная теорема о деревьях. Аналогично, размерность пространства бициклов можно вычислить за полиномиальное время с помощью метода исключений Гаусса.

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

Метод Монте-Карло для цепей Маркова

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

Вычислительная сложность

С многочленом Татта ассоциируются некоторые вычислительные задачи. Наиболее прямолинейный алгоритм

Input
Граф
Output
Коэффициенты

В частности, вывод позволяет вычислить , который эквивалентен подсчёту 3-раскрасок графа . Эта задача является #P-полной[англ.], даже если она ограничена семейством планарных графов, так что задача вычисления коэффициентов многочлена Татта для данного графа является #P- трудной[англ.] даже для планарных графов.

Много больше внимания было уделено семейству задач, называемых Tutte, определённых для любой комплексной пары :

Input
Граф
Output
Значение

Трудность этой задачи меняется в зависимости от координат .

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

Плоскость Татта.
Любая точка на вещественной плоскости соответствует задаче вычисления .
В красных точках задача вычислима за полиномиальное время.
В синих точках задача является, в общем случае, #P-трудной, но вычислима за полиномиальное время для планарных графов.
В любой точке в белой области задача #P-трудна даже для двудольных планарных графов.

Если и являются неотрицательными целыми числами, задача принадлежит классу #P[англ.]. В общем случае для целых пар многочлен Татта содержит отрицательные члены, что помещает задачу в класс сложности класс GapP[англ.], замыкание класса #P[англ.] по вычитанию. Для рациональных координат можно определить рациональный аналог класса #P[англ.][26].

Вычислительная сложность точного вычисления распадается на два класса для . Задача #P-трудна, если только не лежит на гиперболе или не является одной из точек

.

В этих случаях задача разрешима за полиномиальное время[27]. Если задача ограничена классом планарных графов, в точках гиперболы задача становится вычисляемой за полиномиальное время. Все другие точки остаются #P-трудными даже для двудольных планарных графов[28]. В своей статье по дихотомии планарных графов Вертиган утверждает, что тот же результат верен, если наложить дополнительные ограничения на графы (степень вершины не превосходит трёх), за исключением точки , которая подсчитывает нигде не нулевые -потоки и в которой задача разрешима за полиномиальное время[29].

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

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

Вопрос, какие точки позволяют алгоритмы аппроксимации, хорошо изучен. Кроме точек, которые могут быть вычислены точно за полиномиальное время, единственным аппроксимационным алгоритмом, известным для , является (FPRAS) алгоритм Джеррама и Синклера, который работает для точек на гиперболе Изинга для . Если входной граф ограничен до плотных графов со степенью , существует FPRAS-алгоритм, если [30].

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

См. также

Примечания

  1. Bollobás, 1998, с. chapter 10.
  2. Biggs, 1993, с. chapter 13.
  3. Godsil, Royle, 2004, chap. 15.
  4. 1 2 Fortuin, Kasteleyn, 1972.
  5. Sokal, 2005.
  6. Sokal, 2005, с. eq. (2.26).
  7. Совершенный прямоугольник — это прямоугольник, который можно разбить на квадраты и все квадраты имеют различные размеры
  8. 1 2 Tutte, 2004.
  9. Welsh.
  10. 1 2 Farr, 2007.
  11. 1 2 Welsh, 1999.
  12. Las Vergnas, 1980.
  13. Korn, Pak, 2004.
  14. См. статью Корна и Пака (Korn, Pak 2003) о комбинаторной интерпретации многих других точек.
  15. Las Vergnas, 1988.
  16. Welsh, 1993, с. 62.
  17. 1 2 Welsh, Merino, 2000.
  18. Martin, 1977.
  19. Wilf, 1986, с. 46.
  20. 1 2 Sekine, Imai, Tani, 1995.
  21. Chung, Yau, 1999.
  22. Björklund, Husfeldt, Kaski, Koivisto, 2008.
  23. Haggard, Pearce, Royle, 2010.
  24. Pearce, Haggard, Royle, 2010.
  25. Jerrum, Sinclair, 1993.
  26. 1 2 Goldberg, Jerrum, 2008.
  27. Jaeger, Vertigan, Welsh, 1990.
  28. Vertigan, Welsh, 1992.
  29. Vertigan, 2005.
  30. Для случая ≥ 1 и = 1 см. Аннана (Annan 1994). Для случая ≥ 1 и > 1, см. стать. Алона, Фриза и Уэлша (Alon, Frieze, Welsh 1995).

Литература

Ссылки

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!