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

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". در مثورلد.
منابعویرایش
- ↑ The earlier work by Kuratowski (۱۹۳۰) characterizing گراف مسطحs by forbidden complete and complete bipartite subgraphs was originally phrased in topological rather than graph-theoretic terms.