کلیک (نظریه گراف)
گروهک (به انگلیسی: Clique) گرافی بدون جهت درون یک شبکه است که هر جفت گره در آن پاره‌شبکه، همسایه بوده و میان هر جفت-رأس در آن یالی هست.
به عبارتی دیگر، گروهک یک زیر مجموعه از راس‌های یک گراف (با یال‌های بی‌جهت) است که هر دو راس مجزا در آن به یکدیگر متصل باشند (بین آن‌ها یال موجود باشد). گروهک یک زیرگراف تماما متصل است.
معیارها
[ویرایش]در منابع مختلف، ممکن است از نام‌گذاری‌ها و اصطلاحات متفاوتی استفاده کنند (سعی شده‌است در این صفحه از نام‌گذاری‌ها و اصطلاحاتی استفاده شود که رایج‌تر و تأیید شده‌تر هستند).
اندازهٔ گروهک: شمار راس‌های گروهک است.
گروهک بیشینه: گروهکی است که نمی‌توان با افزودن یک راس دیگر به راس‌های حاضر در خوشه، آن را بزرگتر کرد (اندازه‌اش را بیشتر کرد). به عبارتی، راس دیگری وجود ندارد که به همهٔ راس‌های حاضر در گروهک یال داشته باشد. در یک گراف ممکن است چندین گروهک ماکسیمال داشته باشیم.
بزرگترین گروهک: گروهکی است که بیشترین اندازه را دارد.
درجهٔ یک راس: تعداد یال‌هایی که به یک راس متصل هستند.
از آنجایی که در یک گروهک همهٔ راس‌ها باید به یکدیگر متصل باشند، اگر مجوعه‌ای از راس‌ها به اندازهٔ n موجود باشد، می‌توان گفت در صورتی که درجهٔ همهٔ راس‌های موجود، بزرگتر مساوی با n-1 نباشد، این مجموعه از راس‌ها قطعاً تشکیل یک گروهک نمی‌دهند.
با توجه به این که یک گروهک، یک گراف کامل است، تعداد یال‌های موجود در این گراف باید n(n-1)/2 باشد.
اگر یک گروهک موجود باشد، این گروهک می‌تواند ماکسیمال نباشد، اگر درجهٔ تمام راس‌های آن از n-1 بزرگتر باشد.
گروهک بیشین
[ویرایش]گروهکی که نتوان آن را گستراند گروهک بیشین نامیده می‌شود. به سخنی دیگر، با افزودن هر گره‌ای به این گروهک، دست‌کم یک جفت-گرهٔ ناهمسایه خواهیم داشت و این گروهک زیرمجموعه‌ای از گروهکی بزرگتر نیست. یافتن گروهکی بیشینه برای یک گراف پرسمان گروهک بیشینه نامیده می‌شود. این پرسمان ان‌پی کامل است.[۱]
دانش رایانه
[ویرایش]برخی پرسمان‌های گروهک عبارتند از:
- یافتن گروهک بیشین.
- فهرست همهٔ گروهک‌های بیشین برای یک گراف.
- یافتن گروهک وزن‌دار بیشینه در گرافی وزن دار.
- یافتن گروهکی بیشینه.
پیوند به بیرون
[ویرایش]منابع
[ویرایش]- ↑ The earlier work by (Kuratowski ۱۹۳۰) characterizing گراف مسطحs by forbidden complete and complete bipartite subgraphs was originally phrased in topological rather than graph-theoretic terms.