مسئله بزرگترین خوشه

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