Clique

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 , o termo "clique" vem de , 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.

Definições
Um clique em um grafo não direcionado G = (V, E) é um subconjunto de vértices C ⊆ V, tal que para cada dois vértices em C, existe uma aresta os conectando. Isso se equivale a dizer que um subgrafo induzido de C é completo (em alguns casos, o termo clique também pode ser referência ao subgrafo).

Um clique maximal é um clique que não pode ser estendido ao se adicionar um ou mais vértices adjacentes, ou seja, um clique que não existe exclusivamente dentro de um conjunto de vértices de um clique maior.

Um clique máximo é o maior clique possível em um dado grafo. O número do clique ω(G) de um grafo G é o número de vértices de um clique máximo em G. O número da intersecção de G é o menor número de cliques que, juntos, cobrem todas as arestas de  G.

O oposto de um clique é 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úmero de clique possível que inclui todos os vértices no grafo. Um conceito relacionado é um biclique, um subgrafo completo bipartido. A dimensão de bipartição de um grafo é o menor número de bicliques necessários para cobrir todas as arestas do grafo.

Matemáticas
Resultados matemáticos a respeito de cliques incluem os seguintes.
Teorema de Turán  da um limite inferior do tamanho de um clique em um grafo denso. Se um grafo tem uma quantidade suficiente de arestas, ele deve conter um cliquem  grande. Por exemplo, todo grafo com  vértices e mais que  arestas tem que conter um clique de 3 vértices(3-clique).
Teorema de Ramsey  confirma que todo grafo ou seu grafo complementar contém um clique com, ao menos, o número logaritmo da quantidade de vértices.
De acordo com os resultados de , um grafo com 3n vértices pode ter, no máximo, 3n cliques maximais. Os grafos que possuem essa característica são os grafos de Moon–Moser K3,3,..., um caso especial do grafo de Turán surgindo como um caso extremo no teorema de Turán.
A Conjectura de Hadwiger, ainda não provada, relata o tamanho do maior clique mínimoem um grafo (o seu número de Hadwiger) para seu número cromático.
A conjectura de Erdős–Faber–Lovász é outra declaração ainda não provada que relaciona a coloração de grafos à clique.

Ciência da Computação

Na ciência da computação, o problema do clique é um problema computacional para achar um clique máximo, ou todos os cliques, em um dado grafo. Ele é NP-completo, um dos 21 problemas NP-Completos de Karp . Ele também é intratável para parâmetros fixos, e difícil de se aproximar. Não obstante, vários algoritmos para computar  cliques foram desenvolvidos, alguns executando em tempo exponencial (como o algoritmo de Bron–Kerbosch) ou especializado para famílias de grafos como grafos planares ou grafos perfeitos, onde o problema pode ser solucionado em tempo polinomial.

Aplicações
A palavra "clique", no seu uso na teoria dos grafos, veio do trabalho de , que utilizou subgrafos completos para modelar cliques (grupos de pessoas que se conhecem) em redes sociais. Para trabalhos contínuos de como modelar cliques sociais, veja e.g. , , e .

Vários problemas da bioinformática foram modelados utilizando clique.
Na química,  utilizou cliques para descrever produtos químicos em um banco de dados que possuía um alto grau de similaridade com a estrutura alvo.  utilizou cliques para modelar as posições no qual dois produtos químicos vão se associar mutualmente.

Ver também
 Grafo completo

Notas

Referências

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

Ligações externas 

Teoria dos grafos