الگوریتم FKT

الگوریتم FKT که نام آن از ابتدای نام‌های Fisher, Kasteleyn و Temperley گرفته شده است، الگوریتمی است که به شمارش تعداد تطابق کامل در یک گراف مسطح با زمان چندجمله‌ای می‌پردازد. این کار برای گراف‌های عمومی به صورت P-کامل می‌باشد. شمارش تعداد تطابق، حتی برای گراف‌های مسطح نیز به صورت P-کامل می‌باشد. ایده اصلی، تبدیل مسئله به یک پردازش
از ماتریس متقارن مورب که از جاسازی مسطح گراف به دست آمده است می‌باشد. بدین ترتیب این ماتریس به سرعت از الگوریتم استاندارد دترمینان محاسبه می‌گردد.
تاریخچه
مسئله شمارش تعداد تطابق کامل مسطح، ریشه در مکانیک آماری و شیمی دارد، در آنجا سوال اصلی این بوده است که آیا مولکول‌های دو اتمی که بر روی یک سطح جذب می‌شوند و تشکیل یک لایه می‌دهند به چند طریق می‌توان آن‌ها را مرتب نمود؟
تابع پارتیشن یک کمیت بسیار مهم می‌باشد که ویژگی‌های آماری یک سیستم در حال تعادل را رمز می‌کند و می‌توان از آن برای حل مسئله پیشین استفاده نمود. هرچند که تلاش برای محاسبه تابع پارتیشن از تعریف آن، چندان عملی نیست؛ بنابراین برای حل دقیق یک سیستم فیزیکی باید شکل مشابهی از تابع پارتیشن را برای آن سیستم فیزیکی خاص پیدا کنیم که محاسبه آن به اندازه کافی ساده باشد.
در اوایل ۱۹۶۰، تعریف دقیقا قابل حل، چندان ملموس نبود.
در ۱۹۶۵، علم کامپیوتر یک تعریف جدی با معرفی زمان چندجمله‌ای ارائه نمود. به طور مشابه در سال ۱۹۷۹، تعریف نه چندان دقیق قابل حل که به مسائل P-سختی برمی گردد، ارائه شد.
نوع دیگری از سیستم فیزیکی که قابل بررسی است ترکیبی از دیمرها می‌باشد. دیمرها، پلیمری با دو اتم می‌باشند. مدل دیمر، تعداد پوشش‌های دیمر از یک گراف را می‌شمارد. یک سیستم فیزیکی قابل بررسی دیگر، اتصال مولکول‌های آب H 2 O که تشکیل یخ می‌دهند می‌باشد. این سیستم را می‌توان به عنوان یک گراف جهت دار منظم ۳ تایی که جهت یال‌ها در هر راس آن نمی‌تواند یکسان باشد، مدل نمود. سوال این است که چه تعداد جهت یال در این گراف می‌تواند در این گراف وجود داشته باشد؟
با انگیزه سیستم‌های فیزیکی که دیمرها هم شامل آن‌ها می‌شود در سال ۱۹۶۱، Kasteleyn, Temperley و Fisher هر کدام به طور مستقل تعداد کاشی کاری‌های دومینو را برای یک مستطیل m در n پیدا کردند. این فرمول برابر با شمارش تعداد تطابق کامل برای یک یک گراف شبکه m در n می‌باشد. در ۱۹۶۷، Kasteleyn این نتیجه را برای تمام گراف‌های مسطح گسترش داد.
الگوریتم
شرح
دید کلی این است که هر جمله غیر صفر در Pfaffian از ماتریس مجاورت گراف G با یک تطابق کامل مرتبط است؛ بنابراین اگر جهت گیری‌ای از G پیدا شود که مطابق تمام علائم جملات موجود در Pfaffian باشد (مثبت یا منفی بودن فرقی نمی‌کند)، آنگاه می‌توان گفت قدرمطلق Pfaffian نشان دهنده تعداد تطابق کامل گراف G می‌باشد. الگوریتم FKT این کار را برای یک گراف مسطح G انجام می‌دهد.
فرض کنیم (G = (V, E یک گراف بدون جهت با ماتریس مجاورت A باشد. (PM(n را به عنوان مجموعه‌ای از پارتیشن‌های عناصر n به صورت جفتی تعریف می‌کنیم، سپس تعداد تطابق کامل در G به صورت زیر بدست می‌آید:
فرمول مرتبط به این موضوع، فرمول Pfaffian برای هر ماتریس n در n مانند A می‌باشد:
در نهایت، برای هر ماتریس متقارن مورب A داریم:
که در آن (det(A نشان دهنده دترمینان A می‌باشد. این نتجه از زحمات Cayley می‌باشد. از آنجا که دترمینان به راحتی قابل محاسبه است، فرمول بدست آمده هم قابل محاسبه خواهد بود.
توضیحات سطح بالا
مثالی برای روش پیدا کردن جهات Pfaffian با استفاده از الگوریتم FKT
محاسبه مسطح تعبیه شده G
محاسبه درخت پوشای T1 از گراف ورودی G
به هر یال از G که از T1 نیز می‌باشد یک جهت اختیاری تخصیص می‌دهیم
ساخت یک گراف بدون جهت به نام T2 با مجموعه راس‌های گراف همزاد G با استفاده از مسطح تعبیه شده
ساخت یک یال در T2 که بین دو راس آن در گراف متناظر آن در G یالی اینچنین وجود ندارد (دقت داشته باشید که T2 یک درخت می‌باشد)
برای هر یال v در T2 (که ریشه نیست):
فرض کنید e تنها یال G می‌باشد در مقابل v که هنوز جهتی به آن اختصاص داده نشده است
به e یک جهت اختصاص دهید به گونه‌ای که تعداد یال‌هایی که جهت آن‌ها پاد ساعتگرد می‌باشد، فرد گردد.
یال v را از T2 حذف کنید
قدر مطلق Pfaffian از ماتریس مجاورت (۰و۱-و۱) گراف G را باز گردان، که برابر است با قدر مطلق توان دوم دترمینان.
تعمیم
مجموع تطابق کامل وزن دار را نیز می‌توان با استفاده از ماتریس Tutte برای ماتریس مجاورت در گام نهایی انجام داد.
تئوری Kuratowski اثبات می‌کند که:
یک گراف کامل، مسطح است اگر و فقط اگر شامل هیچ زیر گرافی که با گراف کامل ۵ تایی یا با گراف جفت کامل سه تایی (گرافی جفت کامل با دو بخش با اندازه 3) homeomorphic نباشد.
Vijay Vazirani الگوریتم FKT را برای گراف‌هایی که شامل زیر گراف جفت کامل سه تایی نمی‌شوند گسترش داده است. از آنجا که شمارش تعداد تطابق کامل در یک گراف عمومی P-کامل می‌باشد، محدودیت‌هایی بر روی گراف ورودی باید اعمال شود مگر اینکه FP (نسخه‌ای تابعی از P) برابر با P باشد. شمارش تطابق‌ها، که با نام اندیس Hosoya شناخته می‌شود نیز حتی برای گراف‌های مسطح هم، یک مسئله P-کامل می‌باشد.
کاربردها
الگوریتم FKT کاربرد زیادی در الگوریتم‌های هولوگرافیک بر روی گراف‌های مسطح در میان دروازه‌های انطباق دارد. برای مثال، نسخه مسطح از مدل یخ آورده شده در بالا را در نظر بگیرید که نام تکنیکی آن PL-3-NAE-SAT می‌باشد (که NAE در آن به معنای همه برابر نیستند می‌باشد). Valiant یک الگوریتم زمان چندجمله‌ای برای این مسئله پیدا نموده است که از دروازه‌های انطباق استفاده می‌کند.
منابع و مراجع
لینک‌های مرتبط
Presentation by Ashley Montanaro about the
More history, information, and examples can be found in chapter 2 and section 5.3.2 of Dmitry Kamenetskys