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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
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.

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

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

نوشتار اصلی: مسئله گروهک

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

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

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

منابع[ویرایش]

  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.