FKT algorithm
ફિશર-કેસ્ટલીન-ટેમ્પર્લી (એફકેટી) અલ્ગોરિધમ, જેનું નામ માઈકલ ફિશર, પીટર કેસ્ટલીન અને નેવિલ ટેમ્પર્લીના નામ પરથી રાખવામાં આવ્યું છે, તે બહુપદી સમયમાં સમતલીય આલેખમાં સંપૂર્ણ મેળની સંખ્યાની ગણતરી કરે છે. આ જ કાર્ય સામાન્ય આલેખ માટે #P-પૂર્ણ છે. સંપૂર્ણ હોવાની જરૂર ન હોય તેવા મેળ માટે, સમતલીય આલેખ માટે પણ તેમની ગણતરી #P-પૂર્ણ રહે છે. એફકેટી અલ્ગોરિધમનો મુખ્ય વિચાર એ છે કે સમસ્યાને ગ્રાફના પ્લેનર એમ્બેડિંગમાંથી મેળવેલા સ્ક્યુ-સિમેટ્રિક મેટ્રિક્સની ફાફિયન ગણતરીમાં રૂપાંતરિત કરવી. આ મેટ્રિક્સના ફાફિયનની ગણતરી પછી પ્રમાણભૂત નિર્ધારક અલ્ગોરિધમ્સનો ઉપયોગ કરીને અસરકારક રીતે કરવામાં આવે છે. પ્લેનાર સંપૂર્ણ મેચિંગ્સની ગણતરીની સમસ્યાના મૂળ આંકડાકીય મિકેનિક્સ અને રસાયણશાસ્ત્રમાં છે, જ્યાં મૂળ પ્રશ્ન હતોઃ જો ડાયાટોમિક અણુઓ સપાટી પર શોષાય છે, એક સ્તર બનાવે છે, તો તેમને કેટલી રીતે ગોઠવી શકાય? પાર્ટીશન ફંક્શન એ એક મહત્વપૂર્ણ જથ્થો છે જે સંતુલન પર સિસ્ટમના આંકડાકીય ગુણધર્મોને એન્કોડ કરે છે અને તેનો ઉપયોગ અગાઉના પ્રશ્નનો જવાબ આપવા માટે થઈ શકે છે. જો કે, પાર્ટીશન ફંક્શનને તેની વ્યાખ્યામાંથી ગણતરી કરવાનો પ્રયાસ કરવો વ્યવહારુ નથી. આમ ભૌતિક પ્રણાલીને બરાબર ઉકેલવા માટે તે ચોક્કસ ભૌતિક પ્રણાલી માટે પાર્ટીશન કાર્યનું વૈકલ્પિક સ્વરૂપ શોધવું છે જે બરાબર ગણતરી કરવા માટે પૂરતું સરળ છે. 1960 ના દાયકાની શરૂઆતમાં, બરાબર ઉકેલવા યોગ્યની વ્યાખ્યા સખત નહોતી. કોમ્પ્યુટર વિજ્ઞાને બહુપદી સમયની રજૂઆત સાથે સખત વ્યાખ્યા પ્રદાન કરી છે, જે 1965ની છે. તેવી જ રીતે, આ જેવી ગણતરીની સમસ્યા માટે બરાબર ઉકેલી ન શકાય તેવી નોટેશન, #P-કઠોરતાને અનુરૂપ હોવી જોઈએ, જે 1979 માં વ્યાખ્યાયિત કરવામાં આવી હતી. ધ્યાનમાં લેવાની અન્ય પ્રકારની ભૌતિક પ્રણાલી ડાયમરથી બનેલી છે, જે બે અણુઓ સાથેનું પોલિમર છે. ડાયમર મોડેલ ગ્રાફના ડાયમર આવરણની સંખ્યાની ગણતરી કરે છે. ધ્યાનમાં લેવાની અન્ય ભૌતિક પ્રણાલી એ બરફના સ્વરૂપમાં H2O અણુઓનું બંધન છે. આને નિર્દેશિત, 3-નિયમિત આલેખ તરીકે મોડેલિંગ કરી શકાય છે જ્યાં દરેક શિરોબિંદુ પર ધારની દિશા બધા સમાન ન હોઈ શકે. આ મોડેલમાં કેટલી ધાર દિશાઓ છે? ડાઇમર્સ સાથે સંકળાયેલી ભૌતિક પ્રણાલીઓ દ્વારા પ્રેરિત, 1961માં, પીટર કેસ્ટેલિન અને નેવિલ ટેમ્પર્લી અને માઈકલ ફિશર સ્વતંત્ર રીતે m-by-n લંબચોરસ માટે ડોમિનો ટિલિંગની સંખ્યા શોધી કાઢી હતી. આ m-by-n જાળી આલેખ માટે સંપૂર્ણ મેળની સંખ્યાની ગણતરીની સમકક્ષ છે. 1967 સુધીમાં, કેસ્ટેલીને આ પરિણામને તમામ સમતલીય આલેખમાં સામાન્ય બનાવ્યું હતું. અલ્ગોરિધમ સમજૂતી મુખ્ય આંતરદૃષ્ટિ એ છે કે ગ્રાફ G ના નિકટતા મેટ્રિક્સના ફાફિયનમાં દરેક બિન-શૂન્ય પદ સંપૂર્ણ મેળને અનુરૂપ છે. આમ, જો કોઈ વ્યક્તિ પફાફિયનમાં શરતોના તમામ સંકેતોને સંરેખિત કરવા માટે G ની દિશા શોધી શકે છે (કોઈ બાબત + અથવા-), તો પછી પફાફિયનનું નિરપેક્ષ મૂલ્ય G માં માત્ર સંપૂર્ણ મેળની સંખ્યા છે. FKT અલ્ગોરિધમ પ્લેનર ગ્રાફ G માટે આવા કાર્ય કરે છે. તે જે દિશા શોધે છે તેને પફાફિયન દિશા કહેવામાં આવે છે. ધારો કે G = (V, E) એ સંલગ્નતા મેટ્રિક્સ A સાથે દિશાહીન આલેખ છે. પીએમ (એન) ને જોડીમાં n તત્વોના પાર્ટીશનોના સમૂહ તરીકે વ્યાખ્યાયિત કરો, પછી G માં સંપૂર્ણ મેળની સંખ્યા આની સાથે નજીકથી સંબંધિત છે જે n બાય n મેટ્રિક્સ A માટે પ્ફાફિયન છે જ્યાં sgn (M) એ ક્રમચય M ની નિશાની છે. G ની પ્ફાફિયન દિશા એ સંલગ્નતા મેટ્રિક્સ B સાથે નિર્દેશિત આલેખ H છે જેમ કે pf (B) = PerfMatch (G). 1967માં, કેસ્ટેલીને સાબિત કર્યું કે સમતલીય આલેખમાં કાર્યક્ષમ રીતે ગણતરી કરી શકાય તેવી ફાફિયન દિશા હોય છે. ખાસ કરીને, સમતલીય આલેખ G માટે, H એ G નું નિર્દેશિત સંસ્કરણ હોવું જોઈએ જ્યાં G ના સમતલીય એમ્બેડિંગમાં દરેક ચહેરા માટે વિચિત્ર સંખ્યામાં ધાર ઘડિયાળની દિશામાં હોય છે. પછી H એ G ની ફાફિયન દિશા છે. છેવટે, કોઈપણ વક્ર-સમમિતિય મેટ્રિક્સ A માટે, જ્યાં ડેટ (A) એ A નો નિર્ધારક છે. આ પરિણામ આર્થર કેલેને કારણે છે. નિર્ધારકો અસરકારક રીતે ગણતરી કરી શકાય તેવા હોવાથી, તે જ રીતે પર્ફમેચ (જી) પણ છે. ઉચ્ચ-સ્તરનું વર્ણન G ના પ્લેનર એમ્બેડિંગની ગણતરી કરો. ઇનપુટ ગ્રાફ G ના સ્પૅનિંગ ટ્રી T1 ની ગણતરી કરો. G માં દરેક ધારને મનસ્વી દિશા આપો જે T1 માં પણ છે. પ્લાનર એમ્બેડિંગનો ઉપયોગ G ના બેવડા ગ્રાફની જેમ જ શિરોબિંદુ સમૂહ સાથે (દિશાહીન) ગ્રાફ T2 બનાવવા માટે કરો. જો G માં તેમના અનુરૂપ ચહેરાઓ G માં ધાર શેર કરે છે જે T1 માં નથી તો બે શિરોબિંદુઓ વચ્ચે T2 માં ધાર બનાવો. (નોંધ કરો કે T2 એક વૃક્ષ છે.) T2 માં દરેક પાન v માટે (જે મૂળ પણ નથી): ધારો કે e એ v ને અનુરૂપ ચહેરામાં G ની એકમાત્ર ધાર છે જે હજુ સુધી દિશા ધરાવતી નથી. e ને એવી દિશા આપો કે ઘડિયાળ મુજબની કિનારીઓની સંખ્યા વિચિત્ર હોય. T2 માંથી v દૂર કરો. G ના નિકટતા મેટ્રિક્સના પ્ફાફિયનનું નિરપેક્ષ મૂલ્ય પાછું આપો, જે નિર્ધારકનું વર્ગમૂળ છે. સામાન્યીકરણ છેલ્લા પગલામાં સંલગ્નતા મેટ્રિક્સ માટે ટુટ્ટે મેટ્રિક્સનો ઉપયોગ કરીને ભારિત સંપૂર્ણ મેળનો સરવાળો પણ ગણતરી કરી શકાય છે. કુરાટોવ્સ્કીનો પ્રમેય જણાવે છે કે મર્યાદિત આલેખ સમતલ હોય છે જો તેમાં K5 (પાંચ શિરોબિંદુઓ પર સંપૂર્ણ આલેખ) અથવા K3,3 (કદ ત્રણના બે પાર્ટીશનો પર સંપૂર્ણ દ્વિપક્ષી આલેખ) માટે કોઈ સબગ્રાફ હોમોમોર્ફિક ન હોય. વિજય વઝીરાનીએ એફ. કે. ટી. અલ્ગોરિધમને એવા આલેખમાં સામાન્ય બનાવ્યું કે જેમાં કે3,3 માટે સબગ્રાફ હોમોમોર્ફિક ન હોય. સામાન્ય આલેખમાં સંપૂર્ણ મેળની સંખ્યાની ગણતરી #P-પૂર્ણ હોવાથી, ઇનપુટ આલેખ પર કેટલાક પ્રતિબંધ જરૂરી છે સિવાય કે FP, P નું કાર્ય સંસ્કરણ, #P ની બરાબર હોય. ગણતરી મેળ, જે હોસોયા અનુક્રમણિકા તરીકે ઓળખાય છે, તે સમતલ આલેખ માટે પણ #P-પૂર્ણ હોય છે. એપ્લિકેશન્સ એફ. કે. ટી. અલ્ગોરિધમનો મેચગેટ્સ દ્વારા પ્લેનર ગ્રાફ પર હોલોગ્રાફિક અલ્ગોરિધમ્સમાં વ્યાપક ઉપયોગ જોવા મળ્યો છે. ઉદાહરણ તરીકે, ઉપર ઉલ્લેખિત બરફના મોડેલના સમતલીય સંસ્કરણને ધ્યાનમાં લો, જેનું તકનીકી નામ #PL-3-NAE-SAT છે (જ્યાં NAE નો અર્થ "બધા સમાન નથી" થાય છે). વેલિયન્ટે આ સમસ્યા માટે બહુપદી સમય અલ્ગોરિધમ શોધી કાઢ્યું જે મેચગેટનો ઉપયોગ કરે છે. સંદર્ભો બાહ્ય કડીઓ વધુ ઇતિહાસ, માહિતી અને ઉદાહરણો દિમિત્રી કામેનેત્સ્કીના પીએચડી થીસીસ ગ્રાફ અલ્ગોરિધમ્સ પ્લાનર ગ્રાફના પ્રકરણ 2 અને વિભાગ 5.3.2 માં મળી શકે છે.