Алгоритм FKT

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

FKT (назван по именам Фишера, Кастеляйна[en] и Темперли[en]) — алгоритм, подсчитывающий число совершенных паросочетаний в планарном графе за полиномиальное время. Та же задача является #P-полной[en] для общих графов. Вычисление числа паросочетаний даже для планарных графов является также #P-полной задачей. Ключевой идеей является сведение задачи к вычислению пфаффиана кососимметричной матрицы, полученной из планарного вложения графа. Пфаффиан этой матрицы вычисляется тогда эффективно с помощью стандартных алгоритмов вычисления определителя.

История

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

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

Заинтересовавшись физическими системами из димеров, в 1961-м году Кастеляйн[5], а также Темперли вместе с Фишером[6] независимо нашли число замощений костяшками домино для прямоугольника [math]\displaystyle{ m \times n }[/math]. Это эквивалентно подсчёту числа совершенных паросочетаний для [math]\displaystyle{ m \times n }[/math] решётки. В 1967 году Кастеляйн обобщил этот результат на все планарные графы[7][8].

Алгоритм

Подход

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

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

[math]\displaystyle{ \operatorname{PerfMatch}(G)=\sum_{M \in PM(|V|)} \prod_{(i,j) \in M} A_{i j}. }[/math]

Тесно связан с этим пфаффиан для [math]\displaystyle{ n \times n }[/math] матрицы A

[math]\displaystyle{ \operatorname{pf}(A)=\sum_{M \in PM(n)} \operatorname{sgn}(M) \prod_{(i,j) \in M} A_{i j}, }[/math]

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

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

[math]\displaystyle{ \operatorname{pf}(A)^2=\det(A), }[/math]

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

Описание алгоритма

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

Обобщения

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

Теорема Понтрягина — Куратовского утверждает, что

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

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

Приложения

Алгоритм FKT интенсивно используется в голографических алгоритмах[en] на планарных графах через matchgates (двухкубитовые элементы Вэлианта)[3]. Например, рассмотрим плоскую версию модели льда, упомянутую выше, которая имеет техническое название #PL-3-NAE-SAT (здесь NAE означает «Not All Equal» = «не все равны»). Вэлиант нашёл алгоритм полиномиального времени для решения этой задачи, который использует matchgates[13].

Примечания

  1. ↑ Hayes, 2008.
  2. ↑ Baxter, 2008, с. 11.
  3. ↑ 3,0 3,1 Cai, Lu, Xia, 2010.
  4. ↑ Kenyon, Okounkov, 2005, с. 342–343.
  5. ↑ Kasteleyn, 1961, с. 1209–1225.
  6. ↑ Temperley, Fisher, 1961, с. 1061–1063.
  7. ↑ Kasteleyn, 1963, с. 287–293.
  8. ↑ Kasteleyn, 1967, с. 43–110.
  9. ↑ Thomas, 2006, с. 963–984.
  10. ↑ Cayley, 1847, с. 93–96.
  11. ↑ Vazirani, 1989, с. 152—164.
  12. ↑ Jerrum, 1987, с. 121–134.
  13. ↑ Valiant, 2004, с. 306–315.

Литература

Ссылки

  • Больше информации об алгоритме, его истории и примерах можно найти в главе 2 и разделе 5.3.2 диссертации Дмитрия Каменецкого PhD thesis
Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Алгоритм_FKT&oldid=5845420