FKT algorithm
মাইকেল ফিশার, পিটার ক্যাস্টেলিন এবং নেভিল টেম্পারলির নামে নামকরণ করা ফিশার-ক্যাস্টেলিন-টেম্পারলি (এফকেটি) অ্যালগরিদম বহুপদী সময়ে একটি প্ল্যানার গ্রাফে নিখুঁত মিলনের সংখ্যা গণনা করে। এই একই কাজটি সাধারণ গ্রাফের জন্য #P-সম্পূর্ণ। নিখুঁত হওয়ার প্রয়োজন নেই এমন মিলগুলির জন্য, এগুলি গণনা করা #P-এমনকি প্ল্যানার গ্রাফের জন্যও সম্পূর্ণ থাকে। এফকেটি অ্যালগরিদমের মূল ধারণা হল সমস্যাটিকে গ্রাফের প্ল্যানার এম্বেডিং থেকে প্রাপ্ত একটি তির্যক-প্রতিসম ম্যাট্রিক্সের ফাফিয়ান গণনায় রূপান্তর করা। এই ম্যাট্রিক্সের ফাফিয়ান তারপর স্ট্যান্ডার্ড ডিটার্মিনেন্ট অ্যালগরিদম ব্যবহার করে দক্ষতার সাথে গণনা করা হয়। প্ল্যানার নিখুঁত মিলগুলি গণনা করার সমস্যার শিকড় রয়েছে পরিসংখ্যানগত বলবিজ্ঞান এবং রসায়নে, যেখানে মূল প্রশ্নটি ছিলঃ যদি ডায়াটমিক অণুগুলি একটি পৃষ্ঠে শোষিত হয়, একটি একক স্তর গঠন করে, তবে সেগুলি কতগুলি উপায়ে সাজানো যেতে পারে? পার্টিশন ফাংশন একটি গুরুত্বপূর্ণ পরিমাণ যা ভারসাম্যে একটি সিস্টেমের পরিসংখ্যানগত বৈশিষ্ট্যগুলিকে এনকোড করে এবং পূর্ববর্তী প্রশ্নের উত্তর দিতে ব্যবহার করা যেতে পারে। যাইহোক, পার্টিশন ফাংশনকে তার সংজ্ঞা থেকে গণনা করার চেষ্টা করা ব্যবহারিক নয়। সুতরাং একটি ভৌত ব্যবস্থার সঠিক সমাধান হল সেই নির্দিষ্ট ভৌত ব্যবস্থার জন্য পার্টিশন ফাংশনের একটি বিকল্প রূপ খুঁজে বের করা যা সঠিকভাবে গণনা করার জন্য যথেষ্ট সহজ। 1960-এর দশকের গোড়ার দিকে, ঠিক সমাধানযোগ্য সংজ্ঞাটি কঠোর ছিল না। কম্পিউটার বিজ্ঞান বহুপদী সময়ের প্রবর্তনের সাথে একটি কঠোর সংজ্ঞা প্রদান করেছে, যা 1965 সালের। একইভাবে, এই ধরনের একটি গণনা সমস্যার জন্য ঠিক সমাধানযোগ্য নয় এমন স্বরলিপিটি #P-কঠোরতার সাথে সামঞ্জস্যপূর্ণ হওয়া উচিত, যা 1979 সালে সংজ্ঞায়িত করা হয়েছিল। বিবেচনা করার মতো আরেকটি ধরনের ভৌত ব্যবস্থা ডাইমার দ্বারা গঠিত, যা দুটি পরমাণু সহ একটি পলিমার। ডাইমার মডেল একটি গ্রাফের ডাইমার আবরণের সংখ্যা গণনা করে। বিবেচনা করার মতো আরেকটি ভৌত ব্যবস্থা হল বরফের আকারে H2O অণুগুলির বন্ধন। এটি একটি নির্দেশিত, 3-নিয়মিত গ্রাফ হিসাবে মডেল করা যেতে পারে যেখানে প্রতিটি শীর্ষে প্রান্তের অভিযোজন একই হতে পারে না। এই মডেলটির কতগুলি প্রান্তিক অভিমুখ রয়েছে? ডাইমার জড়িত ভৌত ব্যবস্থা দ্বারা অনুপ্রাণিত হয়ে, 1961 সালে, পিটার ক্যাস্টেলিন এবং নেভিল টেম্পারলি এবং মাইকেল ফিশার স্বাধীনভাবে এম-বাই-এন আয়তক্ষেত্রের জন্য ডোমিনো টিলিংয়ের সংখ্যা খুঁজে পান। এটি এম-বাই-এন জাল গ্রাফের জন্য নিখুঁত মিলগুলির সংখ্যা গণনার সমতুল্য। 1967 সালের মধ্যে, ক্যাস্টেলিন এই ফলাফলটিকে সমস্ত সমতলীয় গ্রাফগুলিতে সাধারণীকরণ করেছিলেন। অ্যালগরিদম ব্যাখ্যা মূল অন্তর্দৃষ্টি হল যে গ্রাফ জি-এর সংলগ্ন ম্যাট্রিক্সের ফাফিয়ানের প্রতিটি অ-শূন্য পদ একটি নিখুঁত মিলনের সাথে মিলে যায়। সুতরাং, যদি কেউ ফাফিয়ানের পদগুলির সমস্ত চিহ্নগুলিকে সারিবদ্ধ করার জন্য জি-এর একটি অভিযোজন খুঁজে পায় (কোনও বিষয় + বা-নয়), তবে ফাফিয়ানের পরম মান হল জি-তে নিখুঁত মিলনের সংখ্যা। এফকেটি অ্যালগরিদম একটি প্ল্যানার গ্রাফ জি-এর জন্য এই ধরনের কাজ করে। এটি যে অভিযোজনটি খুঁজে পায় তাকে ফাফিয়ান অভিযোজন বলা হয়। ধরা যাক G = (V, E) সংলগ্ন ম্যাট্রিক্স A সহ একটি অনির্দিষ্ট গ্রাফ। পিএম (এন) কে জোড়ায় এন উপাদানগুলির বিভাজনের সেট হিসাবে সংজ্ঞায়িত করুন, তারপরে জি-তে নিখুঁত মিলনের সংখ্যা এর সাথে ঘনিষ্ঠভাবে সম্পর্কিত একটি এন বাই এন ম্যাট্রিক্স এ-এর জন্য ফাফিয়ান যেখানে এসজিএন (এম) হল ক্রমবর্ধমান এম-এর চিহ্ন। জি-এর এ ফাফিয়ান অভিযোজন হল সংলগ্ন ম্যাট্রিক্স বি সহ একটি নির্দেশিত গ্রাফ এইচ যাতে পিএফ (বি) = পারফম্যাচ (জি) হয়। 1967 সালে, ক্যাস্টেলিন প্রমাণ করেন যে প্ল্যানার গ্রাফগুলির একটি দক্ষতার সাথে গণনাযোগ্য ফাফিয়ান অভিযোজন রয়েছে। বিশেষত, একটি সমতলীয় গ্রাফ জি-এর জন্য, এইচ-কে জি-এর একটি নির্দেশিত সংস্করণ হিসাবে ধরা যাক যেখানে জি-এর সমতলীয় এম্বেডিংয়ে প্রতিটি মুখের জন্য বিজোড় সংখ্যক প্রান্ত ঘড়ির কাঁটার দিকে অবস্থিত। তারপর এইচ হল জি-এর একটি ফাফিয়ান অভিযোজন। অবশেষে, যে কোনও তির্যক-প্রতিসম ম্যাট্রিক্স এ-এর জন্য, যেখানে ডেট (এ) হল এ-এর নির্ধারক। এই ফলাফল আর্থার কেলির কারণে হয়েছে। যেহেতু নির্ধারকগুলি দক্ষতার সাথে গণনাযোগ্য, তাই পারফম্যাচ (জি)। উচ্চ-স্তরের বিবরণ জি-এর একটি প্ল্যানার এম্বেডিং গণনা করুন। ইনপুট গ্রাফ জি-এর একটি স্প্যানিং ট্রি টি1 গণনা করুন। জি-এর প্রতিটি প্রান্তকে একটি নির্বিচারে অভিযোজন দিন যা টি1-এও রয়েছে। জি-এর দ্বৈত গ্রাফের মতো একই শীর্ষ সেট সহ একটি (অনির্দিষ্ট) গ্রাফ টি2 তৈরি করতে প্ল্যানার এম্বেডিং ব্যবহার করুন। দুটি শীর্ষের মধ্যে টি2-এ একটি প্রান্ত তৈরি করুন যদি জি-তে তাদের সংশ্লিষ্ট মুখগুলি জি-তে একটি প্রান্ত ভাগ করে নেয় যা টি1-এ নেই। (লক্ষ্য করুন যে টি2 একটি গাছ।) T2-এর প্রতিটি পাতার জন্য (এটিও মূল নয়): ধরা যাক e হল G-এর মুখের একমাত্র প্রান্ত যা v-এর সাথে সামঞ্জস্যপূর্ণ যার এখনও কোনও অভিযোজন নেই। ই-কে এমন একটি অভিযোজন দিন যাতে ঘড়ির কাঁটার দিকে অবস্থিত প্রান্তের সংখ্যা বিজোড় হয়। T2 থেকে v সরান। জি-এর সংলগ্ন ম্যাট্রিক্সের ফাফিয়ানের পরম মান ফেরত দিন, যা নির্ধারকের বর্গমূল। সাধারণীকরণ শেষ ধাপে সংলগ্ন ম্যাট্রিক্সের জন্য টুটে ম্যাট্রিক্স ব্যবহার করে ওজনযুক্ত নিখুঁত মিলনের যোগফলও গণনা করা যেতে পারে। কুরাটোভস্কির উপপাদ্য বলে যে একটি সসীম গ্রাফ সমতলীয় হয় যদি এবং শুধুমাত্র যদি এতে কে5 (পাঁচটি শীর্ষে সম্পূর্ণ গ্রাফ) বা কে3,3 (আকার তিন-এর দুটি বিভাজনে সম্পূর্ণ দ্বিদলীয় গ্রাফ)-এর কোনও সাবগ্রাফ হোমিওমরফিক না থাকে। বিজয় ভাজিরানি এফকেটি অ্যালগরিদমকে এমন গ্রাফগুলিতে সাধারণীকরণ করেছেন যেখানে কে3,3-এর সাবগ্রাফ হোমিওমরফিক নেই। যেহেতু একটি সাধারণ গ্রাফে নিখুঁত মিলনের সংখ্যা গণনা করা হয় #P-সম্পূর্ণ, তাই ইনপুট গ্রাফের উপর কিছু সীমাবদ্ধতা প্রয়োজন যদি না FP, P এর ফাংশন সংস্করণ, #P এর সমান হয়। গণনা মিলগুলি, যা হোসোয়া সূচক নামে পরিচিত, এমনকি সমতলীয় গ্রাফের জন্যও #P-সম্পূর্ণ হয়। অ্যাপ্লিকেশন এফকেটি অ্যালগরিদম ম্যাচগেটের মাধ্যমে প্ল্যানার গ্রাফগুলিতে হলোগ্রাফিক অ্যালগরিদমগুলিতে ব্যাপক ব্যবহার দেখেছে। উদাহরণস্বরূপ, উপরে উল্লিখিত বরফ মডেলের সমতলীয় সংস্করণটি বিবেচনা করুন, যার প্রযুক্তিগত নাম #PL-3-NAE-SAT (যেখানে NAE মানে "সব সমান নয়")। ভ্যালিয়েন্ট এই সমস্যার জন্য একটি বহুপদী সময় অ্যালগরিদম খুঁজে পেয়েছে যা ম্যাচগেট ব্যবহার করে। তথ্যসূত্র বাইরের লিঙ্ক আরও ইতিহাস, তথ্য এবং উদাহরণ পাওয়া যাবে দিমিত্রি কামেনেটস্কির পিএইচডি থিসিস গ্রাফ অ্যালগরিদম প্ল্যানার গ্রাফের 2য় অধ্যায় এবং 5.3 বিভাগে।