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

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

A graph with 23 1-vertex cliques (its vertices), 42 2-vertex cliques (its edges), 19 3-vertex cliques (the light and dark blue triangles), and 2 4-vertex cliques (dark blue areas). The six edges not associated with any triangle and the 11 light blue triangles form maximal cliques. The two dark blue 4-cliques are both maximum and maximal, and the clique number of the graph is 4.

دانش رایانهویرایش

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

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

پیوند به بیرونویرایش

  • اریک ویستاین. "Clique". در مث‌ورلد.
  • اریک ویستاین. "Clique Number". در مث‌ورلد.

منابعویرایش

  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.