Clique

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Um grafo com 23 cliques de 1-vértice (seus vértices), 42 cliques de 2-vértices (suas arestas), 19 cliques de 3-vértices (os triângulos em azul claro), e 2 cliques de 4-vértices (azul escuro). Seis das arestas e 11 dos triângulos formam cliques maximais. As duas 4-cliques em azul escuro são tanto máximas quanto maximais, e o número de clique do grafo é 4.

Na área da matemática da teoria dos grafos, uma 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. Uma clique em um grafo G é um subgrafo de G que é completo. Eles recebem a notação K_n[1] . O tamanho de uma clique é igual a cardinalidade de seu conjunto de vértices. Por exemplo no grafo G(V,E) sendo V seu conjunto de vértices e E o de arestas, temos que:

Se V={1,2,3,4,5} e E={(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(3,4),(4,5)}, o subgrafo induzido pelos vértices (1,2,3,4) é uma clique de tamanho 4.

Ver também[editar | editar código-fonte]

Referências

  1. BOAVENTURA NETTO, Paulo Oswaldo. Grafos. São Paulo: Edgard Blücher, 2001. ISBN 85-212-0292-X