Mostrar código-fonte de Clique

{{Nota:|Há uma pagina de [[Clique (desambiguação)]] }}
{{Sem notas|data=agosto de 2024}}
[[Imagem:VR complex.svg|thumb|300px|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értice (teoria dos grafos)|vértices]] tais que cada dois vértices do subconjunto são conectados por uma [[aresta (teoria dos grafos)|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 [[Grafo completo|subgrafos completos]] seja da época da reformulação teórica dos grafos da [[Teoria de Ramsey]] por {{harvtxt|Erdős|Szekeres|1935}},<ref>O Trabalho de {{harvtxt|Kuratowski|1930}} caracterizando grafos planares por esquecimento e grafos completos bipartidos foram originalmente citados em topologia ao invés de teoria dos grafos.</ref> o termo "clique" vem de {{harvtxt|Luce|Perry|1949}}, que utilizou subgrafos completos em [[Rede social|redes sociais]] para modelar [[clique]]s 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''&nbsp;=&nbsp;(''V'',&nbsp;''E'') é um subconjunto de [[Vértice (teoria dos grafos)|vértices]] ''C''&nbsp;⊆&nbsp;''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 &nbsp;''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 [[Grafo bipartido completo|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]] {{harv|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 <math>n</math> vértices e mais que <math>\scriptstyle\lfloor\frac{n}{2}\rfloor\cdot\lceil\frac{n}{2}\rceil</math> arestas tem que conter um clique de 3 vértices(3-clique).
*[[Teorema de Ramsey]] {{harv|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 {{harvtxt|Moon|Moser|1965}}, um grafo com 3''n'' vértices pode ter, no máximo, 3<sup>''n''</sup> cliques maximais. Os grafos que possuem essa característica são os grafos de Moon–Moser ''K''<sub>3,3,...</sub>, 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==
{{main|Problema do clique}}
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 {{harv|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 {{harvtxt|Luce|Perry|1949}}, que utilizou subgrafos completos para modelar [[clique]]s (grupos de pessoas que se conhecem) em redes sociais. Para trabalhos contínuos de como modelar cliques sociais, veja e.g. {{harvtxt|Alba|1973}}, {{harvtxt|Peay|1974}}, e {{harvtxt|Doreian|Woodard|1994}}.

Vários problemas da bioinformática foram modelados utilizando clique.
Na [[química]], {{harvtxt|Rhodes|Willett|Calvet|Dunbar|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. {{harvtxt|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==
{{reflist}}

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

== Ligações externas ==
*{{MathWorld|title=Clique|urlname=Clique}}
*{{MathWorld|title=Clique Number|urlname=CliqueNumber}}

[[Categoria:Teoria dos grafos]]