|
مسئلهٔ چک کردن موجودیت خوشه‌ای با اندازهٔ مشخص در یک گراف، در دستهٔ مسائل [[ان‌پی کامل]] (NP-Complete) قرار می‌گیرد، یعنی برای آن هیچ الگوریتم شناخته‌ای که در زمان چندجمله‌ای قابل اجرا باشد وجود ندارد. با این وجود، الگوریتم‌های زیادی برای حل این مسئله و سایر مسائل مربوط به خوشه‌ها مورد مطالعه و بررسی قرار گرفته‌اند.
در گسترهٔ وسیعی از مطالعات و پژوهش‌های علمی از نظریهٔ گراف‌ها و به دنبال آن از خوشه‌ها استفاده می‌شود. برای مثال در علوم اجتماعی محاسباتی برای مدل‌سازی گروه‌های دوستی و انسانی کاربرد فراوان دارد. همچنین در [[بیوانفورماتیک]] و [[شیمی محاسباتی]] نیز توجه زیادی به خوشه‌ها می‌شود.
== خوشه چیست ==
در حوزهٔ ریاضیاتی نظریهٔ گراف‌ها، خوشه یک زیر مجموعه از راس‌های یک گراف (با یال‌های بی‌جهت) است که هر دو راس مجزا در آن به یکدیگر متصل باشند (بین آن‌ها یال موجود باشد). به عبارتی یک خوشه، یک زیرگراف کامل است.
زیرگراف، گرافی است که مجموعهٔ راس‌هایش زیر مجموعهٔ راس‌های گراف مادر باشد و مجموعهٔ یال‌هایش هم زیرمجموعهٔ یال‌های گراف مادر باشد.
گراف کامل گرافی است که بین هر دو راس مجزای آن، یال موجود باشد.
در ادامه، سه تعریف کلیدی و مهم را یادآوری می‌کنیم:
در منابع مختلف، ممکن است از نام‌گذاری‌ها و اصطلاحات متفاوتی استفاده کنند (سعی شده‌است در این صفحه از نام‌گذاری‌ها و اصطلاحاتی استفاده شود که رایج‌تر و تأیید شده‌تر هستند).
اندازهٔ یک خوشه: به تعداد راس‌های حاضر در یک خوشه گفته می‌شود.
خوشهٔ ماکسیمال: خوشه‌ای است که نمی‌توان با افزودن یک راس دیگر به راس‌های حاضر در خوشه، آن را بزرگتر کرد (اندازه‌اش را بیشتر کرد). به عبارتی، راس دیگری وجود ندارد که به همهٔ راس‌های حاضر در خوشه یال داشته باشد.
در یک گراف ممکن است چندین خوشهٔ ماکسیمال داشته باشیم.
بزرگترین خوشه: در یک گراف، بزرگترین خوشه به معنای خوشه‌ای است که بیشترین اندازه را دارد.
درجهٔ یک راس: تعداد یال‌هایی که به یک راس متصل هستند.
از آنجایی که در یک خوشه همهٔ راس‌ها باید به یکدیگر متصل باشند، اگر مجوعه‌ای از راس‌ها به اندازهٔ n موجود باشد، می‌توان گفت در صورتی که درجهٔ همهٔ راس‌های موجود، بزرگتر مساوی با n-1 نباشد، این مجموعه از راس‌ها قطعاً تشکیل یک خوشه نمی‌دهند.
با توجه به این که یک خوشه، یک گراف کامل است، تعداد یال‌های موجود در این گراف باید n(n-1)/2 باشد.
اگر یک خوشه موجود باشد، این خوشه می‌تواند ماکسیمال نباشد، اگر درجهٔ تمام راس‌های آن از n-1 بزرگتر باشد.
== مسائل پیدا کردن خوشه ==
| 