. "En informatique, le probl\u00E8me de la clique est un probl\u00E8me algorithmique qui consiste \u00E0 trouver des cliques (sous-ensembles de sommets d'un graphe tous adjacents les uns aux autres, \u00E9galement appel\u00E9s sous-graphes complets) dans un graphe. Ce probl\u00E8me a plusieurs formulations diff\u00E9rentes selon les cliques et les informations sur les cliques devant \u00EAtre trouv\u00E9es. Les formulations courantes du probl\u00E8me de la clique incluent la recherche d'une clique maximum (une clique avec le plus grand nombre possible de sommets), la recherche d'une clique de poids maximal dans un graphe pond\u00E9r\u00E9, la liste de toutes les cliques maximums et la r\u00E9solution du probl\u00E8me de d\u00E9cision consistant \u00E0 d\u00E9terminer si un graphe contient une clique plus grande qu'une taille donn\u00E9e. Le probl\u00E8me de la clique appara\u00EEt dans la situation r\u00E9elle suivante. Consid\u00E9rons un r\u00E9seau social, o\u00F9 les sommets du graphe repr\u00E9sentent des personnes et les ar\u00EAtes repr\u00E9sentent la connaissance mutuelle entre les personnes. Une clique repr\u00E9sente alors un sous-ensemble de personnes qui se connaissent toutes mutuellement, et des algorithmes pour trouver des cliques peuvent \u00EAtre utilis\u00E9s pour d\u00E9couvrir ces groupes d'amis communs. Outre ses applications aux r\u00E9seaux sociaux, le probl\u00E8me de la clique a \u00E9galement de nombreuses applications en bioinformatique et en chimie num\u00E9rique. La plupart des versions du probl\u00E8me de la clique sont des probl\u00E8mes difficiles. Le probl\u00E8me d\u00E9cisionnel de la clique est NP-complet (l'un des 21 probl\u00E8mes NP-complets de Karp). Le probl\u00E8me de trouver une k-clique est \u00E0 la fois intraitable \u00E0 param\u00E8tre fix\u00E9 (il n'est pas dans la classe de probl\u00E8mes FPT) et est (en). Lister toutes les cliques maximums peut n\u00E9cessiter un temps exponentiel car il existe des graphes avec un nombre de cliques maximums exponentiel en le nombre de sommets. Par cons\u00E9quent, une grande partie de la th\u00E9orie sur le probl\u00E8me de la clique est consacr\u00E9e \u00E0 l'identification de types particuliers de graphes qui admettent des algorithmes plus efficaces, ou \u00E0 l'\u00E9tablissement de la difficult\u00E9 algorithmique du probl\u00E8me g\u00E9n\u00E9ral dans divers mod\u00E8les de calcul. Pour trouver une clique maximum, on peut inspecter tous les sous-ensembles du graphe, mais ce type de recherche exhaustive est trop long pour \u00EAtre utilisable dans des graphes comprenant plus de quelques dizaines de sommets. Bien qu'aucun algorithme de temps polynomial ne soit connu pour ce probl\u00E8me, des algorithmes plus efficaces que la recherche exhaustive sont connus. Par exemple, l'algorithme de Bron-Kerbosch peut \u00EAtre utilis\u00E9 pour lister toutes les cliques maximums, en temps optimal dans le pire cas, et il est \u00E9galement possible de les lister en temps polynomial par clique."@fr . . . . . . . . . . . . . "1093311196"^^ . . . . . . "Em ci\u00EAncia da computa\u00E7\u00E3o, o problema do clique refere-se a qualquer problema que possui como objetivo encontrar subgrafos completos (\"cliques\") em um grafo. Como exemplo, o problema de encontrar conjuntos de n\u00F3s em que todos os elementos est\u00E3o conectados entre si. Problemas que envolvem o clique:"@pt . . . . . "\uD074\uB9AD \uBB38\uC81C"@ko . . . . . . . . . . . . . . . . . . . . . "Problema do clique"@pt . . . . . . . . . . "\u0417\u0430\u0434\u0430\u0447\u0430 \u043E \u043A\u043B\u0438\u043A\u0435"@ru . "In informatica, il problema della cricca si riferisce a uno qualsiasi dei problemi legati alla ricerca di particolari sottografi completi (\"cricche\") in un grafo, cio\u00E8, insiemi di elementi dove ciascuna coppia di elementi \u00E8 connessa. Per esempio, il problema della cricca massima nasce nel seguente scenario del mondo reale. Si consideri una rete sociale, dove i vertici del grafo rappresentano le persone, e gli spigoli del grafo rappresentano le reciproche conoscenze. Per trovare un sottoinsieme pi\u00F9 grande di persone che si conoscono tutte tra di loro, si possono ispezionare sistematicamente tutti i sottoinsiemi, un processo che consuma troppo tempo per essere pratico per reti sociali che comprendano pi\u00F9 di qualche dozzina di persone. Sebbene questa ricerca mediante forza bruta possa essere migliorata da algoritmi pi\u00F9 efficienti, tutti questi algoritmi impiegano un tempo esponenziale per risolvere il problema. Perci\u00F2, gran parte della teoria sul problema della cricca \u00E8 dedicata a identificare tipi speciali di grafo che ammettano algoritmi pi\u00F9 efficienti, o a stabilire la difficolt\u00E0 computazionale del problema generale in vari modelli di computazione. Insieme alle sue applicazioni nelle reti sociali, il problema della cricca ha anche molte applicazioni in bioinformatica e in chimica computazionale. I problemi della cricca includono: \n* trovare la cricca massima (una cricca con il pi\u00F9 grande numero di vertici), \n* trovare una cricca con il peso massimo in un grafo pesato, \n* elencare tutte le cricche massimali (cricche che non possono essere ampliate), \n* risolvere il problema decisionale di verificare se un grafo contiene una cricca pi\u00F9 grande di una data dimensione. Questi problemi sono tutti difficili: il problema decisionale della cricca \u00E8 NP-completo (uno dei 21 problemi NP-completi di Karp), il problema di trovare la cricca massima \u00E8 sia , sia , ed elencare tutte le cricche massimali pu\u00F2 richiedere un tempo esponenziale in quanto esistono grafi con un numero esponenziale di cricche massimali. Nondimeno, ci sono algoritmi per questi problemi che si eseguono in tempo esponenziale o che gestiscono certi grafi di entrata pi\u00F9 specializzati in tempo polinomiale."@it . . . . . . . . . . . "Das Cliquenproblem (mit CLIQUE notiert) ist ein Entscheidungsproblem der Graphentheorie.Das Cliquenproblem ist eines der 21 klassischen NP-vollst\u00E4ndigen Probleme, deren Zugeh\u00F6rigkeit zu dieser Klasse Richard M. Karp 1972 bewies."@de . . "En complejidad computacional, el problema del clique (a veces tambi\u00E9n traducido desde el ingl\u00E9s como problema del clan o problema de la camarilla\u200B), es un problema NP-completo seg\u00FAn la Teor\u00EDa de la complejidad computacional."@es . . "In informatica, il problema della cricca si riferisce a uno qualsiasi dei problemi legati alla ricerca di particolari sottografi completi (\"cricche\") in un grafo, cio\u00E8, insiemi di elementi dove ciascuna coppia di elementi \u00E8 connessa. I problemi della cricca includono:"@it . . . . . . . . . . . "Problem kliki \u2013 jeden z pierwszych zidentyfikowanych problem\u00F3w NP-zupe\u0142nych. Klika w grafie jest zbiorem wierzcho\u0142k\u00F3w, w kt\u00F3rym ka\u017Cda para wierzcho\u0142k\u00F3w jest po\u0142\u0105czona kraw\u0119dzi\u0105, czyli zbiorem, kt\u00F3ry indukuje podgraf b\u0119d\u0105cy grafem pe\u0142nym. Problem kliki polega na stwierdzeniu, czy w danym grafie istnieje klika o podanym rozmiarze k. Maj\u0105c podane wierzcho\u0142ki nale\u017C\u0105ce do takiej kliki, mo\u017Cemy trywialnie stwierdzi\u0107, \u017Ce tworz\u0105 one klik\u0119, dlatego problem ten nale\u017Cy do klasy NP. Odpowiadaj\u0105cy mu problem optymalizacyjny, problem maksymalnej kliki, polega na wskazaniu maksymalnych klik w podanym grafie."@pl . . . . "\u6700\u5927\u30AF\u30EA\u30FC\u30AF\u554F\u984C\uFF08\u3055\u3044\u3060\u3044\u30AF\u30EA\u30FC\u30AF\u3082\u3093\u3060\u3044\uFF09\u306F\u3001\u30B0\u30E9\u30D5\u7406\u8AD6\u306B\u304A\u3044\u3066\u3001\u30B0\u30E9\u30D5\u4E2D\u306E\u30AF\u30EA\u30FC\u30AF\uFF08\u4EFB\u610F\u306E\u4E8C\u9802\u70B9\u9593\u306B\u679D\u304C\u3042\u308B\u3088\u3046\u306A\u9802\u70B9\u96C6\u5408\uFF09\u306E\u4E2D\u3067\u6700\u5927\u306E\u3082\u306E\u3092\u898B\u3064\u3051\u308B\u554F\u984C\u3002NP\u56F0\u96E3\u3067\u3042\u308B\u3053\u3068\u304C\u77E5\u3089\u308C\u3066\u3044\u308B\u3002 \u3053\u306E\u554F\u984C\u306F\u3001\u88DC\u30B0\u30E9\u30D5\u306B\u5BFE\u3059\u308B\u6700\u5927\u72EC\u7ACB\u96C6\u5408\u554F\u984C\u3068\u7B49\u4FA1\u3067\u3042\u308B\u3002 \u8FD1\u4F3C\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u306B\u3064\u3044\u3066\u3082\u7814\u7A76\u3055\u308C\u3066\u3044\u308B\u304C\u3001\u30B0\u30E9\u30D5\u306E\u9802\u70B9\u6570\u3092 n \u3068\u3059\u308B\u3068\u304D\u3001\u8FD1\u4F3C\u5EA6 O(n / (log n)2) \u304C\u9054\u6210\u3055\u308C\u3066\u3044\u308B\u306E\u307F\u3067\u3042\u308B\u3002\u307E\u305F\u3001P = NP \u304C\u6210\u308A\u7ACB\u305F\u306A\u3044\u3068\u304D\u3001\u4EFB\u610F\u306E \u03B5 > 0 \u306B\u3064\u3044\u3066\u3001\u8FD1\u4F3C\u5EA6 n1/2 \u2212 \u03B5 \u306E\u8FD1\u4F3C\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u304C\u5B58\u5728\u3057\u306A\u3044\u3053\u3068\u304C\u793A\u3055\u308C\u3066\u3044\u308B\u3002NP = ZPP \u304C\u6210\u308A\u7ACB\u305F\u306A\u3044\u5834\u5408\u3001\u8FD1\u4F3C\u5EA6 n1 \u2212 \u03B5 \u306E\u8FD1\u4F3C\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u304C\u5B58\u5728\u3057\u306A\u3044\u3053\u3068\u3082\u793A\u3055\u308C\u3066\u3044\u308B\u3002"@ja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . "\u0417\u0430\u0434\u0430\u0447\u0430 \u043E \u043A\u043B\u0438\u043A\u0435 \u043E\u0442\u043D\u043E\u0441\u0438\u0442\u0441\u044F \u043A \u043A\u043B\u0430\u0441\u0441\u0443 NP-\u043F\u043E\u043B\u043D\u044B\u0445 \u0437\u0430\u0434\u0430\u0447 \u0432 \u043E\u0431\u043B\u0430\u0441\u0442\u0438 \u0442\u0435\u043E\u0440\u0438\u0438 \u0433\u0440\u0430\u0444\u043E\u0432. \u0412\u043F\u0435\u0440\u0432\u044B\u0435 \u043E\u043D\u0430 \u0431\u044B\u043B\u0430 \u0441\u0444\u043E\u0440\u043C\u0443\u043B\u0438\u0440\u043E\u0432\u0430\u043D\u0430 \u0432 1972 \u0433\u043E\u0434\u0443 \u0420\u0438\u0447\u0430\u0440\u0434\u043E\u043C \u041A\u0430\u0440\u043F\u043E\u043C. \u041A\u043B\u0438\u043A\u043E\u0439 \u0432 \u043D\u0435\u043E\u0440\u0438\u0435\u043D\u0442\u0438\u0440\u043E\u0432\u0430\u043D\u043D\u043E\u043C \u0433\u0440\u0430\u0444\u0435 \u043D\u0430\u0437\u044B\u0432\u0430\u0435\u0442\u0441\u044F \u043F\u043E\u0434\u043C\u043D\u043E\u0436\u0435\u0441\u0442\u0432\u043E \u0432\u0435\u0440\u0448\u0438\u043D, \u043A\u0430\u0436\u0434\u044B\u0435 \u0434\u0432\u0435 \u0438\u0437 \u043A\u043E\u0442\u043E\u0440\u044B\u0445 \u0441\u043E\u0435\u0434\u0438\u043D\u0435\u043D\u044B \u0440\u0435\u0431\u0440\u043E\u043C \u0433\u0440\u0430\u0444\u0430. \u0418\u043D\u044B\u043C\u0438 \u0441\u043B\u043E\u0432\u0430\u043C\u0438, \u044D\u0442\u043E \u043F\u043E\u043B\u043D\u044B\u0439 \u043F\u043E\u0434\u0433\u0440\u0430\u0444 \u043F\u0435\u0440\u0432\u043E\u043D\u0430\u0447\u0430\u043B\u044C\u043D\u043E\u0433\u043E \u0433\u0440\u0430\u0444\u0430. \u0420\u0430\u0437\u043C\u0435\u0440 \u043A\u043B\u0438\u043A\u0438 \u043E\u043F\u0440\u0435\u0434\u0435\u043B\u044F\u0435\u0442\u0441\u044F \u043A\u0430\u043A \u0447\u0438\u0441\u043B\u043E \u0432\u0435\u0440\u0448\u0438\u043D \u0432 \u043D\u0435\u0439. \u0417\u0430\u0434\u0430\u0447\u0430 \u043E \u043A\u043B\u0438\u043A\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0432 \u0434\u0432\u0443\u0445 \u0432\u0430\u0440\u0438\u0430\u043D\u0442\u0430\u0445: \u0432 \u0437\u0430\u0434\u0430\u0447\u0435 \u0440\u0430\u0441\u043F\u043E\u0437\u043D\u0430\u0432\u0430\u043D\u0438\u044F \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044F \u043E\u043F\u0440\u0435\u0434\u0435\u043B\u0438\u0442\u044C, \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043B\u0438 \u0432 \u0437\u0430\u0434\u0430\u043D\u043D\u043E\u043C \u0433\u0440\u0430\u0444\u0435 G \u043A\u043B\u0438\u043A\u0430 \u0440\u0430\u0437\u043C\u0435\u0440\u0430 k, \u0432 \u0442\u043E \u0432\u0440\u0435\u043C\u044F \u043A\u0430\u043A \u0432 \u0432\u044B\u0447\u0438\u0441\u043B\u0438\u0442\u0435\u043B\u044C\u043D\u043E\u043C \u0432\u0430\u0440\u0438\u0430\u043D\u0442\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044F \u043D\u0430\u0439\u0442\u0438 \u0432 \u0437\u0430\u0434\u0430\u043D\u043D\u043E\u043C \u0433\u0440\u0430\u0444\u0435 G \u043A\u043B\u0438\u043A\u0443 \u043C\u0430\u043A\u0441\u0438\u043C\u0430\u043B\u044C\u043D\u043E\u0433\u043E \u0440\u0430\u0437\u043C\u0435\u0440\u0430."@ru . . "Problem kliki"@pl . . . . . "85275"^^ . . . . "In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique (a clique with the largest possible number of vertices), finding a maximum weight clique in a weighted graph, listing all maximal cliques (cliques that cannot be enlarged), and solving the decision problem of testing whether a graph contains a clique larger than a given size."@en . . . . . . . . . . "Das Cliquenproblem (mit CLIQUE notiert) ist ein Entscheidungsproblem der Graphentheorie.Das Cliquenproblem ist eines der 21 klassischen NP-vollst\u00E4ndigen Probleme, deren Zugeh\u00F6rigkeit zu dieser Klasse Richard M. Karp 1972 bewies."@de . "En informatique, le probl\u00E8me de la clique est un probl\u00E8me algorithmique qui consiste \u00E0 trouver des cliques (sous-ensembles de sommets d'un graphe tous adjacents les uns aux autres, \u00E9galement appel\u00E9s sous-graphes complets) dans un graphe. Ce probl\u00E8me a plusieurs formulations diff\u00E9rentes selon les cliques et les informations sur les cliques devant \u00EAtre trouv\u00E9es. Les formulations courantes du probl\u00E8me de la clique incluent la recherche d'une clique maximum (une clique avec le plus grand nombre possible de sommets), la recherche d'une clique de poids maximal dans un graphe pond\u00E9r\u00E9, la liste de toutes les cliques maximums et la r\u00E9solution du probl\u00E8me de d\u00E9cision consistant \u00E0 d\u00E9terminer si un graphe contient une clique plus grande qu'une taille donn\u00E9e."@fr . . . . . . "Probl\u00E8me de la clique"@fr . . . . "249254"^^ . . . . . . . . . . . . "Problema del clique"@es . . . . . "\u6700\u5927\u30AF\u30EA\u30FC\u30AF\u554F\u984C\uFF08\u3055\u3044\u3060\u3044\u30AF\u30EA\u30FC\u30AF\u3082\u3093\u3060\u3044\uFF09\u306F\u3001\u30B0\u30E9\u30D5\u7406\u8AD6\u306B\u304A\u3044\u3066\u3001\u30B0\u30E9\u30D5\u4E2D\u306E\u30AF\u30EA\u30FC\u30AF\uFF08\u4EFB\u610F\u306E\u4E8C\u9802\u70B9\u9593\u306B\u679D\u304C\u3042\u308B\u3088\u3046\u306A\u9802\u70B9\u96C6\u5408\uFF09\u306E\u4E2D\u3067\u6700\u5927\u306E\u3082\u306E\u3092\u898B\u3064\u3051\u308B\u554F\u984C\u3002NP\u56F0\u96E3\u3067\u3042\u308B\u3053\u3068\u304C\u77E5\u3089\u308C\u3066\u3044\u308B\u3002 \u3053\u306E\u554F\u984C\u306F\u3001\u88DC\u30B0\u30E9\u30D5\u306B\u5BFE\u3059\u308B\u6700\u5927\u72EC\u7ACB\u96C6\u5408\u554F\u984C\u3068\u7B49\u4FA1\u3067\u3042\u308B\u3002 \u8FD1\u4F3C\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u306B\u3064\u3044\u3066\u3082\u7814\u7A76\u3055\u308C\u3066\u3044\u308B\u304C\u3001\u30B0\u30E9\u30D5\u306E\u9802\u70B9\u6570\u3092 n \u3068\u3059\u308B\u3068\u304D\u3001\u8FD1\u4F3C\u5EA6 O(n / (log n)2) \u304C\u9054\u6210\u3055\u308C\u3066\u3044\u308B\u306E\u307F\u3067\u3042\u308B\u3002\u307E\u305F\u3001P = NP \u304C\u6210\u308A\u7ACB\u305F\u306A\u3044\u3068\u304D\u3001\u4EFB\u610F\u306E \u03B5 > 0 \u306B\u3064\u3044\u3066\u3001\u8FD1\u4F3C\u5EA6 n1/2 \u2212 \u03B5 \u306E\u8FD1\u4F3C\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u304C\u5B58\u5728\u3057\u306A\u3044\u3053\u3068\u304C\u793A\u3055\u308C\u3066\u3044\u308B\u3002NP = ZPP \u304C\u6210\u308A\u7ACB\u305F\u306A\u3044\u5834\u5408\u3001\u8FD1\u4F3C\u5EA6 n1 \u2212 \u03B5 \u306E\u8FD1\u4F3C\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u304C\u5B58\u5728\u3057\u306A\u3044\u3053\u3068\u3082\u793A\u3055\u308C\u3066\u3044\u308B\u3002"@ja . . . . . . . . . . . . . "Cliquenproblem"@de . . . "\u0645\u0634\u0643\u0644\u0629 \u0627\u0644\u0645\u062E\u0637\u0637 \u0627\u0644\u0643\u0627\u0645\u0644 \u0636\u0645\u0646 \u0645\u062E\u0637\u0637"@ar . . . . . . . . . . "\u5728\u8A08\u7B97\u8907\u96DC\u5EA6\u7406\u8AD6\u4E2D\uFF0C\u5206\u5718\u554F\u984C\uFF08clique problem\uFF09\u662F\u5716\u8AD6\u4E2D\u7684\u4E00\u500BNP\u5B8C\u5168\uFF08NP-complete\uFF09\u554F\u984C\u3002 \u56E2\uFF08clique\uFF09\u662F\u4E00\u500B\u5716\u4E2D\u5169\u5169\u76F8\u9130\u7684\u4E00\u500B\u9802\u9EDE\u96C6\uFF0C\u6216\u662F\u4E00\u500B\u5B8C\u5168\u5B50\u5716\uFF08complete subgraph\uFF09\uFF0C\u5982\u53F3\u5716\u4E2D\u76841\u30012\u30015\u4E09\u500B\u9802\u9EDE\u3002 \u5206\u56E2\u95EE\u9898\u662F\u554F\u4E00\u500B\u5716\u4E2D\u662F\u5426\u6709\u5927\u5C0F\u662Fk\u4EE5\u4E0A\u7684\u56E2\u3002\u4EFB\u610F\u6311\u51FAk\u500B\u9EDE\uFF0C\u6211\u5011\u53EF\u4EE5\u7C21\u55AE\u7684\u5224\u65B7\u51FA\u9019k\u500B\u9EDE\u662F\u4E0D\u662F\u4E00\u500B\u56E2\uFF0C\u6240\u4EE5\u9019\u500B\u554F\u984C\u5C6C\u65BCNP\u3002 \u8B49\u660E\u9019\u554F\u984C\u662FNP\u5B8C\u5099\uFF0C\u6211\u5011\u53EF\u4EE5\u5F88\u7C21\u55AE\u7684\u5C07(Independent set problem)\u6B78\u7D04\u6210\u9019\u500B\u554F\u984C\u3002\u56E0\u70BA\u5B58\u5728\u4E00\u500B\u5927\u5C0F\u662Fk\u4EE5\u4E0A\u7684\u5206\u5718\uFF0C\u7B49\u50F9\u65BC\u5B83\u7684\u88DC\u5716\u4E2D\u5B58\u5728\u4E00\u500B\u5927\u5C0F\u662Fk\u4EE5\u4E0A\u7684\u7368\u7ACB\u96C6\u3002"@zh . . . . "\u6700\u5927\u30AF\u30EA\u30FC\u30AF\u554F\u984C"@ja . . . . . "Em ci\u00EAncia da computa\u00E7\u00E3o, o problema do clique refere-se a qualquer problema que possui como objetivo encontrar subgrafos completos (\"cliques\") em um grafo. Como exemplo, o problema de encontrar conjuntos de n\u00F3s em que todos os elementos est\u00E3o conectados entre si. Por exemplo, o problema clique surge no cen\u00E1rio seguinte. Considere uma rede social, onde os v\u00E9rtices do grafo representam pessoas, e as arestas representam o conhecimento m\u00FAtuo. Para encontrar um maior subconjunto de pessoas, em que todas conhecem umas as outras, pode-se sistematicamente inspecionar todos os subconjuntos, um processo que \u00E9 muito demorado para ser pr\u00E1tico para as redes sociais, mesmo que pequenas. Embora a pesquisa por for\u00E7a bruta possa ser melhorada atrav\u00E9s de algoritmos mais eficientes, todos estes algoritmos levam tempo exponencial para resolver o problema. Portanto, grande parte da teoria sobre o problema do clique \u00E9 dedicado \u00E0 identifica\u00E7\u00E3o de tipos especiais de gr\u00E1fo que admitem algoritmos mais eficientes, ou a defini\u00E7\u00E3o da dificuldade computacional do problema geral em v\u00E1rios modelos de computa\u00E7\u00E3o. Junto com seus aplicativos em redes sociais , o clique tamb\u00E9m tem muitas aplica\u00E7\u00F5es em bioinform\u00E1tica e qu\u00EDmica computacional. Problemas que envolvem o clique: \n* encontrar o clique m\u00E1ximo (um clique com o maior n\u00FAmero de v\u00E9rtices); \n* encontrar o clique com maior valor em um grafo valorado; \n* listar todos os cliques m\u00E1ximos (cliques que n\u00E3o podem ser ampliados); \n* resolver o problema de decis\u00E3o de testar se um grafo cont\u00E9m um clique maior que um tamanho determinado. Esses problemas s\u00E3o todos dif\u00EDceis: o problema de decis\u00E3o clique \u00E9 NP-completo (um dos 21 problemas NP-Completo de Karp), e listar todos os cliques m\u00E1ximos pode exigir tempo exponencial. No entanto, existem algoritmos para esses problemas que s\u00E3o executados em tempo exponencial ou que lidam com grafos de entrada mais especializados em tempo polinomial."@pt . . . . . . . . . . . "\u0417\u0430\u0434\u0430\u0447\u0430 \u043F\u0440\u043E \u043A\u043B\u0456\u043A\u0443"@uk . . . . . . . . "\u0627\u0644\u0645\u062E\u0637\u0637 \u0627\u0644\u0643\u0627\u0645\u0644 \u0647\u0648 \u0645\u0636\u0644\u0639 \u0643\u0644 \u0631\u0623\u0633\u064A\u0646 \u0641\u064A\u0647 \u0645\u0631\u062A\u0628\u0637\u0627\u0646. \u0648\u0631\u062A\u0628\u0629 \u0627\u0644\u0645\u062E\u0637\u0637 \u0627\u0644\u0643\u0627\u0645\u0644 \u0647\u0648 \u0639\u062F\u062F \u0631\u0624\u0648\u0633\u0647."@ar . . . . . "\u0417\u0430\u0434\u0430\u0447\u0430 \u043E \u043A\u043B\u0438\u043A\u0435 \u043E\u0442\u043D\u043E\u0441\u0438\u0442\u0441\u044F \u043A \u043A\u043B\u0430\u0441\u0441\u0443 NP-\u043F\u043E\u043B\u043D\u044B\u0445 \u0437\u0430\u0434\u0430\u0447 \u0432 \u043E\u0431\u043B\u0430\u0441\u0442\u0438 \u0442\u0435\u043E\u0440\u0438\u0438 \u0433\u0440\u0430\u0444\u043E\u0432. \u0412\u043F\u0435\u0440\u0432\u044B\u0435 \u043E\u043D\u0430 \u0431\u044B\u043B\u0430 \u0441\u0444\u043E\u0440\u043C\u0443\u043B\u0438\u0440\u043E\u0432\u0430\u043D\u0430 \u0432 1972 \u0433\u043E\u0434\u0443 \u0420\u0438\u0447\u0430\u0440\u0434\u043E\u043C \u041A\u0430\u0440\u043F\u043E\u043C. \u041A\u043B\u0438\u043A\u043E\u0439 \u0432 \u043D\u0435\u043E\u0440\u0438\u0435\u043D\u0442\u0438\u0440\u043E\u0432\u0430\u043D\u043D\u043E\u043C \u0433\u0440\u0430\u0444\u0435 \u043D\u0430\u0437\u044B\u0432\u0430\u0435\u0442\u0441\u044F \u043F\u043E\u0434\u043C\u043D\u043E\u0436\u0435\u0441\u0442\u0432\u043E \u0432\u0435\u0440\u0448\u0438\u043D, \u043A\u0430\u0436\u0434\u044B\u0435 \u0434\u0432\u0435 \u0438\u0437 \u043A\u043E\u0442\u043E\u0440\u044B\u0445 \u0441\u043E\u0435\u0434\u0438\u043D\u0435\u043D\u044B \u0440\u0435\u0431\u0440\u043E\u043C \u0433\u0440\u0430\u0444\u0430. \u0418\u043D\u044B\u043C\u0438 \u0441\u043B\u043E\u0432\u0430\u043C\u0438, \u044D\u0442\u043E \u043F\u043E\u043B\u043D\u044B\u0439 \u043F\u043E\u0434\u0433\u0440\u0430\u0444 \u043F\u0435\u0440\u0432\u043E\u043D\u0430\u0447\u0430\u043B\u044C\u043D\u043E\u0433\u043E \u0433\u0440\u0430\u0444\u0430. \u0420\u0430\u0437\u043C\u0435\u0440 \u043A\u043B\u0438\u043A\u0438 \u043E\u043F\u0440\u0435\u0434\u0435\u043B\u044F\u0435\u0442\u0441\u044F \u043A\u0430\u043A \u0447\u0438\u0441\u043B\u043E \u0432\u0435\u0440\u0448\u0438\u043D \u0432 \u043D\u0435\u0439. \u0417\u0430\u0434\u0430\u0447\u0430 \u043E \u043A\u043B\u0438\u043A\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0432 \u0434\u0432\u0443\u0445 \u0432\u0430\u0440\u0438\u0430\u043D\u0442\u0430\u0445: \u0432 \u0437\u0430\u0434\u0430\u0447\u0435 \u0440\u0430\u0441\u043F\u043E\u0437\u043D\u0430\u0432\u0430\u043D\u0438\u044F \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044F \u043E\u043F\u0440\u0435\u0434\u0435\u043B\u0438\u0442\u044C, \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043B\u0438 \u0432 \u0437\u0430\u0434\u0430\u043D\u043D\u043E\u043C \u0433\u0440\u0430\u0444\u0435 G \u043A\u043B\u0438\u043A\u0430 \u0440\u0430\u0437\u043C\u0435\u0440\u0430 k, \u0432 \u0442\u043E \u0432\u0440\u0435\u043C\u044F \u043A\u0430\u043A \u0432 \u0432\u044B\u0447\u0438\u0441\u043B\u0438\u0442\u0435\u043B\u044C\u043D\u043E\u043C \u0432\u0430\u0440\u0438\u0430\u043D\u0442\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044F \u043D\u0430\u0439\u0442\u0438 \u0432 \u0437\u0430\u0434\u0430\u043D\u043D\u043E\u043C \u0433\u0440\u0430\u0444\u0435 G \u043A\u043B\u0438\u043A\u0443 \u043C\u0430\u043A\u0441\u0438\u043C\u0430\u043B\u044C\u043D\u043E\u0433\u043E \u0440\u0430\u0437\u043C\u0435\u0440\u0430."@ru . "\u0417\u0430\u0434\u0430\u0447\u0430 \u043F\u0440\u043E \u043A\u043B\u0456\u043A\u0443 \u0432\u0456\u0434\u043D\u043E\u0441\u0438\u0442\u044C\u0441\u044F \u0434\u043E \u043A\u043B\u0430\u0441\u0443 NP-\u043F\u043E\u0432\u043D\u0438\u0445 \u0437\u0430\u0434\u0430\u0447 \u0432 \u043E\u0431\u043B\u0430\u0441\u0442\u0456 \u0442\u0435\u043E\u0440\u0456\u0457 \u0433\u0440\u0430\u0444\u0456\u0432. \u0412\u043F\u0435\u0440\u0448\u0435 \u0432\u043E\u043D\u0430 \u0431\u0443\u043B\u0430 \u0441\u0444\u043E\u0440\u043C\u0443\u043B\u044C\u043E\u0432\u0430\u043D\u0430 \u0443 1972 \u0440\u043E\u0446\u0456 \u0420\u0456\u0447\u0430\u0440\u0434\u043E\u043C \u041A\u0430\u0440\u043F\u043E\u043C. \u041A\u043B\u0456\u043A\u043E\u044E \u0432 \u043D\u0435\u043E\u0440\u0456\u0454\u043D\u0442\u043E\u0432\u0430\u043D\u043E\u043C\u0443 \u0433\u0440\u0430\u0444\u0456 \u043D\u0430\u0437\u0438\u0432\u0430\u0454\u0442\u044C\u0441\u044F \u043F\u0456\u0434\u043C\u043D\u043E\u0436\u0438\u043D\u0430 \u0432\u0435\u0440\u0448\u0438\u043D, \u043A\u043E\u0436\u043D\u0456 \u0434\u0432\u0456 \u0437 \u044F\u043A\u0438\u0445 \u0437'\u0454\u0434\u043D\u0430\u043D\u0456 \u0440\u0435\u0431\u0440\u043E\u043C \u0433\u0440\u0430\u0444\u0443. \u0406\u043D\u0448\u0438\u043C\u0438 \u0441\u043B\u043E\u0432\u0430\u043C\u0438, \u0446\u0435 \u043F\u043E\u0432\u043D\u0438\u0439 \u043F\u0456\u0434\u0433\u0440\u0430\u0444 \u043F\u0435\u0440\u0432\u0456\u0441\u043D\u043E\u0433\u043E \u0433\u0440\u0430\u0444\u0443. \u0420\u043E\u0437\u043C\u0456\u0440 \u043A\u043B\u0456\u043A\u0438 \u0432\u0438\u0437\u043D\u0430\u0447\u0430\u0454\u0442\u044C\u0441\u044F \u044F\u043A \u0447\u0438\u0441\u043B\u043E \u0432\u0435\u0440\u0448\u0438\u043D \u0432 \u043D\u0456\u0439. \u0417\u0430\u0434\u0430\u0447\u0430 \u043F\u0440\u043E \u043A\u043B\u0456\u043A\u0443 \u0456\u0441\u043D\u0443\u0454 \u0443 \u0434\u0432\u043E\u0445 \u0432\u0430\u0440\u0456\u0430\u043D\u0442\u0430\u0445: \u0443 \u0437\u0430\u0434\u0430\u0447\u0456 \u0440\u043E\u0437\u043F\u0456\u0437\u043D\u0430\u0432\u0430\u043D\u043D\u044F \u043F\u043E\u0442\u0440\u0456\u0431\u043D\u043E \u0432\u0438\u0437\u043D\u0430\u0447\u0438\u0442\u0438, \u0447\u0438 \u0456\u0441\u043D\u0443\u0454 \u0432 \u0437\u0430\u0434\u0430\u043D\u043E\u043C\u0443 \u0433\u0440\u0430\u0444\u0456 G \u043A\u043B\u0456\u043A\u0430 \u0440\u043E\u0437\u043C\u0456\u0440\u0443 k, \u0442\u043E\u0434\u0456 \u044F\u043A \u0432 \u043E\u0431\u0447\u0438\u0441\u043B\u044E\u0432\u0430\u043B\u044C\u043D\u043E\u043C\u0443 \u0432\u0430\u0440\u0456\u0430\u043D\u0442\u0456 \u043F\u043E\u0442\u0440\u0456\u0431\u043D\u043E \u0437\u043D\u0430\u0439\u0442\u0438 \u0432 \u0437\u0430\u0434\u0430\u043D\u043E\u043C\u0443 \u0433\u0440\u0430\u0444\u0456 G \u043A\u043B\u0456\u043A\u0443 \u043C\u0430\u043A\u0441\u0438\u043C\u0430\u043B\u044C\u043D\u043E\u0433\u043E \u0440\u043E\u0437\u043C\u0456\u0440\u0443 \u0430\u0431\u043E \u0432\u0441\u0456 \u043C\u0430\u043A\u0441\u0438\u043C\u0430\u043B\u044C\u043D\u0456 \u043A\u043B\u0456\u043A\u0438 (\u0442\u0430\u043A\u0456, \u0449\u043E \u043D\u0435 \u043C\u043E\u0436\u043D\u0430 \u0437\u0431\u0456\u043B\u044C\u0448\u0438\u0442\u0438)."@uk . . . "\uD074\uB9AD \uBB38\uC81C (clique problem)\uB294 NP\uC644\uC804\uC778 \uADF8\uB798\uD504 \uC774\uB860\uC5D0 \uB4F1\uC7A5\uD558\uB294 \uBB38\uC81C\uC774\uB2E4. \uC774 \uBB38\uC81C\uB294 \uB9AC\uCC98\uB4DC \uCE74\uD504\uAC00 1972\uB144 \uB17C\uBB38\uC5D0\uC11C NP\uC644\uC804\uC784\uC744 \uC99D\uBA85\uD55C 21\uBB38\uC81C \uC911\uC758 \uD558\uB098\uC77C \uBFD0\uB9CC \uC544\uB2C8\uB77C, NP\uC644\uC804 \uBB38\uC81C \uC774\uB860\uC744 \uC18C\uAC1C\uD55C \uCFE1\uC758 \uB17C\uBB38\uC5D0\uC11C\uB3C4 \uC5B8\uAE09\uB41C \uC720\uBA85\uD55C \uBB38\uC81C\uC774\uB2E4. \uADF8\uB798\uD504\uC758 \uD074\uB9AD(clique)\uC774\uB780 \uBD80\uBD84\uADF8\uB798\uD504\uC774\uBA74\uC11C \uADF8\uB798\uD504\uC758 \uC784\uC758\uC758 \uB450 \uB178\uB4DC\uAC00 \uC11C\uB85C \uC5F0\uACB0\uB41C \uAC83\uC73C\uB85C \uC815\uC758\uB41C\uB2E4. \uC989, \uC644\uC804 \uADF8\uB798\uD504\uC778 \uBD80\uBD84\uADF8\uB798\uD504\uB97C \uD074\uB9AD\uC774\uB77C \uD55C\uB2E4. \uC624\uB978\uCABD \uADF8\uB9BC\uC5D0\uC11C \uB178\uB4DC 1, 2, 5\uB85C \uC774\uB8E8\uC5B4\uC9C4 \uBD80\uBD84\uADF8\uB798\uD504\uB294 \uD074\uB9AD\uC774 \uB41C\uB2E4. \uC65C\uB0D0\uD558\uBA74, \uAC01 \uB178\uB4DC\uAC00 \uBAA8\uB4E0 \uB098\uBA38\uC9C0 \uB178\uB4DC\uC640 \uC5F0\uACB0\uB418\uC5B4 \uC788\uAE30 \uB54C\uBB38\uC774\uB2E4. \uBC18\uBA74 2, 5, 3\uC73C\uB85C \uC774\uB8E8\uC5B4\uC9C4 \uADF8\uB798\uD504\uB97C \uBCF4\uBA74, 5\uC640 3\uC774 \uC5F0\uACB0\uB418\uC5B4 \uC788\uC9C0 \uC54A\uC544 \uD074\uB9AD\uC774 \uB418\uC9C0 \uBABB\uD55C\uB2E4."@ko . . . . . . "\u5206\u5718\u554F\u984C"@zh . . . . . . . . . . . . . . . . . . . . . "\u5728\u8A08\u7B97\u8907\u96DC\u5EA6\u7406\u8AD6\u4E2D\uFF0C\u5206\u5718\u554F\u984C\uFF08clique problem\uFF09\u662F\u5716\u8AD6\u4E2D\u7684\u4E00\u500BNP\u5B8C\u5168\uFF08NP-complete\uFF09\u554F\u984C\u3002 \u56E2\uFF08clique\uFF09\u662F\u4E00\u500B\u5716\u4E2D\u5169\u5169\u76F8\u9130\u7684\u4E00\u500B\u9802\u9EDE\u96C6\uFF0C\u6216\u662F\u4E00\u500B\u5B8C\u5168\u5B50\u5716\uFF08complete subgraph\uFF09\uFF0C\u5982\u53F3\u5716\u4E2D\u76841\u30012\u30015\u4E09\u500B\u9802\u9EDE\u3002 \u5206\u56E2\u95EE\u9898\u662F\u554F\u4E00\u500B\u5716\u4E2D\u662F\u5426\u6709\u5927\u5C0F\u662Fk\u4EE5\u4E0A\u7684\u56E2\u3002\u4EFB\u610F\u6311\u51FAk\u500B\u9EDE\uFF0C\u6211\u5011\u53EF\u4EE5\u7C21\u55AE\u7684\u5224\u65B7\u51FA\u9019k\u500B\u9EDE\u662F\u4E0D\u662F\u4E00\u500B\u56E2\uFF0C\u6240\u4EE5\u9019\u500B\u554F\u984C\u5C6C\u65BCNP\u3002 \u8B49\u660E\u9019\u554F\u984C\u662FNP\u5B8C\u5099\uFF0C\u6211\u5011\u53EF\u4EE5\u5F88\u7C21\u55AE\u7684\u5C07(Independent set problem)\u6B78\u7D04\u6210\u9019\u500B\u554F\u984C\u3002\u56E0\u70BA\u5B58\u5728\u4E00\u500B\u5927\u5C0F\u662Fk\u4EE5\u4E0A\u7684\u5206\u5718\uFF0C\u7B49\u50F9\u65BC\u5B83\u7684\u88DC\u5716\u4E2D\u5B58\u5728\u4E00\u500B\u5927\u5C0F\u662Fk\u4EE5\u4E0A\u7684\u7368\u7ACB\u96C6\u3002"@zh . . . . . "Problem kliki \u2013 jeden z pierwszych zidentyfikowanych problem\u00F3w NP-zupe\u0142nych. Klika w grafie jest zbiorem wierzcho\u0142k\u00F3w, w kt\u00F3rym ka\u017Cda para wierzcho\u0142k\u00F3w jest po\u0142\u0105czona kraw\u0119dzi\u0105, czyli zbiorem, kt\u00F3ry indukuje podgraf b\u0119d\u0105cy grafem pe\u0142nym. Problem kliki polega na stwierdzeniu, czy w danym grafie istnieje klika o podanym rozmiarze k. Maj\u0105c podane wierzcho\u0142ki nale\u017C\u0105ce do takiej kliki, mo\u017Cemy trywialnie stwierdzi\u0107, \u017Ce tworz\u0105 one klik\u0119, dlatego problem ten nale\u017Cy do klasy NP. Odpowiadaj\u0105cy mu problem optymalizacyjny, problem maksymalnej kliki, polega na wskazaniu maksymalnych klik w podanym grafie. NP-zupe\u0142no\u015B\u0107 tego problemu wynika \u0142atwo z NP-zupe\u0142no\u015Bci problemu zbioru niezale\u017Cnego, poniewa\u017C w grafie istnieje klika o rozmiarze k wtedy i tylko wtedy, gdy w dope\u0142nieniu grafu istnieje zbi\u00F3r niezale\u017Cny o rozmiarze k."@pl . . . . . "\u0417\u0430\u0434\u0430\u0447\u0430 \u043F\u0440\u043E \u043A\u043B\u0456\u043A\u0443 \u0432\u0456\u0434\u043D\u043E\u0441\u0438\u0442\u044C\u0441\u044F \u0434\u043E \u043A\u043B\u0430\u0441\u0443 NP-\u043F\u043E\u0432\u043D\u0438\u0445 \u0437\u0430\u0434\u0430\u0447 \u0432 \u043E\u0431\u043B\u0430\u0441\u0442\u0456 \u0442\u0435\u043E\u0440\u0456\u0457 \u0433\u0440\u0430\u0444\u0456\u0432. \u0412\u043F\u0435\u0440\u0448\u0435 \u0432\u043E\u043D\u0430 \u0431\u0443\u043B\u0430 \u0441\u0444\u043E\u0440\u043C\u0443\u043B\u044C\u043E\u0432\u0430\u043D\u0430 \u0443 1972 \u0440\u043E\u0446\u0456 \u0420\u0456\u0447\u0430\u0440\u0434\u043E\u043C \u041A\u0430\u0440\u043F\u043E\u043C. \u041A\u043B\u0456\u043A\u043E\u044E \u0432 \u043D\u0435\u043E\u0440\u0456\u0454\u043D\u0442\u043E\u0432\u0430\u043D\u043E\u043C\u0443 \u0433\u0440\u0430\u0444\u0456 \u043D\u0430\u0437\u0438\u0432\u0430\u0454\u0442\u044C\u0441\u044F \u043F\u0456\u0434\u043C\u043D\u043E\u0436\u0438\u043D\u0430 \u0432\u0435\u0440\u0448\u0438\u043D, \u043A\u043E\u0436\u043D\u0456 \u0434\u0432\u0456 \u0437 \u044F\u043A\u0438\u0445 \u0437'\u0454\u0434\u043D\u0430\u043D\u0456 \u0440\u0435\u0431\u0440\u043E\u043C \u0433\u0440\u0430\u0444\u0443. \u0406\u043D\u0448\u0438\u043C\u0438 \u0441\u043B\u043E\u0432\u0430\u043C\u0438, \u0446\u0435 \u043F\u043E\u0432\u043D\u0438\u0439 \u043F\u0456\u0434\u0433\u0440\u0430\u0444 \u043F\u0435\u0440\u0432\u0456\u0441\u043D\u043E\u0433\u043E \u0433\u0440\u0430\u0444\u0443. \u0420\u043E\u0437\u043C\u0456\u0440 \u043A\u043B\u0456\u043A\u0438 \u0432\u0438\u0437\u043D\u0430\u0447\u0430\u0454\u0442\u044C\u0441\u044F \u044F\u043A \u0447\u0438\u0441\u043B\u043E \u0432\u0435\u0440\u0448\u0438\u043D \u0432 \u043D\u0456\u0439. \u0417\u0430\u0434\u0430\u0447\u0430 \u043F\u0440\u043E \u043A\u043B\u0456\u043A\u0443 \u0456\u0441\u043D\u0443\u0454 \u0443 \u0434\u0432\u043E\u0445 \u0432\u0430\u0440\u0456\u0430\u043D\u0442\u0430\u0445: \u0443 \u0437\u0430\u0434\u0430\u0447\u0456 \u0440\u043E\u0437\u043F\u0456\u0437\u043D\u0430\u0432\u0430\u043D\u043D\u044F \u043F\u043E\u0442\u0440\u0456\u0431\u043D\u043E \u0432\u0438\u0437\u043D\u0430\u0447\u0438\u0442\u0438, \u0447\u0438 \u0456\u0441\u043D\u0443\u0454 \u0432 \u0437\u0430\u0434\u0430\u043D\u043E\u043C\u0443 \u0433\u0440\u0430\u0444\u0456 G \u043A\u043B\u0456\u043A\u0430 \u0440\u043E\u0437\u043C\u0456\u0440\u0443 k, \u0442\u043E\u0434\u0456 \u044F\u043A \u0432 \u043E\u0431\u0447\u0438\u0441\u043B\u044E\u0432\u0430\u043B\u044C\u043D\u043E\u043C\u0443 \u0432\u0430\u0440\u0456\u0430\u043D\u0442\u0456 \u043F\u043E\u0442\u0440\u0456\u0431\u043D\u043E \u0437\u043D\u0430\u0439\u0442\u0438 \u0432 \u0437\u0430\u0434\u0430\u043D\u043E\u043C\u0443 \u0433\u0440\u0430\u0444\u0456 G \u043A\u043B\u0456\u043A\u0443 \u043C\u0430\u043A\u0441\u0438\u043C\u0430\u043B\u044C\u043D\u043E\u0433\u043E \u0440\u043E\u0437\u043C\u0456\u0440\u0443 \u0430\u0431\u043E \u0432\u0441\u0456 \u043C\u0430\u043A\u0441\u0438\u043C\u0430\u043B\u044C\u043D\u0456 \u043A\u043B\u0456\u043A\u0438 (\u0442\u0430\u043A\u0456, \u0449\u043E \u043D\u0435 \u043C\u043E\u0436\u043D\u0430 \u0437\u0431\u0456\u043B\u044C\u0448\u0438\u0442\u0438)."@uk . . . . . "Problema della cricca"@it . . . . . . . "En complejidad computacional, el problema del clique (a veces tambi\u00E9n traducido desde el ingl\u00E9s como problema del clan o problema de la camarilla\u200B), es un problema NP-completo seg\u00FAn la Teor\u00EDa de la complejidad computacional."@es . "\uD074\uB9AD \uBB38\uC81C (clique problem)\uB294 NP\uC644\uC804\uC778 \uADF8\uB798\uD504 \uC774\uB860\uC5D0 \uB4F1\uC7A5\uD558\uB294 \uBB38\uC81C\uC774\uB2E4. \uC774 \uBB38\uC81C\uB294 \uB9AC\uCC98\uB4DC \uCE74\uD504\uAC00 1972\uB144 \uB17C\uBB38\uC5D0\uC11C NP\uC644\uC804\uC784\uC744 \uC99D\uBA85\uD55C 21\uBB38\uC81C \uC911\uC758 \uD558\uB098\uC77C \uBFD0\uB9CC \uC544\uB2C8\uB77C, NP\uC644\uC804 \uBB38\uC81C \uC774\uB860\uC744 \uC18C\uAC1C\uD55C \uCFE1\uC758 \uB17C\uBB38\uC5D0\uC11C\uB3C4 \uC5B8\uAE09\uB41C \uC720\uBA85\uD55C \uBB38\uC81C\uC774\uB2E4. \uADF8\uB798\uD504\uC758 \uD074\uB9AD(clique)\uC774\uB780 \uBD80\uBD84\uADF8\uB798\uD504\uC774\uBA74\uC11C \uADF8\uB798\uD504\uC758 \uC784\uC758\uC758 \uB450 \uB178\uB4DC\uAC00 \uC11C\uB85C \uC5F0\uACB0\uB41C \uAC83\uC73C\uB85C \uC815\uC758\uB41C\uB2E4. \uC989, \uC644\uC804 \uADF8\uB798\uD504\uC778 \uBD80\uBD84\uADF8\uB798\uD504\uB97C \uD074\uB9AD\uC774\uB77C \uD55C\uB2E4. \uC624\uB978\uCABD \uADF8\uB9BC\uC5D0\uC11C \uB178\uB4DC 1, 2, 5\uB85C \uC774\uB8E8\uC5B4\uC9C4 \uBD80\uBD84\uADF8\uB798\uD504\uB294 \uD074\uB9AD\uC774 \uB41C\uB2E4. \uC65C\uB0D0\uD558\uBA74, \uAC01 \uB178\uB4DC\uAC00 \uBAA8\uB4E0 \uB098\uBA38\uC9C0 \uB178\uB4DC\uC640 \uC5F0\uACB0\uB418\uC5B4 \uC788\uAE30 \uB54C\uBB38\uC774\uB2E4. \uBC18\uBA74 2, 5, 3\uC73C\uB85C \uC774\uB8E8\uC5B4\uC9C4 \uADF8\uB798\uD504\uB97C \uBCF4\uBA74, 5\uC640 3\uC774 \uC5F0\uACB0\uB418\uC5B4 \uC788\uC9C0 \uC54A\uC544 \uD074\uB9AD\uC774 \uB418\uC9C0 \uBABB\uD55C\uB2E4."@ko . . . "In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique (a clique with the largest possible number of vertices), finding a maximum weight clique in a weighted graph, listing all maximal cliques (cliques that cannot be enlarged), and solving the decision problem of testing whether a graph contains a clique larger than a given size. The clique problem arises in the following real-world setting. Consider a social network, where the graph's vertices represent people, and the graph's edges represent mutual acquaintance. Then a clique represents a subset of people who all know each other, and algorithms for finding cliques can be used to discover these groups of mutual friends. Along with its applications in social networks, the clique problem also has many applications in bioinformatics, and computational chemistry. Most versions of the clique problem are hard. The clique decision problem is NP-complete (one of Karp's 21 NP-complete problems). The problem of finding the maximum clique is both fixed-parameter intractable and hard to approximate. And, listing all maximal cliques may require exponential time as there exist graphs with exponentially many maximal cliques. Therefore, much of the theory about the clique problem is devoted to identifying special types of graph that admit more efficient algorithms, or to establishing the computational difficulty of the general problem in various models of computation. To find a maximum clique, one can systematically inspect all subsets, but this sort of brute-force search is too time-consuming to be practical for networks comprising more than a few dozen vertices.Although no polynomial time algorithm is known for this problem, more efficient algorithms than the brute-force search are known. For instance, the Bron\u2013Kerbosch algorithm can be used to list all maximal cliques in worst-case optimal time, and it is also possible to list them in polynomial time per clique."@en . . . "\u0627\u0644\u0645\u062E\u0637\u0637 \u0627\u0644\u0643\u0627\u0645\u0644 \u0647\u0648 \u0645\u0636\u0644\u0639 \u0643\u0644 \u0631\u0623\u0633\u064A\u0646 \u0641\u064A\u0647 \u0645\u0631\u062A\u0628\u0637\u0627\u0646. \u0648\u0631\u062A\u0628\u0629 \u0627\u0644\u0645\u062E\u0637\u0637 \u0627\u0644\u0643\u0627\u0645\u0644 \u0647\u0648 \u0639\u062F\u062F \u0631\u0624\u0648\u0633\u0647."@ar . "Clique problem"@en . . .