Русская Википедия:Алгоритм FKT

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

История

Задача подсчёта планарных совершенных паросочетаний берёт свои корни в статистической механике и химии, где первоначальным вопросом был: Если двухатомные молекулы абсорбируются на поверхности, образуя один слой, сколькими способами они могут быть расположеныШаблон:Sfn? Статистическая сумма является важной величиной, которая кодирует статистические свойства системы в состоянии равновесия, и она могла бы быть использована для ответа на предыдущий вопрос. Однако попытка вычислить статистическую сумму исходя из определения мало практична. Тогда точное решение физической системы есть нахождение альтернативной формы статистической суммы для конкретной физической системы, которая достаточно просто вычислима точноШаблон:Sfn. В начале 1960-х определение точно решаемая задача не было строгимШаблон:Sfn и информатика дала точное определение с введением понятия полиномиального времени, которое датируется 1965-м годом. Аналогично, понятие не совсем решаемая задача должно соответствовать Шаблон:Не переведено 5, которая была определена в 1979 году.

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

Заинтересовавшись физическими системами из димеров, в 1961-м году КастеляйнШаблон:Sfn, а также Темперли вместе с ФишеромШаблон:Sfn независимо нашли число замощений костяшками домино для прямоугольника <math>m \times n</math>. Это эквивалентно подсчёту числа совершенных паросочетаний для <math>m \times n</math> решётки. В 1967 году Кастеляйн обобщил этот результат на все планарные графыШаблон:SfnШаблон:Sfn.

Алгоритм

Подход

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

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

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

Тесно связан с этим пфаффиан для <math>n \times n</math> матрицы A

<math>\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)Шаблон:Sfn. В 1967 году Кастеляйн доказал, что планарные графы имеют эффективно вычисляемую пфаффову ориентацию. А именно для планарного графа G пусть H будет ориентированной версией графа G, в котором нечётное число рёбер ориентировано против часовой стрелки для любой грани планарного вложения графа G. Тогда H является пфаффовой ориентацией графа G.

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

<math>\operatorname{pf}(A)^2=\det(A),</math>

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

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

Файл:Pfaffian orientation via FKT algorithm example.gif
Пример, показывающий как алгоритм 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, которое равно квадратному корню из определителя.

Обобщения

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

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

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

Шаблон:Не переведено 5 обобщил алгоритм FKT на графы, которые не содержат подграф, гомеоморфный K3,3Шаблон:Sfn. Поскольку подсчёт числа совершенных паросочетаний в графе общего вида является Шаблон:Не переведено 5 задачей, требуются некоторые ограничения на входной граф если только сложность Шаблон:Не переведено 5, функциональной версии P, не равна #P. Подсчёт паросочетаний, который известен также как индекс Хосойи, также является #P-полной задачей даже для планарных графовШаблон:Sfn.

Приложения

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

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Ссылки

  • Больше информации об алгоритме, его истории и примерах можно найти в главе 2 и разделе 5.3.2 диссертации Дмитрия Каменецкого PhD thesis

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Алгоритм_FKT&oldid=8939940