FKT algorithm
माइकल फिशर, पीटर कास्टेलिन और नेविल टेम्पर्ली के नाम पर नामित फिशर-कास्टेलिन-टेम्पर्ली (एफकेटी) एल्गोरिथ्म, बहुपद समय में एक समतलीय ग्राफ में पूर्ण मिलान की संख्या की गणना करता है। यही कार्य सामान्य ग्राफ के लिए #P-पूर्ण है। उन मिलानों के लिए जिन्हें सही होने की आवश्यकता नहीं है, उन्हें गिनना समतल ग्राफ के लिए भी #P-पूर्ण रहता है। एफ. के. टी. एल्गोरिदम का प्रमुख विचार समस्या को ग्राफ के एक समतलीय एम्बेडिंग से प्राप्त एक तिरछे-सममित मैट्रिक्स की फाफियन गणना में बदलना है। फिर इस मैट्रिक्स के फाफियन की गणना मानक निर्धारक एल्गोरिदम का उपयोग करके कुशलता से की जाती है। प्लेनार परिपूर्ण मिलानों की गिनती की समस्या की जड़ें सांख्यिकीय यांत्रिकी और रसायन विज्ञान में हैं, जहां मूल प्रश्न थाः यदि द्विपरमाण्विक अणुओं को एक सतह पर अवशोषित किया जाता है, तो एक परत बनाई जाती है, तो उन्हें कितने तरीकों से व्यवस्थित किया जा सकता है? विभाजन फलन एक महत्वपूर्ण मात्रा है जो संतुलन में एक प्रणाली के सांख्यिकीय गुणों को कूटबद्ध करती है और इसका उपयोग पिछले प्रश्न का उत्तर देने के लिए किया जा सकता है। हालाँकि, विभाजन फलन को उसकी परिभाषा से गणना करने का प्रयास करना व्यावहारिक नहीं है। इस प्रकार एक भौतिक प्रणाली को सटीक रूप से हल करने के लिए उस विशेष भौतिक प्रणाली के लिए विभाजन कार्य का एक वैकल्पिक रूप खोजना है जो सटीक रूप से गणना करने के लिए पर्याप्त रूप से सरल है। 1960 के दशक की शुरुआत में, सटीक रूप से हल करने योग्य की परिभाषा कठोर नहीं थी। कंप्यूटर विज्ञान ने बहुपद समय की शुरुआत के साथ एक कठोर परिभाषा प्रदान की, जो 1965 की है। इसी तरह, इस तरह की गिनती की समस्या के लिए, ठीक से हल न होने का संकेतन, #P-कठोरता के अनुरूप होना चाहिए, जिसे 1979 में परिभाषित किया गया था। विचार करने के लिए एक अन्य प्रकार की भौतिक प्रणाली डिमर से बनी है, जो दो परमाणुओं के साथ एक बहुलक है। डायमर मॉडल एक ग्राफ के डायमर आवरणों की संख्या को गिनता है। विचार करने के लिए एक अन्य भौतिक प्रणाली बर्फ के रूप में H2O अणुओं का बंधन है। इसे एक निर्देशित, 3-नियमित ग्राफ के रूप में मॉडल किया जा सकता है जहां प्रत्येक शीर्ष पर किनारों का अभिविन्यास समान नहीं हो सकता है। इस मॉडल में कितने किनारे हैं? डाइमर्स से जुड़ी भौतिक प्रणालियों से प्रेरित, 1961 में, पीटर कास्टेलिन और नेविल टेम्पर्ली और माइकल फिशर ने स्वतंत्र रूप से m-by-n आयत के लिए डोमिनोज़ झुकाव की संख्या का पता लगाया। यह m-by-n जाली ग्राफ के लिए सही मिलान की संख्या की गिनती के बराबर है। 1967 तक, कास्टेलिन ने इस परिणाम को सभी समतल ग्राफों में सामान्यीकृत कर दिया था। एल्गोरिथम व्याख्या मुख्य अंतर्दृष्टि यह है कि ग्राफ जी के निकटता मैट्रिक्स के फाफियन में प्रत्येक गैर-शून्य शब्द एक पूर्ण मिलान से मेल खाता है। इस प्रकार, यदि कोई पफाफियन में शब्दों के सभी संकेतों को संरेखित करने के लिए जी का अभिविन्यास पा सकता है (कोई बात नहीं + या-), तो पफाफियन का पूर्ण मूल्य जी में सही मिलान की संख्या है। एफकेटी एल्गोरिथ्म एक समतलीय ग्राफ जी के लिए ऐसा कार्य करता है। यह जो अभिविन्यास पाता है उसे पफाफियन अभिविन्यास कहा जाता है। मान लीजिए कि G = (V, E) निकटता मैट्रिक्स A के साथ एक दिशाहीन ग्राफ है। पी. एम. (एन) को जोड़ों में एन तत्वों के विभाजन के समूह के रूप में परिभाषित करें, फिर जी में पूर्ण मिलान की संख्या इससे निकटता से संबंधित है, एक एन/एन मैट्रिक्स ए के लिए प्फाफियन है जहां एस. जी. एन. (एम) क्रमपरिवर्तन एम का संकेत है। 1967 में, कास्टेलिन ने साबित किया कि समतल ग्राफ में एक कुशलता से कम्प्यूटेबल फाफियन अभिविन्यास है। विशेष रूप से, एक समतलीय ग्राफ जी के लिए, मान लीजिए कि एच जी का एक निर्देशित संस्करण है जहां जी के समतलीय एम्बेडिंग में प्रत्येक चेहरे के लिए किनारों की एक विषम संख्या घड़ी की दिशा में उन्मुख होती है। फिर एच जी का एक फाफियन अभिविन्यास है। अंत में, किसी भी तिरछे-सममित मैट्रिक्स ए के लिए, जहां डेट (ए) ए का निर्धारक है। यह परिणाम आर्थर केली के कारण है। चूँकि निर्धारक कुशलता से संगणनीय होते हैं, इसलिए पर्फमैच (जी) भी है। उच्च-स्तरीय विवरण जी के एक समतल एम्बेडिंग की गणना करें. इनपुट ग्राफ जी के एक फैले हुए ट्री टी1 की गणना करें. जी में प्रत्येक किनारे को एक मनमाना अभिविन्यास दें जो टी1 में भी है। जी के दोहरे ग्राफ के समान शीर्ष सेट के साथ एक (अनिर्दिष्ट) ग्राफ टी2 बनाने के लिए समतल एम्बेडिंग का उपयोग करें। दो शीर्षों के बीच टी2 में एक किनारा बनाएँ यदि जी में उनके संबंधित चेहरे जी में एक किनारे को साझा करते हैं जो टी1 में नहीं है। (ध्यान दें कि टी2 एक पेड़ है।) T2 में प्रत्येक पत्ती v के लिए (जो मूल भी नहीं है): मान लीजिए कि e, v के अनुरूप चेहरे पर G का एकमात्र किनारा है जिसका अभी तक अभिविन्यास नहीं है। ई को ऐसा अभिविन्यास दें कि घड़ी की दिशा में उन्मुख किनारों की संख्या विषम हो। T2 से v निकालें। जी के निकटता मैट्रिक्स के फाफियन का निरपेक्ष मान वापस करें, जो निर्धारक का वर्गमूल है। सामान्यीकरण भारित पूर्ण मिलानों के योग की गणना अंतिम चरण में निकटता मैट्रिक्स के लिए टुटे मैट्रिक्स का उपयोग करके भी की जा सकती है। कुराटोव्स्की की प्रमेय बताती है कि एक परिमित ग्राफ समतल है यदि और केवल तभी जब इसमें K5 (पांच शीर्षों पर पूर्ण ग्राफ) या K3,3 (आकार तीन के दो विभाजनों पर पूर्ण द्विदलीय ग्राफ) के लिए कोई उपग्राफ समरूपता नहीं है। विजय वजीरानी ने एफकेटी एल्गोरिदम को उन ग्राफों के लिए सामान्यीकृत किया जिनमें के3,3 के लिए एक उपग्राफ समरूपता नहीं है। चूंकि एक सामान्य ग्राफ में पूर्ण मिलान की संख्या की गणना #P-पूर्ण है, इसलिए इनपुट ग्राफ पर कुछ प्रतिबंध की आवश्यकता होती है जब तक कि FP, P का कार्य संस्करण, #P के बराबर न हो। मिलान की गणना, जिसे होसोया सूचकांक के रूप में जाना जाता है, समतल ग्राफ के लिए भी #P-पूर्ण है। अनुप्रयोग एफ. के. टी. एल्गोरिदम ने मैचगेट के माध्यम से समतल ग्राफ पर होलोग्राफिक एल्गोरिदम में व्यापक उपयोग देखा है। उदाहरण के लिए, ऊपर उल्लिखित बर्फ मॉडल के समतल संस्करण पर विचार करें, जिसका तकनीकी नाम #PL-3-NAE-SAT है (जहाँ NAE का अर्थ है "सभी समान नहीं")। वैलिएंट ने इस समस्या के लिए एक बहुपद समय एल्गोरिथ्म पाया जो मैचगेट का उपयोग करता है। अधिक इतिहास, जानकारी और उदाहरण दिमित्री कामेनेत्स्की के पीएचडी थीसिस ग्राफ एल्गोरिदम प्लानर ग्राफ के अध्याय 2 और खंड 5.3.2 में पाए जा सकते हैं।