طرز نشستن مهمانان قهر دور میز

Question

می‌خواهیم یک مهمانی با حضور n نفر برگزار کنیم که برخی افراد باهم قهر هستند. چگونه می‌توان این n نفر را طوری دور یک میز گرد نشاند به شکلی که هیچ دو نفر قهر در کنار هم ننشسته باشند.

Comments

@سپیده پرسش اصلی‌تان دقیقا به این شکل بوده‌ است؟ برای نمونه اگر تمام افراد با هم قهر بوده‌باشند اصلا این کار ممکن نیست. احیانا فرض خاصی را در مورد رابطه یا تعداد قهربودن‌ها از قلم نیانداخته‌اید؟

---

سلام.این بخشی از سوال الگوریتم پیشرفته است.با کمک مساله دورهمیلتونی ثابت کنید مساله زیرnp_complete است.

---

@سپیده در این صورت متن پرسش اصلی شما این بوده است که ثابت کنید فلان مسأله از فلان دسته قرار دارد نه اینکه تعداد فلان را در این مسأله پیدا کنید. در نتیجه باید متن پرسش‌تان را ویرایش کنید. همینی که در دیدگاه‌تان نوشتید را باید در متن پرسش اضافه کنید و عنوان را هم تغییر دهید به «... مسأله‌ای زیرِ np-complete است».

Answer 1

این مسئله را می‌توان با استفاده از تانسورهای دو بعدی حل کرد. فرض کنید ماتریس$ A $یک ماتریس دو بعدی باشد که در سطر $i$ و ستون$ j $آن، مقدار $1 $قرار داده شده است اگر نفر $i$ و$ j با$ هم قهر باشند و در غیر این صورت، مقدار$ 0$ قرار داده شده است.

حال با استفاده از تانسور $A$، می‌توان یک تانسور دو بعدی$ B $را تعریف کرد که در سطر$ i$ و ستون$ j $آن، مقدار$ 1 $قرار داده شده است اگر نفر $i$ و $j$ با هم قهر نباشند و در غیر این صورت، مقدار $0$ قرار داده شده است.

حال با استفاده از تانسو$ر B$، می‌توان یک تانسور دو بعدی$ C $را تعریف کرد که در سطر$ i $و ستون$ j$ آن، مقدار$ 1$ قرار داده شده است اگر نفر$ i $و$ j$ در کنار هم ننشسته باشند و در غیر این صورت، مقدار$ 0 $قرار داده شده است.

حال با استفاده از تانسور$ C$، می‌توان یک تانسور دو بعدی$ D $را تعریف کرد که در سطر$ i$ و ستون$ j$ آن، مقدار$ 1$ قرار داده شده است اگر نفر i و j در جایگاه‌های متفاوتی نشسته باشند و در غیر این صورت، مقدار $0$ قرار داده شده است.

حال با استفاده از تانسور$ D$، می‌توان یک تانسور دو بعدی $E$ را تعریف کرد که در سطر$ i $و ستون$ j$ آن، مقدار$ 1$ قرار داده شده است اگر نفر $i $در جایگاه$ j-1$، نفر $j$ در جایگاه$ i-1 $و سایر افراد در جایگاه‌های متفاوتی نشسته باشند و در غیر این صورت، مقدار $0 $قرار داده شده است.

حال با استفاده از تانسور E، می‌توان$ n $نفر را به شکلی دور یک میز گرد نشاند که هیچ دو نفر قهر در کنار هم ننشسته باشند.