کلیک (نظریه گراف)

در منابع مختلف، ممکن است از نام‌گذاری‌ها و اصطلاحات متفاوتی استفاده کنند (سعی شده‌است در این صفحه از نام‌گذاری‌ها و اصطلاحاتی استفاده شود که رایج‌تر و تأیید شده‌تر هستند).

اندازهٔ گروهک: شمار راس‌های گروهک است.

گروهک بیشینه: گروهکی است که نمی‌توان با افزودن یک راس دیگر به راس‌های حاضر در خوشه، آن را بزرگتر کرد (اندازه‌اش را بیشتر کرد). به عبارتی، راس دیگری وجود ندارد که به همهٔ راس‌های حاضر در گروهک یال داشته باشد. در یک گراف ممکن است چندین گروهک ماکسیمال داشته باشیم.

بزرگترین گروهک: گروهکی است که بیشترین اندازه را دارد.

درجهٔ یک راس: تعداد یال‌هایی که به یک راس متصل هستند.

از آنجایی که در یک گروهک همهٔ راس‌ها باید به یکدیگر متصل باشند، اگر مجوعه‌ای از راس‌ها به اندازهٔ n موجود باشد، می‌توان گفت در صورتی که درجهٔ همهٔ راس‌های موجود، بزرگتر مساوی با n-1 نباشد، این مجموعه از راس‌ها قطعاً تشکیل یک گروهک نمی‌دهند.

با توجه به این که یک گروهک، یک گراف کامل است، تعداد یال‌های موجود در این گراف باید n(n-1)/2 باشد.

اگر یک گروهک موجود باشد، این گروهک می‌تواند ماکسیمال نباشد، اگر درجهٔ تمام راس‌های آن از n-1 بزرگتر باشد.

گروهکی که نتوان آن را گستراند گروهک بیشین نامیده می‌شود. به سخنی دیگر، با افزودن هر گره‌ای به این گروهک، دست‌کم یک جفت-گرهٔ ناهمسایه خواهیم داشت و این گروهک زیرمجموعه‌ای از گروهکی بزرگ‌تر نیست. یافتن گروهکی بیشینه برای یک گراف پرسمان گروهک بیشینه نامیده می‌شود. این پرسمان ان‌پی کامل است.

برخی پرسمان‌های گروهک عبارتند از:

• یافتن گروهک بیشین.
• فهرست همهٔ گروهک‌های بیشین برای یک گراف.
• یافتن گروهک وزن‌دار بیشینه در گرافی وزن دار.
• یافتن گروهکی بیشینه.