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

در ریاضیات و در زمینه نظریه گراف کلیک (به انگلیسی: 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.

دانش رایانه

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

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

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

  • Weisstein, Eric W. "Clique". MathWorld.
  • Weisstein, Eric W. "Clique Number". MathWorld.

منابع

  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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.