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, 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ênca, principalmente na bioinformática.

Definições[editar | editar código-fonte]

Um clique em um grafo não direcionado G = (VE) é 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ática[editar | editar código-fonte]

Resultados matemáticos a respeito de cliques incluem os seguintes.

  • Teorema de Turán (Turán 1941) 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 clique grande. Por exemplo, todo grafo com n vértices e mais que \scriptstyle\lfloor\frac{n}{2}\rfloor\cdot\lceil\frac{n}{2}\rceil arestas tem que conter um clique de 3 vértices(3-clique).
  • Teorema de Ramsey (Graham, Rothschild & Spencer 1990) 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 Moon & Moser (1965), 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[editar | editar código-fonte]

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.

Aplicações[editar | editar código-fonte]

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.

Notas[editar | editar código-fonte]

  1. O Trabalho de Kuratowski (1930) caracterizando grafos planares por esquecimento e grafos completos bipartidos foram originalmente citados em topologia ao invés de teoria dos grafos.

Referências[editar | editar código-fonte]

Links Externos[editar | editar código-fonte]

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

Referências