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 é NP-completo, mas apesar de sua dificuldade, vários algoritmos para encontrar clique foram estudados.
Imagem: San Diego Shooter · BY-NC-ND · Openverse
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.
Imagem: anarchosyn · BY-SA · Openverse
Resultados matemáticos a respeito de cliques incluem os seguintes.
Imagem: @CarShowShooter · BY-NC-SA · Openverse
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 (Karp 1972). 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.
Imagem: quinn.anya · BY-SA · Openverse
A 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ínuos de como modelar cliques sociais, veja e.g. Alba (1973), Peay (1974), e Doreian & Woodard (1994). Vários problemas da bioinformática foram modelados utilizando clique. Na química, Rhodes et al. (2003) utilizou cliques para descrever produtos químicos em um banco de dados que possuía um alto grau de similaridade com a estrutura alvo. Kuhl, Crippen & Friesen (1983) utilizou cliques para modelar as posições no qual dois produtos químicos vão se associar mutualmente.
