eff. keey. tii algorithm

fisher, castellin mariyu temperly paeru pettabadina eff. keey. tii algorithm, bahupadi samayamlo samathooka graphlo khachitamaina saripolikala sankhyanu lekkistundi. idhe pani saadhaarana graphlaku #p-puurti. khachitamainavigaa undaalsina avasaram laeni matchla kosam, vaatini lekkinchadam planar graphla kosam kooda #p-puurti avutundi. eff. keey. tii algorithm yokka mukhya aalochana emitante, graph yokka planner embedding nundi udbhavinchina vakra-samamita maatruka yokka samasyanu fafian gananagaa marchadam. eee maatrika yokka pfaffian appudu praamaanika nirnayaatmaka algorithamlanu upayoginchi samarthavantamgaa lekkinchabadutundi.
charitra.
samathooka khachitamaina saripolikalanu lekkinche samasya ganaanka yantrasaastram mariyu rasayana saastramlo daani muulaalanu kaligi undhi, ikkada asalu prasna emitante diatomic anuvulu uparitalampai adhishoshanam cheyabadi, oke poranu yerparuchukunte, vaatini enni margallo amarchavacchu? vibhajana function anedi samathoulyamlo unna vyavastha yokka ganaanka lakshanaalanu encode chese oka mukhyamaina parimaanam mariyu munupati prasnaku samadhanam ivvadaaniki upayoginchavacchu. ayithe, vibhajana functionnu daani nirvachanam nundi lekkinchadaaniki prayatninchadam aacharanaatmakamainadi kaadu. anduvalla bhouthika vyavasthanu sarigga parishkarinchadaaniki, aaa nirdishta bhouthika vyavastha kosam vibhajana function yokka pratyaamnaaya roopaanni kanugonadam, idhi khachitamgaa lekkinchadaaniki taginanta sulabham. 1960la praarambhamlo, "sarigga parishkarinchadaginadi" anae nirvachanam kathinamainadi kaadu. computer sains 1965 naati bahupadi samayanni pravesapettadamto kathinamaina nirvachananni andinchindi. adevidhamgaa, ilanti lekkimpu samasyaku "sarigga parishkarinchalenidi" anae sangnaamaanam, sangnaamaanam nirvachinchabadina #p-kaatinyaaniki anugunamgaa undaali.
pariganinchavalasina maroka rakamaina bhouthika vyavastha diamerlatho koodi untundi, idhi rendu anuvulatho kuudina polymer. diamer modal graph yokka diamer coveringla sankhyanu lekkistundi. pariganinchavalasina maroka bhouthika vyavastha manchu roopamlo h2o anuvula bandham. prati sheersham vadda anchula dhorani annee okela undani nirdesita, 3-kramabaddhamaina graphga dheenini roopondinchavacchu. eee namuunaa enni anchu dhoranulanu kaligi undhi?
diamerlatho kuudina bhouthika vyavasthalachae prerepinchabadina, prerepinchabadina, castellin mariyu temperly mariyu fisher swatantramgaa "m"-bye-"n" deerghachaturasram kosam domino tillingla sankhyanu kanugonnaru. idhi "m"-bye-"n" jaalakapu graph kosam khachitamaina saripolikala sankhyanu lekkinchadaaniki samanam. 1967 natiki, castellin eee phalitaanni anni samatala graphlaku saadhaaraneekarinchaaru.
algorithm.
vivarana.
pradhana antardrushti emitante, graph "g" yokka prakkane unna matricks yokka pfaffian looni prati sunna kaani padam khachitamaina saripolikaku anugunamgaa untundi. anduvalla, pfaffian ("+" ledhaa "-" anevi pattimpu ledhu) loe padaala yokka anni sankethaalanu samalekhanam cheyadaaniki "g" yokka dhoranini kanugonagaligite, appudu pfaffian yokka sampoorna viluva kevalam "g" loe khachitamaina matchla sankhya matrame. eff. keey. tii algorithm oka planner graph "zii" kosam atuvanti panini chestundi. adhi kanugonna dhoranini fafian dhorani antaaru.
g" = ("v", "e") anedi prakkane unna matricks "a" thoo daari mallinchani graph gaa undanivvandi. p" ("n") nuu "n" muulakaala vibhajanala samitigaa jatalugaa nirvachinchandi, appudu "g" loe paripuurnata saripolikala sankhya
dheeniki daggari sambandham "n" dwara "n" maatrika "a" kosam pfaffian."
ikkada sgn ("m") anedi kramaparivartana "m" yokka sanketam. g" yokka pfaffian dhorani anedi pf ("b") = perfmatch ("g") vanti prakkane unna matricks "b" thoo kuudina directed graph "h". "h", planner graphlu samarthavantamgaa ganinchadagina fafian dhoranini kaligi unnayani castellin niroopinchaadu. pratyaekamgaa, oka samathooka rekhaachitram "g" kosam, "h" anedi "g" yokka nirdesita samskaranagaa undanivvandi, ikkada "g" yokka samathookam ponduparachabadina prati mukhaniki besi sankhyalo anchulu savyadisalo untaayi. appudu "h" anedi "g" yokka pfaffian dhorani.
chivaraga, edainaa vakra-samamiti maatrika "a" kosam,
ikkada ditt ("eah") anedi "eah" yokka nirnayaadhikaari. eee phalitam kylie kaaranamgaa undhi. nirnayakaalu samarthavantamgaa ganinchadaginavi kabatti, perfmatch ("g") kooda.
saadhaaraneekaranalu.
chivari dasalo prakkane unna matricks kosam tatte matricksnu upayoginchadam dwara kooda waited perfect matchla mottaanni lekkinchavacchu.
kuratovsky siddhaantam ilaa perkondih 
vijay vaziiraanii fkt algorithamnu "k" 3,3 kuu upagraph homeomarphic laeni graphlaku saadhaaraneekarinchaaru. saadhaarana graphlo khachitamaina saripolikala sankhyanu lekkinchadam #p-puurti ayinanduna, p yokka function version ayina fp, #p kii samanam kakapothe input graphpy kontha parimiti avasaram. hosoya suuchika anie piluvabade lekkimpu saripolikalu kooda samatala graphlaku kooda #p-puurti.
applications.
eff. keey. tii. algorithm matchgates dwara planner graphlapy holographic algorithamlalo vistrutamgaa upayoginchabadindi. udaaharanaku, paina perkonna manchu namuunaa yokka samatala samskarananu pariganinchandi, dheeniki saanketika paeru #pl-3-nae-saat (ikkada nae antey "andaruu samanam kaadu"). valient eee samasyaku saripolikalu upayoginche bahupadi samaya algorithamnu kanugonnadu.

