Clique

Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. Ajude a melhorar este artigo inserindo citações no corpo do artigo. (Agosto de 2024)

Na área da matemática da teoria dos grafos, um clique em um grafo não orientado é um subconjunto de seus vértices tais que cada dois vértices do subconjunto são conectados por uma aresta. Clique é um dos conceitos mais básicos na teoria dos grafos e são utilizados em vários problemas matemáticos e construções em grafos. O Clique vem sendo estudado na ciência da computação: a tarefa de achar se existe um clique de um dado tamanho em um grafo (o problema do clique) é NP-completo, mas apesar de sua dificuldade, vários algoritmos para encontrar clique foram estudados.

Embora o estudo de subgrafos completos seja da época da reformulação teórica dos grafos da Teoria de Ramsey por Erdős & Szekeres (1935),^[1] 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árias outras aplicações na ciência, principalmente na bioinformática.