ФКТ алгоритам

С Википедије, слободне енциклопедије

ФКТ алгоритам, назван по Фишеру, Кастелину и Темперлију, рачуна број савршених упаривања планарног графа у полиномијалном времену. Овај исти задатак је #П-комплетан и за остале графове. Рачунањем броја уређењих парова, чак и за планарне графове такође је #П-комплетно. Кључна идеја је да конвертује проблем у Пфафијан рачунање коц-симетричне матрице изведене од планарног уграђивања графа. Пфафиан матрица је онда компјутеризована ефикасно стандардним алгоритмима детерминанте.

Историја[уреди | уреди извор]

Проблем бројања планарних савршених упаривања има своје корене у статици и хемији, где је оригинално питање: Ако се диатомиски молекули апсорбују на површини, формирајући један слој, на колико начина се они могу организовати?[1] Функција партиционисања је важан квантитет који кодира статистичке особине система у равнотези и може се користити као одговор на претходно питање. Међутим израчунавање функције партиције директном применом њеном дефиниције није практичано. Тако да би се прецизно решио физички систем, неопходно је пронаћи алтернативну форму функције партиционисања за тај појединачни физички систем која је довољно једноставна за прецизно израчунавање.[2] Раних 1960-тих, дефиниција тачно решивог није била ригорозна.[3] Информатика је обезбедила ригорозну дефиницију увођењем полиномијалног времена, које датира од 1965. Слично томе, нотација не баш тачно решивог треба да одговара #П-тескоци, која је дефинисана 1979.

Друга врста физичког система за разматрање је састављена од димера, што је полимер са два атома. Димерни модел рачуна број димерски покрића графа.[4] Други физички систем за разматрање је везивање H2O молекула у облику леда. Ово може бити моделовано као усмерени, 3-регуларни граф код кога оријентације ивица на сваком чвору не могу бити исте. Колико ивица оријентације има овај модел?

Мотивисани физичким системима који укључују димере, 1961, Кастелин[5] и Темперли-Фишер[6] независно налазе број доминског поплочавања за m-са-n правоугаоник. Ово је еквивалентно броју савршених упаривања за m-са-n решеткасти граф. 1967. Кастелин је генерализовао овај резултат за све планарне графове.[7][8]

Алгоритам[уреди | уреди извор]

Објашњење[уреди | уреди извор]

Главни увид је да сваки не-нула рок у Пфаффиану од матрице суседства графа Г одговара саврсеном упаривању. Дакле, ако неко мозе да пронадје полозај Г да усклади све знаке термина у Пфаффиан (без обзира на + или -), онда апсолутна вредност Пфаффиана је само број саврсених упаривања у Г. ФКТ алгоритам ради такав задатак за планаран граф Г.

Нека Г=(V,Е) буде неусмерен граф са матрицом суседства А. Дефиниси ПМ(н) да буде скуп партиција од н елемената у парове, затим број саврсених упаривања у Г је

У тесној вези са овим је Пфаффиан за н x н матрицу А

Где је сгн(M) знак пермутације од M. Пфаффиан оријентација од Г је усмерен граф Х са (1,-1,0) матрицом суседства Б таквом да је пф(б)= ПерфМатцх(Г)[9]. 1967. Кастелеyн је доказао да су планарни графови ефикасно подлозни рацунању пфафиан оријентације. Конкретно, за планаран граф Г, нека Х буде усмерена верзија Г где је непаран број ивица оријентисано у смеру казаљке на сату за свако лице у планарном уградјивању Г. Онда је Х пфафиан оријентација од Г.

На крају, за било коју коц-симетричну матрицу А,

где дет(А) је детерминанта од А. Овај резултат је због Цаyлеyа.[10] Посто су детерминанте ефективно подлозне рацунању, онда је и ПерфМатцх(Г).

Опис високог нивоа[уреди | уреди извор]

Ан еxампле схоwинг хоw тхе ФКТ алгоритхм финдс а Пфаффиан ориентатион.
  1. Израцуна планарну уградњу од Г
  2. Израцуна спаннинг стабло Т1 улазног графа Г
  3. Даје произвољну оријентацију свакој ивици у Г која је такодје у Т1.
  4. Користи планарна уградјивања да створи (неусмерен)граф Т2 са истим скупом цворова као двојни граф од Г
  5. Направи ивицу у Т2 измедју два цвора ако су одговарајуца
  6. За сваки лист в у Т1(то није и корен)
    1. Нека је е усамљена ивица од Г у лице одговара в који јос нема оријентацију
    2. Дај е оријентацију такву да је број ивица оријентисаних у смеру казаљке на сату непаран.
    3. Уклони в од Т2.
  7. Врати апсолутну вредност Пфаффиан од (1,-1,0) матрице суседства Г, која је апсолутна вредност квадратног корена детерминанте.

Генерализација[уреди | уреди извор]

Збир оптерецених саврсених упаривања се мозе израцунати помоцу Тутте матрице за матрицу суседства у последњем кораку.

Куратовски теорема наводи да коначни граф је планаран ако и само ако не садрзи подграф хомеоморфан К5 (потпун граф од пет цворова) или К3,3 (потпун бипартидан граф на две партиције велицине три). Вијаy Вазирани генерализовао је ФКТ алгоритам за графове који не садрзе хомеоморфан подграф за К3,3.[11] Од пребројавања саврсених упаривања у опстем графу је #П-комплетан (#П-цомплете), нека ограницења улазног графа су потребна, осим ако ФП , функцијска верзија П , једнака је #П. Пребројавање парова, која су позната као Хосоја индекс (Хосоyа индеx), су такодје #П-комплетна цак и за планарне графове.

Апликације[уреди | уреди извор]

ФКТ алгоритам је видео сироку примену у холографским алгоритмима(холограпхиц алгоритхм) за планарне графове преко упаривања(матцхгатес).[3] На пример, размотрите планарану верзију леденог модела горе наведеног, која има техницко име #ПЛ-3-НАЕ-САТ (где НАЕ знаци "" нису сви исти""). Валиант је насао полиномијално временски алгоритам за овај проблем, који користи упаривања.[12]

Референце[уреди | уреди извор]

  1. ^ Хаyес, Бриан (2008), „Аццидентал Алгоритхмс”, Америцан Сциентист 
  2. ^ Баxтер, Р. Ј. (2008) [1982]. Еxацтлy Солвед Моделс ин Статистицал Мецханицс (Тхирд изд.). Довер Публицатионс. стр. 11. ИСБН 978-0-486-46271-4. Архивирано из оригинала 20. 03. 2012. г. Приступљено 31. 05. 2013. 
  3. ^ а б Цаи, Јин-Yи; Лу, Пинyан; Xиа, Мингји (2010). Холограпхиц Алгоритхмс wитх Матцхгатес Цаптуре Прециселy Трацтабле Планар #ЦСП. Фоундатионс оф Цомпутер Сциенце (ФОЦС), 2010 51ст Аннуал ИЕЕЕ Сyмпосиум он. Лас Вегас, НВ, УСА: ИЕЕЕ. арXив:1008.0683 Слободан приступ. 
  4. ^ Кенyон, Рицхард; Окоунков, Андреи (2005). „Wхат ис а Димер?” (ПДФ). АМС. 52 (3): 342—343. 
  5. ^ Кастелеyн, П. W. (1961), „Тхе статистицс оф димерс он а латтице. I. Тхе нумбер оф димер аррангементс он а qуадратиц латтице”, Пхyсица, 27 (12): 1209—1225, дои:10.1016/0031-8914(61)90063-5 
  6. ^ Темперлеy, Х. Н. V.; Фисхер, Мицхаел Е. (1961). „Димер проблем ин статистицал мецханицс-ан еxацт ресулт”. Пхилосопхицал Магазине. 6 (68): 1061—1063. дои:10.1080/14786436108243366. 
  7. ^ Кастелеyн, П. W. (1963). „Димер Статистицс анд Пхасе Транситионс”. Јоурнал оф Матхематицал Пхyсицс. 4 (2): 287—293. дои:10.1063/1.1703953. 
  8. ^ Кастелеyн, П. W. (1967), „Грапх тхеорy анд црyстал пхyсицс”, Ур.: Харарy, Ф., Грапх Тхеорy анд Тхеоретицал Пхyсицс, Неw Yорк: Ацадемиц Пресс, стр. 43—110 
  9. ^ Тхомас, Робин (2006). А сурвеy оф Пфаффиан ориентатионс оф грапхс (ПДФ). Интернатионал Цонгресс оф Матхематицианс. III. Зурицх: Еуропеан Матхематицал Социетy. стр. 963—984. 
  10. ^ Цаyлеy, Артхур (1847). „Сур лес детерминантс гауцхес” [Он скеw детерминантс]. Црелле'с Јоурнал. 38: 93—96. 
  11. ^ Вазирани, Вијаy V. (1988), „НЦ алгоритхмс фор цомпутинг тхе нумбер оф перфецт матцхингс ин К3,3-фрее грапхс анд релатед проблемс”, Проц. 1ст Сцандинавиан Wорксхоп он Алгоритхм Тхеорy (СWАТ '88), Лецтуре Нотес ин Цомпутер Сциенце, 318, Спрингер-Верлаг, стр. 233—242, дои:10.1007/3-540-19487-8_27 
  12. ^ Валиант, Леслие Г. (2004). „Холограпхиц Алгоритхмс (Еxтендед Абстрацт)”. Процеедингс оф тхе 45тх Аннуал ИЕЕЕ Сyмпосиум он Фоундатионс оф Цомпутер Сциенце. ФОЦС'04. Роме, Италy: ИЕЕЕ Цомпутер Социетy. стр. 306—315. ИСБН 978-0-7695-2228-9. дои:10.1109/ФОЦС.2004.34. Архивирано из оригинала|арцхиве-урл= захтева |урл= (помоћ) 13. 03. 2012. г. 

Литература[уреди | уреди извор]

Спољашње везе[уреди | уреди извор]

  • Presentation by Ashley Montanaro about the FKT algorithm
  • More history, information, and examples can be found in chapter 2 and section 5.3.2 of Dmitry Kamenetsky's PhD thesis
Преузето из „https://sr.wikipedia.org/w/index.php?title=FKT_algoritam&oldid=27751432”