سلام
یک اشتباه دیگه توی فصل ارضای محدودیت راهیان ارشد که به نظرم اومد. من واقعا نمی‌دونم نویسنده کتاب راهیان چقدر فکر کرده تا تونسته اینطور استدلال کنه که گزینه چهارم درسته (در اثبات صحت کلید اولیه سنجش) اما به نظر من که درست نیست. چون ما تنها یک رنگ داریم و با یک رنگ هم امکان رنگ‌آمیزی و متمایزسازی سه همسایه نیست، پس بدون شک مسئله غیر قابل حله (با هر هیورستیکی)، خب اینجا می‌خوایم سازگار بودن یا نبودن گراف رو به ازای مقادیر مختلف بررسی کنیم.

تصویر سوال:

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


تعریف K-Consistenxy یا سازگاری K :
گوییم یک مسئله ارضای محدودیت (CSP) در سازگاری K است، اگر برای هر K-1 متغیر از آن CSP و برای هر انتساب سازگار از آن‌ها بتوان یک مقدار سازگار به متغیر Kاُم نسبت داد.

گزینه اول (K=0): غلط - این گزینه یعنی به هیچ وجه نتونیم سازگاری هیچ گرهی رو حتی به صورت منفرد تضمین کنیم، ولی ما یک رنگ داریم!

گزینه دوم (K=1): درست - این گزینه یعنی صرفا با K=1 می‌تونیم برقراری شرط سازگاری رو تضمین کنیم (یعنی هر گره صرفا با خودش سازگاره)، در واقع به صورت منفرد یک متغیر رو انتخاب می‌کنیم و رنگ می‌کنیم و به بقیه مقداری منتسب نمی‌کنیم، چون رنگ دیگه‌ای نداریم.

گزینه سوم (K=1 و K=2): غلط - بخش اولش درسته، اما بخش دومش (K=2) یعنی وقتی به یک گره یک رنگ منتسب می‌کنیم، بتونیم به گره مجاور هم رنگی رو منتسب کنیم، اما رنگ دومی در کار نیست که این کار رو انجام بدیم، بنابراین به تناقض می‌رسیم.

گزینه چهارم (K=1 و K=3): غلط - بخش اولش درسته، اما بخش دومش (K=3) به همون دلیل گزینه سوم صحیح نیست.

برای اطمینان، یکی از دوستان این سوال رو از استاد هوش پارسه پرسید که ایشون هم نظرش گزینه دوم بود. اگه کسی نظر دیگه‌ای داره حتما بگه تا بررسی کنیم.