کلیک (نظریه گراف)
در ریاضیات و در زمینه نظریه گراف کلیک (به انگلیسی: Clique)، برای گرافی بدون جهت زیرمجموعه‌ای از رئوس که زیرگرافی کامل می‌سازند؛ به سخنی دیگر، هر جفت رأس همسایه بوده و میان هر جفت-رأس در یک کلیک یالی هست. شمار گره‌های یک کلیک اندازهٔ کلیک نامیده می‌شود. گروهک‌ها از مفهوم‌های بنیادی نظریه گراف هستند و کاربرد فراوانی در ریاضی و دانش رایانه دارند. گروهکی که نتوان آن را گستراند کلیک بیشین نامیده می‌شود. به سخنی دیگر، با افزودن هر گره‌ای به این کلیک، دست‌کم یک جفت-گرهٔ ناهمسایه خواهیم داشت و این کلیک زیرمجموعه‌ای از گروهکی بزرگ‌تر نیست. یافتن گروهکی بیشینه برای یک گراف پرسمان کلیک بیشینه نامیده می‌شود. این پرسمان ان‌پی کامل است،[1]
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.
دانش رایانه
برخی پرسمان‌های کلیک عبارتند از:
- یافتن کلیک بیشین.
- فهرست همهٔ گروهک‌های بیشین برای یک گراف.
- یافتن کلیک وزن‌دار بیشینه در گرافی وزن دار.
- یافتن گروهکی بیشینه.
پیوند به بیرون
منابع
- The earlier work by Kuratowski (۱۹۳۰) characterizing گراف مسطحs by forbidden complete and complete bipartite subgraphs was originally phrased in topological rather than graph-theoretic terms.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.