FKT algorithm
فشر-کاسٹلین-ٹیمپرلی (ایف کے ٹی) الگورتھم، جس کا نام مائیکل فشر، پیٹر کاسٹلین، اور نیویل ٹیمپرلی کے نام پر رکھا گیا ہے، کثیر الجہتی وقت میں پلانر گراف میں کامل ملاپ کی تعداد شمار کرتا ہے۔ عام گراف کے لیے یہی کام #P-مکمل ہے۔ ان ملاپوں کے لیے جن کے کامل ہونے کی ضرورت نہیں ہے، ان کی گنتی #P-مکمل رہتی ہے یہاں تک کہ پلانر گراف کے لیے بھی۔ ایف کے ٹی الگورتھم کا کلیدی خیال یہ ہے کہ اس مسئلے کو گراف کے پلانر ایمبیڈنگ سے حاصل کردہ اسکیو سمیٹرک میٹرکس کے فافین کمپیوٹیشن میں تبدیل کیا جائے۔ اس میٹرکس کے فافین کو پھر معیاری تعیناتی الگورتھم کا استعمال کرتے ہوئے مؤثر طریقے سے شمار کیا جاتا ہے۔ پلانر پرفیکٹ میچنگ کی گنتی کے مسئلے کی جڑیں شماریاتی میکانکس اور کیمسٹری میں ہیں، جہاں اصل سوال یہ تھا: اگر ڈائیٹومک مالیکیولز کو کسی سطح پر جذب کیا جاتا ہے، جس سے ایک ہی پرت بنتی ہے، تو انہیں کتنے طریقوں سے ترتیب دیا جا سکتا ہے؟ پارٹیشن فنکشن ایک اہم مقدار ہے جو توازن میں کسی نظام کی شماریاتی خصوصیات کو انکوڈ کرتی ہے اور پچھلے سوال کا جواب دینے کے لیے استعمال کی جا سکتی ہے۔ تاہم، پارٹیشن فنکشن کو اس کی تعریف سے شمار کرنے کی کوشش کرنا عملی نہیں ہے۔ اس طرح کسی فزیکل سسٹم کو درست طریقے سے حل کرنے کے لیے اس مخصوص فزیکل سسٹم کے لیے پارٹیشن فنکشن کی ایک متبادل شکل تلاش کرنا ہے جو بالکل حساب لگانے کے لیے کافی آسان ہو۔ 1960 کی دہائی کے اوائل میں، بالکل قابل حل کی تعریف سخت نہیں تھی۔ کمپیوٹر سائنس نے کثیر الجہتی وقت کے تعارف کے ساتھ ایک سخت تعریف فراہم کی، جو 1965 کی ہے۔ اسی طرح، اس طرح کے گنتی کے مسئلے کے لیے بالکل حل نہ ہونے کا اشارہ #P-سختی سے مطابقت رکھتا ہے، جس کی تعریف 1979 میں کی گئی تھی۔ غور کرنے کے لیے ایک اور قسم کا جسمانی نظام ڈائمرز پر مشتمل ہے، جو کہ دو ایٹموں والا پولیمر ہے۔ ڈائمر ماڈل گراف کے ڈائمر کورنگ کی تعداد کو شمار کرتا ہے۔ غور کرنے کے لیے ایک اور جسمانی نظام برف کی شکل میں H2O مالیکیولز کا بندھن ہے۔ اسے ایک ڈائریکٹڈ، 3-ریگولر گراف کے طور پر بنایا جا سکتا ہے جہاں ہر سرے پر کناروں کی سمت ایک جیسی نہیں ہو سکتی۔ اس ماڈل کے کتنے کنارے ہیں؟ ڈائمرز پر مشتمل جسمانی نظاموں سے متاثر ہو کر، 1961 میں، پیٹر کاسٹلین اور نیویل ٹیمپرلی اور مائیکل فشر نے آزادانہ طور پر m-by-n مستطیل کے لیے ڈومینو ٹائلنگ کی تعداد دریافت کی۔ یہ m-by-n جالی گراف کے لیے کامل ملاپ کی تعداد کی گنتی کے برابر ہے۔ 1967 تک، کاسٹلین نے اس نتیجے کو تمام پلانر گرافوں میں عام کر دیا تھا۔ الگورتھم کی وضاحت بنیادی بصیرت یہ ہے کہ گراف G کے ملحقہ میٹرکس کے فافین میں ہر غیر صفر اصطلاح ایک کامل مماثلت سے مطابقت رکھتی ہے۔ اس طرح، اگر کوئی فافین میں اصطلاحات کی تمام علامتوں کو سیدھا کرنے کے لیے G کی سمت تلاش کر سکتا ہے (کوئی فرق نہیں + یا-)، تو فافین کی مطلق قیمت صرف G میں کامل ملاپ کی تعداد ہے۔ ایف کے ٹی الگورتھم پلانر گراف G کے لیے ایسا کام کرتا ہے۔ اس سے ملنے والی سمت کو فافین سمت کہا جاتا ہے۔ مان لیں کہ G = (V، E) ملحقہ میٹرکس A کے ساتھ ایک غیر ہدایت شدہ گراف ہے۔ پی ایم (این) کو جوڑوں میں n عناصر کی تقسیم کے مجموعے کے طور پر بیان کریں، پھر جی میں کامل ملاپ کی تعداد کا اس سے گہرا تعلق ہے، ایک این بائی این میٹرکس اے کے لیے فافین ہے جہاں ایس جی این (ایم) پرموٹیشن ایم کی علامت ہے۔ جی کا ایک فافین واقفیت ملحقہ میٹرکس بی کے ساتھ ایک ہدایت شدہ گراف ایچ ہے جس میں پی ایف (بی) = پرفمیچ (جی) ہے۔ 1967 میں، کاسٹلین نے ثابت کیا کہ پلانر گراف میں ایک مؤثر طریقے سے کمپیوٹیبل فافین واقفیت ہے۔ خاص طور پر، پلانر گراف G کے لیے، H کو G کا ایک ہدایت شدہ ورژن ہونے دیں جہاں G کے پلانر ایمبیڈنگ میں ہر چہرے کے لیے کناروں کی ایک عجیب تعداد گھڑی کی سمت پر مبنی ہوتی ہے۔ پھر H G کا ایک فافین واقفیت ہے۔ آخر میں، کسی بھی اسکیو-سمیٹرک میٹرکس A کے لیے، جہاں ڈیٹ (A) A کا تعین کنندہ ہے۔ یہ نتیجہ آرتھر کیلی کی وجہ سے ہے۔ چونکہ تعین کرنے والے مؤثر طریقے سے قابل حساب ہوتے ہیں، اسی طرح پرف میچ (جی) بھی ہے۔ اعلی سطح کی تفصیل G کے ایک پلانر ایمبیڈنگ کا حساب لگائیں۔ ان پٹ گراف G کے ایک پھیلے ہوئے درخت T1 کا حساب لگائیں۔ G میں ہر کنارے کو ایک من مانی سمت دیں جو کہ T1 میں بھی ہے۔ پلانر ایمبیڈنگ کا استعمال ایک (غیر ہدایت شدہ) گراف T2 بنانے کے لیے کریں جس میں G کے دوہری گراف کی طرح ایک ہی ورٹیکس سیٹ ہو۔ دو عمودی کے درمیان T2 میں ایک کنارے بنائیں اگر G میں ان کے متعلقہ چہرے G میں ایک کنارے کا اشتراک کرتے ہیں جو T1 میں نہیں ہے۔ (نوٹ کریں کہ T2 ایک درخت ہے۔) T2 میں ہر پتی v کے لیے (جو کہ جڑ بھی نہیں ہے): فرض کریں کہ e چہرے پر G کا واحد کنارہ ہے جو کہ v سے مطابقت رکھتا ہے جس کی ابھی تک سمت نہیں ہے۔ ای کو ایک سمت اس طرح دیں کہ گھڑی کے لحاظ سے کناروں کی تعداد عجیب ہو۔ T2 سے v کو ہٹا دیں۔ G کے ملحقہ میٹرکس کے فافین کی مطلق قیمت واپس کریں، جو کہ تعین کنندہ کا مربع جڑ ہے۔ عمومییاں ویٹڈ پرفیکٹ میچنگز کا مجموعہ آخری مرحلے میں ملحقہ میٹرکس کے لیے ٹوٹے میٹرکس کا استعمال کرکے بھی شمار کیا جا سکتا ہے۔ کوراتووسکی کے نظریہ میں کہا گیا ہے کہ ایک محدود گراف پلانر ہے اگر اور صرف اس صورت میں جب اس میں K5 (پانچ عمودی حصوں پر مکمل گراف) یا K3,3 (سائز تین کے دو حصوں پر مکمل دو طرفہ گراف) کے لیے کوئی ذیلی گراف ہومومورفک نہ ہو۔ وجے وزیرانی نے ایف کے ٹی الگورتھم کو ان گرافوں میں عام کیا جن میں K3,3 کا ذیلی گراف ہومیومورفک نہیں ہوتا ہے۔ چونکہ عام گراف میں کامل ملاپ کی تعداد کی گنتی #P-مکمل ہے، اس لیے ان پٹ گراف پر کچھ پابندی کی ضرورت ہوتی ہے جب تک کہ FP، P کا فنکشن ورژن، #P کے برابر نہ ہو۔ گنتی ملاپ، جسے ہوسویا انڈیکس کے نام سے جانا جاتا ہے، بھی #P-مکمل ہے یہاں تک کہ پلانر گراف کے لیے بھی۔ ایپلی کیشنز ایف کے ٹی الگورتھم نے میچ گیٹس کے ذریعے پلانر گراف پر ہولوگرافک الگورتھم میں وسیع استعمال دیکھا ہے۔ مثال کے طور پر، اوپر بیان کردہ آئس ماڈل کے پلینر ورژن پر غور کریں، جس کا تکنیکی نام #PL-3-NAE-SAT ہے (جہاں NAE کا مطلب "تمام برابر نہیں" ہے)۔ ویلینٹ نے اس مسئلے کے لیے ایک کثیر الجہتی ٹائم الگورتھم پایا جو میچ گیٹس کا استعمال کرتا ہے۔ حوالہ جات بیرونی روابط مزید تاریخ، معلومات اور مثالیں دمتری کامینیٹسکی کے پی ایچ ڈی تھیسس گراف الگورتھم پلانر گراف کے باب 2 اور سیکشن 5.3.2 میں مل سکتی ہیں۔