مسئله پوشش گروهک

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در نظریهٔ پیچیدگی محاسباتی، پیدا کردن یک پوشش گروهک کمینه، یک مساله NP-کامل نظری گراف است. این مسئله یکی از۲۱ مسئله اصلی ریچارد کاپ است که در آن NP-کامل را در مقاله‌اش "کاهش پذیری درمیان مسائل ترکیبی "در سال ۱۹۷۲ نشان داده بود.

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

کامل بودن NP پوشش گروهک‌ها، به دنبال کاهش از رنگ‌پذیری K گراف می‌آید. برای فهمیدن این موضوع، ابتدا یک نمونه G از گراف ''K'' رنگ پذیری را به گراف G مکمل اش تبدیل کنید. یک دسته بندی از Gبه Kگروهک،سپس با پیدا کردن یک دسته‌بندی ازرئوس G به K مجموعهٔ مستقل ارتباط دارد، هرکدام از این مجموعه‌ها می‌تواند یک رنگ بپذیرند تا یک K رنگ‌پذیری را حاصل کنند.

مسئلهٔ پوشش لبهٔ گروهک مرتبط، مجموعه‌ای از گروهک‌ها را که شامل همهٔ لبه‌هایی از یک گراف داده شده‌است را درنظر می‌گیرد. این مسئله همچنین NP کامل است.

منابع[ویرایش]

  • مشارکت‌کنندگان ویکی‌پدیا، «Clique cover problem»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۲۱ تیر ۱۳۹۱).

.194.