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

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از کلیک (نظریه گراف))
پرش به: ناوبری، جستجو
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) در یک گراف بدون جهت یک زیرمجموعه از رئوس است که هر دو رأس در این زیرمجموعه به وسیله یک لبه (یال) به هم متصل شده‌اند. کلیک‌ها یکی از مفاهیم بنیادی نظریه گراف هستند و در خیلی از مسائل دیگر ریاضی استفاده می‌شود. کلیک‌ها همچنین در علوم رایانه مطالعه می‌شوند، یافتن اینکه آیا کلیکی با اندازه داده شده در یک گراف موجود است (مسئله کلیک) یک مسئله ان‌پی کامل است.[۱]

علوم رایانه[ویرایش]

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

در علوم رایانه، مسئله کلیک یک مسئله محاسباتی یافتن یک کلیک حداکثر یا همه کلیک‌ها در یک گراف داده شده است. jyjtyjh

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

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

  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.