b'\n_START_ARTICLE_\nClique\n_START_PARAGRAPH_\nNa \xc3\xa1rea da matem\xc3\xa1tica da teoria dos grafos, um clique em um grafo n\xc3\xa3o-orientado \xc3\xa9 um subconjunto de seus v\xc3\xa9rtices tais que cada dois v\xc3\xa9rtices do subconjunto s\xc3\xa3o conectados por uma aresta._NEWLINE_Clique \xc3\xa9 um dos conceitos mais b\xc3\xa1sicos na teoria dos grafos e s\xc3\xa3o utilizados em v\xc3\xa1rios problemas matem\xc3\xa1ticos e constru\xc3\xa7\xc3\xb5es em grafos. O Clique vem sendo estudado na ci\xc3\xaancia da computa\xc3\xa7\xc3\xa3o: a tarefa de achar se existe um clique de um dado tamanho em um grafo (o problema do clique) \xc3\xa9 NP-completo, mas apesar de sua dificuldade, v\xc3\xa1rios algoritmos para encontrar clique foram estudados._NEWLINE_Embora o estudo de subgrafos completos seja da \xc3\xa9poca da reformula\xc3\xa7\xc3\xa3o te\xc3\xb3rica dos grafos da Teoria de Ramsey por Erd\xc5\x91s & Szekeres (1935), o termo "clique" vem de Luce & Perry (1949), que utilizou subgrafos completos em redes sociais para modelar cliques de pessoas; ou seja, grupos de pessoas onde todas se conhecem. O Clique possui v\xc3\xa1rias outras aplica\xc3\xa7\xc3\xb5es na ci\xc3\xaancia, principalmente na bioinform\xc3\xa1tica.\n_START_SECTION_\nDefini\xc3\xa7\xc3\xb5es\n_START_PARAGRAPH_\nUm clique em um grafo n\xc3\xa3o direcionado G\xc2\xa0=\xc2\xa0(V,\xc2\xa0E) \xc3\xa9 um subconjunto de v\xc3\xa9rtices C\xc2\xa0\xe2\x8a\x86\xc2\xa0V, tal que para cada dois v\xc3\xa9rtices em C, existe uma aresta os conectando. Isso se equivale a dizer que um subgrafo induzido de C \xc3\xa9 completo (em alguns casos, o termo clique tamb\xc3\xa9m pode ser refer\xc3\xaancia ao subgrafo)._NEWLINE_Um clique maximal \xc3\xa9 um clique que n\xc3\xa3o pode ser estendido ao se adicionar um ou mais v\xc3\xa9rtices adjacentes, ou seja, um clique que n\xc3\xa3o existe exclusivamente dentro de um conjunto de v\xc3\xa9rtices de um clique maior._NEWLINE_Um clique m\xc3\xa1ximo \xc3\xa9 o maior clique poss\xc3\xadvel em um dado grafo. O n\xc3\xbamero do clique \xcf\x89(G) de um grafo G \xc3\xa9 o n\xc3\xbamero de v\xc3\xa9rtices de um clique m\xc3\xa1ximo em G. O n\xc3\xbamero da intersec\xc3\xa7\xc3\xa3o de G \xc3\xa9 o menor n\xc3\xbamero de cliques que, juntos, cobrem todas as arestas de \xc2\xa0G._NEWLINE_O oposto de um clique \xc3\xa9 um conjunto independente, no sentido de que cada clique corresponde a um conjunto independente no grafo complementar. O problema da cobertura de clique se preocupa em achar o menor n\xc3\xbamero de clique poss\xc3\xadvel que inclui todos os v\xc3\xa9rtices no grafo. Um conceito relacionado \xc3\xa9 um biclique, um subgrafo completo bipartido. A dimens\xc3\xa3o de biparti\xc3\xa7\xc3\xa3o de um grafo \xc3\xa9 o menor n\xc3\xbamero de bicliques necess\xc3\xa1rios para cobrir todas as arestas do grafo.\n_START_SECTION_\nCi\xc3\xaancia da Computa\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nNa ci\xc3\xaancia da computa\xc3\xa7\xc3\xa3o, o problema do clique \xc3\xa9 um problema computacional para achar um clique m\xc3\xa1ximo, ou todos os cliques, em um dado grafo. Ele \xc3\xa9 NP-completo, um dos 21 problemas NP-Completos de Karp (Karp 1972). Ele tamb\xc3\xa9m \xc3\xa9 intrat\xc3\xa1vel para par\xc3\xa2metros fixos, e dif\xc3\xadcil de se aproximar. N\xc3\xa3o obstante, v\xc3\xa1rios algoritmos para computar  cliques foram desenvolvidos, alguns executando em tempo exponencial (como o algoritmo de Bron\xe2\x80\x93Kerbosch) ou especializado para fam\xc3\xadlias de grafos como grafos planares ou grafos perfeitos, onde o problema pode ser solucionado em tempo polinomial.\n_START_SECTION_\nAplica\xc3\xa7\xc3\xb5es\n_START_PARAGRAPH_\nA palavra "clique", no seu uso na teoria dos grafos, veio do trabalho de Luce & Perry (1949), que utilizou subgrafos completos para modelar cliques (grupos de pessoas que se conhecem) em redes sociais. Para trabalhos cont\xc3\xadnuos de como modelar cliques sociais, veja e.g. Alba (1973), Peay (1974), e Doreian & Woodard (1994)._NEWLINE_V\xc3\xa1rios problemas da bioinform\xc3\xa1tica foram modelados utilizando clique._NEWLINE_Na qu\xc3\xadmica, Rhodes et al. (2003) utilizou cliques para descrever produtos qu\xc3\xadmicos em um banco de dados que possu\xc3\xada um alto grau de similaridade com a estrutura alvo. Kuhl, Crippen & Friesen (1983) utilizou cliques para modelar as posi\xc3\xa7\xc3\xb5es no qual dois produtos qu\xc3\xadmicos v\xc3\xa3o se associar mutualmente.'