مسائل np کامل گراف¶

بزرگ ترین مجموعه مستقل¶

در این قسمت ثابت می کنیم که مساله آیا گراف یک زیرگراف القایی با \(k\) راس و بدون یال دارد یا خیر، یک مساله تصمیم np کامل است که نشان می دهد محاسبه \(\alpha\) گراف یک مساله np سخت است.

این مساله را به مساله 3sat کاهش می دهیم. به ازای هر جمله در ورودی 3sat سه راس متناظر با اعضای آن عبارت بگذارید و آن ها را به هم وصل کنید. سپس هر دو راسی که یکی متغیر و دیگری نقیض آن است را به هم وصل کنید. گرافی با \(3k\) راس و چند یال ساخته می شود. واضح است که مجموعه مستقل این گراف از \(k\) نمی تواند بیشتر باشد. حال این گراف یک مجموعه مستقل به این اندازه دارد اگر و تنها اگر مساله اصلی بتواند برقرار شود. چون در هر جمله باید حداقل یکی انتخاب شود که مقدارش برابر یک باشد و این اعضای انتخاب شده نمی توانند نقیض هم باشند، پس در گراف اصلی به هم یال ندارند و یک مجموعه مستقل تشکیل می دهند.

لازم به ذکر است که اگر \(k\) یک عدد ثابت باشد (مثلا مساله این باشد که آیا گراف یک مثلث دارد) آنگاه این مساله np کامل نیست و راهی چند جمله ای در زمان \(O(n^k)\) خواهد داشت.

خوشه گراف و مینیمم پوشش راسی¶

بزرگترین خوشه همان بزرگ ترین مجموعه مستقل گراف مکمل است. بنابراین محاسبه \(\omega\) یک گراف هم np سخت است.

کوچک ترین پوشش راسی نیز برعکس بزرگ ترین مجموعه مستقل است. یعنی راس های بیرون بزرگ ترین مجموعه مستقل، کوچک ترین مجموعه پوشش راسی را تشکیل می دهد و بلعکس، پس \(\beta\) گراف هم یک مساله np سخت است.

عدد رنگی¶

مساله تصمیم آیا این گراف ورودی سه بخشی است، یک مساله np کامل است. از این مطلب نتیجه می شود که محاسبه عدد رنگی یا \(\chi\) گراف یک مساله np سخت است.

این مساله را نیز به مساله 3sat کاهش می دهیم. گرافی به این شکل می سازیم:

• سه راس درست، غلط و خنثی می سازیم و آن ها را دو به دو به هم وصل می کنیم. این کار را به این دلیل انجام می دهیم که این رئوس همرنگ نشوند و رنگشان نماینده درستی یا غلطی متغیر باشند.
• به ازای هر متغیر و نقیضش، یک راس می گذاریم و این دو را با یال به هم متصل می کنیم. هم چنین جفت آن ها را به راس خنثی وصل می کنیم تا یکی از دو رنگ درست یا غلط را برگزینند.
• سپس به ازای هر جمله، یک گجت به گراف اضافه می کنیم. گجت گرافی است که سه یال به بیرون و یک راس نهایی دارد. گجت این خاصیت را دارد که اگر راس های بیرونی آن سه یال همرنگ راس غلط باشند، نمی توان راس نهایی را هم رنگ درست قرار داد و در غیر این صورت، می توان این کار را کرد. به ازای هر جمله سه یال بیرونی گجت را به رئوس مربوط به متغیر وصل می کنیم و راس نهایی را به راس خنثی و غلط وصل می کنیم تا رنگ آن مجبور شود همرنگ راس درست باشد.

به این ترتیب جوابی وجود دارد اگر و تنها اگر گراف را بتوان با سه رنگ رنگ آمیزی کرد. تنها نکته ای که باقی می ماند، طراحی گراف گجت است. یک کاندید ممکن برای گراف گجت، گراف زیر است.

که در آن سه یال بیرونی با رنگ آبی و راس نهایی با رنگ قرمز معلوم شده است. صحت این گراف گجت را خودتان می توانید بررسی کنید. شاید برای شما سوال شود که این گراف از کجا ظاهر شد؟ ایده پشت طراحی این گراف این است که هر کدام از مثلث ها مانند یک گیت یای منطقی عمل می کنند و با ترکیب دو گیت دو ورودی، یک گیت سه ورودی به دست آورده ایم.

از فصل های گذشته می دانید که مساله دو رنگ پذیری، بر خلاف مساله سه رنگ پذیری که np کامل است، در زمان خطی به کمک الگوریتم dfs قابل حل است.

مسیر همیلتونی¶

این مساله را به مساله sat کاهش می دهیم. به ازای هر جمله، یک راس و به ازای هر متغیر، یک شکل لوزی مانند قرار می دهیم.

بقیه اثبات در https://www.geeksforgeeks.org/proof-hamiltonian-path-np-complete/

دور همیلتونی¶

این مساله را به مساله مسیر همیلتونی کاهش می دهیم. یک گراف دلخواه ساده را در نظر بگیرید مانند \(G\) سپس به آن یک راس اضافه کنید و آن را به تمام رئوس قبلی متصل کنید. گراف جدید را \(G^{\prime}\) بنامید. هر مسیر همیلتونی در گراف \(G\) را می توان با عبور از راس جدید به یک دور همیلتونی در گراف \(G^{\prime}\) تبدیل کرد و هر دور همیلتونی در گراف \(G^{\prime}\) با حذف راس جدید به یک مسیر همیلتونی در گراف \(G\) تبدیل کرد. بنابراین اگر الگوریتمی داشته باشیم که بتوان با آن دور همیلتونی را تشخیص داد، با اضافه کردن یک راس می توان با آن مسیر همیلتونی را نیز تشخیص داد و چون مسیر همیلتونی np کامل است و دور همیلتونی هم به وضوح جز مسائل np است، دور همیلتونی نیز np کامل است.

بلند ترین مسیر و دور¶

این مسائل مساله تصمیم نیستند ولی چون تمام مسائل کلاس np به آن ها کاهیده می شوند (چون مسیر و دور همیلتونی حالت خاص این دو مساله اند) پس این مسائل np سخت هستند.