Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

ФКТ алгоритм , названный в честь Фишера , Кастелеен и Temperley , подсчитывает количество совершенных паросочетаний в плоском графе в полиномиальное время. Эта же задача является # P-полной для общих графов. Для сопоставлений , которые не должны быть идеальными, их подсчет остается # P-полным даже для плоских графов. Ключевая идея алгоритма FKT состоит в том, чтобы преобразовать задачу в вычисление Пфаффа кососимметричной матрицы, полученной из плоского вложения графа. Затем эффективно вычисляется пфаффиан этой матрицы с использованием стандартных детерминантных алгоритмов .

История [ править ]

Проблема подсчета плоских идеальных совпадений уходит корнями в статистическую механику и химию , где исходный вопрос был таков : если двухатомные молекулы адсорбируются на поверхности, образуя единый слой, сколькими способами они могут быть расположены? [1] функция распределения является важной величиной , которая кодирует статистические свойства системы при равновесии и может быть использована для ответа на предыдущий вопрос. Однако пытаться вычислить функцию распределения по ее определению нецелесообразно. Таким образом, точное решение физической системы - это поиск альтернативной формы статистической суммы для этой конкретной физической системы, которую достаточно просто вычислить точно. [2]В начале 1960-х определение точно решаемой не было строгим. [3] Информатика предоставила строгое определение с введением полиномиального времени , которое датируется 1965 годом. Точно так же обозначение не совсем решаемой задачи должно соответствовать # P-hardness , которое было определено в 1979 году.

Другой тип физической системы, которую следует рассмотреть, состоит из димеров , то есть полимера с двумя атомами. Модель димера подсчитывает количество димерных покрытий графа. [4] Еще одна физическая система, которую следует учитывать, - это связывание молекул H 2 O в форме льда. Это можно смоделировать как ориентированный 3- регулярный граф, в котором ориентация ребер в каждой вершине не может быть одинаковой. Сколько ориентаций краев у этой модели?

В 1961 году Кастелейн [5] и Темперли и Фишер [6], руководствуясь физическими системами, включающими димеры, независимо друг от друга нашли количество мозаик домино для прямоугольника размером m на n . Это эквивалентно подсчету количества совершенных паросочетаний для решетчатого графа размером m на n . К 1967 году Кастелейн обобщил этот результат на все плоские графы. [7] [8]

Алгоритм [ править ]

Объяснение [ править ]

Главное понимание, что каждый ненулевой член в пфаффиане части матрицы смежности графы G соответствует до идеального соответствия. Таким образом, если можно найти ориентацию на G , чтобы выровнять все признаки терминов в пфаффиане (независимо от + или - ), то абсолютное значение пфаффиана только число совершенных паросочетаний G . Алгоритм ФКТ делает такую задачу для плоского графа G . Обнаруженная ориентация называется ориентацией Пфаффа .

Пусть G = ( V , E ) неориентированный граф с матрицей смежности A . Определим PM ( n ) как набор разбиений n элементов на пары, тогда количество улучшающих сопоставлений в G равно

В тесной связи с этим является пфаффова для п по п матрицы А

где SGN ( M ) является знаком перестановки М . Пфаффовой ориентацией графа G называется ориентированный граф H с (1, −1, 0) -матрицей сопряжения B такой, что pf ( B ) = PerfMatch ( G ). [9] В 1967 году Кастелейн доказал, что плоские графы имеют эффективно вычислимую пфаффову ориентацию. В частности, для плоского графа G , пусть Н будет направлена версией G , где нечетное число ребер ориентированы по часовой стрелке для каждой грани в плоском вложении G . Тогда H - пфаффова ориентация группы G.

Наконец, для любой кососимметрической матрицы А ,

где Det ( ) является фактором , определяющим из A . Этот результат принадлежит Кэли . [10] Поскольку детерминанты вычислимы эффективно, PerfMatch ( G ) тоже .

Описание высокого уровня [ править ]

Пример, показывающий, как алгоритм FKT находит пфаффовскую ориентацию.
  1. Вычислить плоское вложение из G .
  2. Вычислить связующее дерево T 1 входного граф G .
  3. Задайте произвольную ориентацию каждому ребру в G , которое также находится в T 1 .
  4. Используйте плоское вложение , чтобы создать (неориентированный граф) T 2 с тем же множеством вершин как двойственный графом из G .
  5. Создайте ребро в T 2 между двумя вершинами, если их соответствующие грани в G имеют общее ребро в G , которое не находится в T 1 . (Обратите внимание, что T 2 - это дерево.)
  6. Для каждого листа v в T 2 (который также не является корнем):
    1. Пусть e - одинокое ребро графа G в грани, соответствующей v, которая еще не имеет ориентации.
    2. Задайте для e такую ​​ориентацию, чтобы количество ребер, ориентированных по часовой стрелке, было нечетным.
    3. Удалите v из T 2 .
  7. Возвращает абсолютное значение пфаффиана из -adjacency матрицы (1, -1, 0) из G , который является квадратным корнем из определителя.

Обобщения [ править ]

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

Теорема Куратовского утверждает, что

конечный граф является планарным тогда и только тогда , когда он не содержит подграф , гомеоморфный к K 5 ( полный граф на пять вершин) или K 3,3 ( полный двудольный граф на два разделах размера три).

Виджей Вазирани обобщил алгоритм FKT на графы, не содержащие подграф, гомеоморфный K 3,3 . [11] Так как подсчет количества совершенных сопоставлений в общем графе является # P-полным , требуется некоторое ограничение на входной граф, если только FP , функциональная версия P , не равна #P . Подсчет сопоставлений, известный как индекс Хосоя , также является # P-полным даже для плоских графов. [12]

Приложения [ править ]

Алгоритм FKT широко используется в голографических алгоритмах на планарных графах с помощью матриц . [3] Например, рассмотрим упомянутую выше плоскую версию модели льда, которая имеет техническое название # PL -3-NAE- SAT (где NAE означает «не все равны»). Valiant нашел алгоритм полиномиального времени для этой задачи, который использует матчи. [13]

Ссылки [ править ]

  1. ^ Хейс, Брайан (январь – февраль 2008 г.), «Случайные алгоритмы» , американский ученый
  2. Перейти ↑ Baxter, RJ (2008) [1982]. Точно решенные модели в статистической механике (Третье изд.). Dover Publications. п. 11. ISBN 978-0-486-46271-4.
  3. ^ а б Цай, Цзинь-И; Лу, Пиньян; Ся, Минцзи (2010). Голографические алгоритмы с Matchgates захватывают точно управляемую планарную #CSP . Основы компьютерных наук (FOCS), 51-й ежегодный симпозиум IEEE, 2010 г., посвященный . Лас-Вегас, Невада, США: IEEE. arXiv : 1008.0683 . Bibcode : 2010arXiv1008.0683C .
  4. ^ Кеньон, Ричард; Окуньков, Андрей (2005). "Что такое димер?" (PDF) . AMS . 52 (3): 342–343.
  5. ^ Кастеляйна, PW (1961), "Статистика димеров на решетке I. Число димерных механизмов на квадратной решетки.", Physica , 27 (12): 1209-1225, Bibcode : 1961Phy .... 27.1209K , DOI : 10,1016 / 0031-8914 (61) 90063-5
  6. ^ Temperley, HNV ; Фишер, Майкл Э. (1961). «Проблема Димера в статистической механике - точный результат». Философский журнал . 6 (68): 1061–1063. DOI : 10.1080 / 14786436108243366 .
  7. ^ Кастеляйна, PW (1963). «Статистика димеров и фазовые переходы». Журнал математической физики . 4 (2): 287–293. Bibcode : 1963JMP ..... 4..287K . DOI : 10.1063 / 1.1703953 .
  8. ^ Кастеляйна, PW (1967), "Теория графов и кристалл физики", в Харари, F. (ред.), Теории графов и теоретической физики , Нью - Йорк:. Academic Press, стр 43-110
  9. ^ Томас, Робин (2006). Обзор пфаффовых ориентаций графов (PDF) . Международный конгресс математиков . III . Цюрих: Европейское математическое общество. С. 963–984.
  10. ^ Кэли, Артур (1847). "Sur les определители gauches" [О косых детерминантах]. Журнал Крелля . 38 : 93–96.
  11. ^ Вазирани, Виджай В. (1989). «Алгоритмы ЧПУ для вычисления числа совершенных паросочетаний в K 3,3 -свободных графах и связанные проблемы» . Информация и вычисления . 80 (2): 152–164. DOI : 10.1016 / 0890-5401 (89) 90017-5 . ISSN 0890-5401 . 
  12. ^ Jerrum, Марк (1987), "Двумерные мономер-димер системы вычислительно неразрешимыми", Журнал статистической физики , 48 (1): 121-134, Bibcode : 1987JSP .... 48..121J , DOI : 10.1007 / BF01010403.
  13. ^ Валиант, Лесли Г. (2004). «Голографические алгоритмы (расширенная аннотация)». Материалы 45-го ежегодного симпозиума IEEE по основам информатики . FOCS'04 . Рим, Италия: Компьютерное общество IEEE. С. 306–315. DOI : 10.1109 / FOCS.2004.34 . ISBN 0-7695-2228-9.

Внешние ссылки [ править ]

  • Более подробную историю, информацию и примеры можно найти в главе 2 и разделе 5.3.2 кандидатской диссертации Дмитрия Каменецкого.