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 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ê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 (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 cliquem 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, 3ⁿ cliques maximais. Os grafos que possuem essa característica são os grafos de Moon–Moser K_3,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 (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

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.

Ver também

Grafo completo

Notas

↑ 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

Alba, Richard D. (1973), «A graph-theoretic definition of a sociometric clique» (PDF), Journal of Mathematical Sociology, 3 (1): 113–126, doi:10.1080/0022250X.1973.9989826 .
Barthélemy, J.-P.; Leclerc, B.; Monjardet, B. (1986), «On the use of ordered sets in problems of comparison and consensus of classifications», Journal of Classification, 3 (2): 187–224, doi:10.1007/BF01894188 .
Ben-Dor, Amir; Shamir, Ron; Yakhini, Zohar (1999), «Clustering gene expression patterns.», Journal of Computational Biology, 6 (3–4): 281–297, PMID 10582567, doi:10.1089/106652799318274 .
J., Cong; M., Smith (1993), «A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design», Proc. 30th International Design Automation Conference, pp. 755–760, doi:10.1145/157485.165119 .
Day, William H. E.; Sankoff, David (1986), «Computational complexity of inferring phylogenies by compatibility», Systematic Zoology, 35 (2): 224–229, JSTOR 2413432, doi:10.2307/2413432 .
Doreian, Patrick; Woodard, Katherine L. (1994), «Defining and locating cores and boundaries of social networks», Social Networks, 16 (4): 267–293, doi:10.1016/0378-8733(94)90013-2 .
Erdős, Paul; Szekeres, George (1935), «A combinatorial problem in geometry» (PDF), Compositio Math., 2: 463–470 .
Graham, R.; Rothschild, B.; Spencer, J. H. (1990), Ramsey Theory, ISBN 0-471-50046-1, New York: John Wiley and Sons .
Hamzaoglu, I.; Patel, J. H. (1998), «Test set compaction algorithms for combinational circuits», Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design, pp. 283–289, doi:10.1145/288548.288615 .
Karp, Richard M. (1972), «Reducibility among combinatorial problems», in: Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (PDF), New York: Plenum, pp. 85–103 .
Kuhl, F. S.; Crippen, G. M.; Friesen, D. K. (1983), «A combinatorial algorithm for calculating ligand binding», Journal of Computational Chemistry, 5 (1): 24–34, doi:10.1002/jcc.540050105 .
Kuratowski, Kazimierz (1930), «Sur le probléme des courbes gauches en Topologie» (PDF), Fundamenta Mathematicae (em francês), 15: 271–283 .
Luce, R. Duncan; Perry, Albert D. (1949), «A method of matrix analysis of group structure», Psychometrika, 14 (2): 95–116, PMID 18152948, doi:10.1007/BF02289146 .
Moon, J. W.; Moser, L. (1965), «On cliques in graphs», Israel J. Math., 3: 23–28, MR 0182577, doi:10.1007/BF02760024 .
Paull, M. C.; Unger, S. H. (1959), «Minimizing the number of states in incompletely specified sequential switching functions», IRE Trans. on Electronic Computers, EC–8 (3): 356–367, doi:10.1109/TEC.1959.5222697 .
Peay, Edmund R. (1974), «Hierarchical clique structures», Sociometry, 37 (1): 54–65, JSTOR 2786466, doi:10.2307/2786466 .
Prihar, Z. (1956), «Topological properties of telecommunications networks», Proceedings of the IRE, 44 (7): 927–933, doi:10.1109/JRPROC.1956.275149 .
Rhodes, Nicholas; Willett, Peter; Calvet, Alain; Dunbar, James B.; Humblet, Christine (2003), «CLIP: similarity searching of 3D databases using clique detection», Journal of Chemical Information and Computer Sciences, 43 (2): 443–448, PMID 12653507, doi:10.1021/ci025605o .
Samudrala, Ram; Moult, John (1998), «A graph-theoretic algorithm for comparative modeling of protein structure», Journal of Molecular Biology, 279 (1): 287–302, PMID 9636717, doi:10.1006/jmbi.1998.1689 .
Spirin, Victor; Mirny, Leonid A. (2003), «Protein complexes and functional modules in molecular networks», Proceedings of the National Academy of Sciences, 100 (21): 12123–12128, PMC 218723, PMID 14517352, doi:10.1073/pnas.2032324100 .
Sugihara, George (1984), «Graph theory, homology and food webs», in: Levin, Simon A., Population Biology, Proc. Symp. Appl. Math., 30, pp. 83–101 .
Tanay, Amos; Sharan, Roded; Shamir, Ron (2002), «Discovering statistically significant biclusters in gene expression data», Bioinformatics, 18 (Suppl. 1): S136–S144, PMID 12169541, doi:10.1093/bioinformatics/18.suppl_1.S136 .
Turán, Paul (1941), «On an extremal problem in graph theory», Matematikai és Fizikai Lapok (em húngaro), 48: 436–452

Ligações externas

Weisstein, Eric W. «Clique». MathWorld (em inglês)
Weisstein, Eric W. «Clique Number». MathWorld (em inglês)

[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.

[1]