Um clique de um grafo não direcionado é, na teoria dos grafos , um subconjunto dos vértices desse grafo cujo subgrafo induzido está completo , ou seja, quaisquer dois vértices do clique são sempre adjacentes.
Um clique máximo de um grafo é um clique com a maior cardinalidade (ou seja, tem o maior número de vértices). A cardinalidade de tal clique máximo é uma característica do grafo, chamada número de clique , e que podemos relacionar ao seu número cromático . O problema do clique máximo, encontrar um dos cliques máximos para um dado grafo (finito), é um problema NP-difícil .
Na teoria dos grafos , um clique é um conjunto de vértices adjacentes dois por dois. Mas o termo "clique" também é freqüentemente usado para se referir ao grafo induzido por um clique, isto é, um subgráfico induzido completo .
Da mesma forma, o termo “biclical” é comumente usado para designar um grafo bipartido completo em vez de seu conjunto de vértices ou arestas.
Às vezes usamos o termo p-clique ou mesmo clique de cardinalidade p para denotar um clique contendo p vértices.
O número cromático de um gráfico é maior ou igual ao número de vértices em seu maior clique
Vários problemas algorítmicos são definidos a partir de cliques, notadamente o problema do clique e o problema da partição do clique , que são parte dos 21 problemas NP-completos de Karp .
(pt) Ke Xu, " Benchmarks com soluções ótimas ocultas para problemas de gráfico (Clique máximo, conjunto independente máximo, cobertura de vértice mínima e coloração de vértice " , no BUAA