Vizualizare sursă pentru „Clică (Matematică)”

{{About-distinguish|Clică în domeniul matematic|Clică (Științe sociale)}}[[Fișier:VR_complex.svg|miniatura|Un graf cu {{Bulleted list| 23 × clici de 1 nod (nodurile),
| 42 × clici de 2 noduri (muchiile),
| 19 × clici de 3 noduri (triunghiurile albastru-închis și deschis), și
| 2 × clici de 4 noduri (zonele albastru-închis).}}
Cele 11 triunghiuri albastre deschis formează clici maximale. Cele două 4-clici albastre închis sunt atât maxime cât și maximale, iar numărul de clică al grafului este 4.]]
În domeniul [[Matematică|matematic]] al [[Teoria grafurilor|teoriei grafurilor]], o '''clică''' este o submulțime de noduri ale unui [[Graf|graf neorientat]] cu proprietatea că subgraful indus de ele este [[Graf complet|complet]]; adică, orice două noduri distincte din clică sunt adiacente. Clicile sunt unul dintre conceptele de bază din teoria grafurilor și sunt folosite în multe alte probleme de matematică și construcții de grafuri. Clicile au fost studiate și în [[informatică]]: aflarea dacă există o clică de o anumită dimensiune într-un [[graf]] ([[problema clicii]]) este [[NP-completitudine|NP-completă]], dar în ciuda acestui rezultat ce relevă dificultatea problemei, s-au studiat mulți algoritmi pentru găsirea de clici.

Deși studiul [[Graf complet|subgrafurilor complete]] datează cel puțin de la reformularea [[Teoria lui Ramsey|teoriei lui Ramsey]] în termeni de teoria grafurilor de către {{harvtxt|Erdős|Szekeres|1935}},<ref>Lucrările anterioare de {{harvtxt|Kuratowski|1930}} ce caracterizează [[Graf planar|grafurile planare]] interzicând subgrafurile complete și {{Ill-wd|Q913598|3=bipartite complete}} au fost formulate inițial în termeni topologici și nu de teoria grafurilor.</ref> termenul de ''clică'' vine de la {{harvtxt|Luce|Perry|1949}}, care au folosit subgrafurile complete în [[Rețea socială|rețelele sociale]] pentru a modela [[Clică (științe sociale)|clici]] de oameni; adică grupuri de oameni care se cunosc reciproc. Clicile au multe alte aplicații în științe și în special în [[bioinformatică]].

== Definiții ==
O '''clică''' ''C'', într-un [[Graf|graf neorientat]] ''G'' = (''V'', ''E'') este o submulțime de [[Nod (teoria grafurilor)|noduri]], ''C'' ⊆ ''V'', astfel încât fiecare două noduri distincte sunt adiacente. Acest lucru este echivalent cu condiția ca [[Subgraf indus|subgraful indus]] al lui ''G'' de către ''C'' s ă fie[[ graf complet]]. În unele cazuri, termenul de clică se poate referi și direct la subgraf.

O '''clică maximală''' este o clică care nu poate fi extinsă prin includerea niciunui alt nod adiacent, adică o clică care nu este inclusă în mulțimea de noduri a unei clici mai mari. Unii autori definesc clicile într-un mod în care li se impune să fie maximale, și utilizează alte terminologii pentru subgrafurile complete care nu sunt maximale.

'''Clica maximă''' a unui graf ''G'', este o clică cu proprietatea că nu există nicio clică cu mai multe noduri.

'''Numărul de clică''' ω(''G'') al unui graf ''G'' este numărul de noduri dintr-o clică maximă în ''G''.

'''{{Ill-wd|Q17101799|3=Numărul de intersecție}}''' al lui ''G'' este cel mai mic număr de clici care împreună acoperă toate muchiile lui ''G''.

'''Numărul de acoperire cu clici''' al unui graf ''G'' este cel mai mic număr de clici ale lui ''G'' a căror reuniune acoperă ''V(G)''.

Un '''parcurgere maximă a clicilor''' unui graf este o submulțime de noduri cu proprietatea că orice clică maximă a grafului conține cel puțin un nod din submulțime.{{Sfnp|Chang|Kloks|Lee|2001}}

Opusul conceptului de clică este cel de '''mulțime independentă''', în sensul că fiecare clică corespunde unei mulțimi independente în {{Ill-wd|Q902252|3=graful complementar}}. Problema {{Ill-wd|Q1096734|3=acoperirii de clică}} se referă la găsirea a cât mai puține clici posibil, care includ toate nodurile din graf.

Un concept legat este cel de '''biclică''', un {{Ill-wd|Q913598|3=subgraf bipartit complet}}. {{Ill-wd|Q4915408|3=Dimensiunea bipartită}} a unui graf este numărul minim de biclici necesare pentru a acoperi toate muchiile grafului.

== Matematică ==
Printre rezultatele matematice ce includ conceptul de clică se numără următoarele:
* {{Ill-wd|Q1047749|3=Teorema lui Turán}} dă o {{Ill-wd|Q13222579|3=limită inferioară}} cu privire la dimensiunea unei clici în {{Ill-wd|Q3085841|3=grafuri dense}}.{{Sfnp|Turán|1941}} Dacă un graf are suficient de multe margini, acesta trebuie să conțină o clică mare. De exemplu, fiecare graf cu {{math|n}} noduri și mai mult de <math>\scriptstyle\lfloor\frac{n}{2}\rfloor\cdot\lceil\frac{n}{2}\rceil</math> muchii trebuie să conțină clici cu cel puțin trei noduri.
* {{Ill-wd|Q918099|3=Teorema lui Ramsey}} afirmă că orice graf sau {{Ill-wd|Q902252|3=graful său complementar}} conține o clică cu cel puțin un număr logaritmic de noduri.{{Sfnp|Graham|Rothschild|Spencer|1990}}
* Potrivit unui rezultat al lui {{harvtxt|Moon|Moser|1965}}, un graf cu 3''n'' noduri poate avea cel mult 3<sup>''n''</sup> clici maximale. Grafurile care îndeplinesc această limită sunt grafurile Luna–Moser ''K''<sub>3,3,...</sub>, un caz special de {{Ill-wd|Q720459|3=grafuri Turán}} care rezultă drept cazuri extreme în teorema lui Turán.
* {{Ill-wd|Q1128435|3=Conjectura lui Hadwiger}}, încă nedemonstrată, leagă dimensiunea celui mai mare minor de clică într-un graf ({{Ill-wd|Q5638117|3=numărul Hadwiger}}) de [[Colorarea grafurilor|numărul său cromatic]].
* Conjectura Erdős–Faber–Lovasz este o alt enunț nedemonstrat ce face legătura între colorarea grafurilor și clici.
Mai multe clase importante de grafuri pot fi definite sau caracterizate prin clicile lor:
* Un {{Ill-wd|Q24892498|3=graf cluster}} este un graf ale cărui [[Componentă conexă|componente conexe]] sunt clici.
* Un {{Ill-wd|Q4927193|3=graf bloc}} este un graf ale cărui {{Ill-wd|Q2300244|3=componente biconexe}} sunt clici.
* Un {{Ill-wd|Q1322892|3=graf cordal}} este un graf ale cărui noduri pot fi ordonate într-o ordine perfectă de eliminare, astfel încât {{Ill-wd|Q1354987|3=vecinii}} fiecărui nod ''v'' care vin mai târziu decât ''v'' în ordonare formează o clică.
* Un {{Ill-wd|Q5141281|3=cograf}} este un graf ale cărui subgrafuri induse au proprietatea că orice clică maximală intersectează orice {{Ill-wd|Q7888149|3=mulțime independentă maximală}} într-un singur nod.
* Un {{Ill-wd|Q835942|3=graf de intervale}} este un graf ale cărui clici maximale pot fi ordonate în așa fel încât, pentru fiecare nod ''v'', clicile care conțin ''v'' sunt consecutive în ordonare.
* Un {{Ill-wd|Q1378376|3=graf linie}} este un graf ale cărui muchii pot fi acoperite cu clici cu muchii disjuncte clici în așa fel încât fiecare nod face parte din exact două dintre clicile din acoperire.
* Un {{Ill-wd|Q1187620|3=graf perfect}} este un graf în care numărul de clică este egal cu [[Colorarea grafurilor|numărul cromatic]] în orice [[subgraf indus]].
* Un {{Ill-wd|Q3893853|3=graf împărțit}} este un graf în care o clică conține cel puțin o extremitate a fiecărei muchii.
* Un {{Ill-wd|Q7840044|3=graf fără triunghiuri}} este un graf care nu are clici, altele decât nodurile și muchiile sale.
În plus, multe alte construcții matematice implică clicile în grafuri. Printre ele,
* {{Ill-wd|Q5134413|3=Complexul de clică}} al unui graf ''G'' este un {{Ill-wd|Q4669959|3=complex abstract simplicial}} ''X''(''G'') cu un simplex pentru fiecare clică din ''G''
* Un [[graf simplex]] este un graf neorientat κ(''G'') cu un nod pentru fiecare clică dintr-un graf ''G'' și o muche ce leagă două clici care diferă printr-un singur nod. Acesta este un exemplu de {{Ill-wd|Q3115592|3=graf median}}, și este asociat cu o {{Ill-wd|Q6806108|3=algebră mediană}} pe clicile unui graf: mediana ''m''(''A'',''B'',''C'') a trei clici ''A'', ''B'' și ''C'' este clica ale cărei noduri aparțin a cel puțin două dintre clicile ''A'', ''B'', și ''C''.<ref>{{harvtxt|Barthélemy|Leclerc|Monjardet|1986}}, page 200.</ref>
* {{Ill-wd|Q5134410|3=Suma de clică}} este o metodă de combinare a două grafuri prin comasarea lor de-a lungul unei clici comune.
* {{Ill-wd|Q1101814|3=Lățimea de clică}} este o noțiune de complexitate a unui graf în ceea ce privește numărul minim de etichete distincte de noduri necesare pentru a construi graful din reuninuni disjuncte, operațiuni de reetichetare, precum și operațiuni care leagă toate perechile de noduri cu etichete date. Grafurile cu lățime de clică unul sunt exact reuniuni disjuncte de clici.
* {{Ill-wd|Q17101799|3=Numărul de intersecție}} al unui graf este numărul minim de clici necesare pentru a acoperi toate muchiile grafului.
* {{Ill-wd|Q17101022|3=Graful de clici}} al unui graf este {{Ill-wd|Q3498041|3=graful de intersecție}} al clicilor lui maximale.
Concepte strâns legate de subgrafurile complete sunt {{Ill-wd|Q584521|3=subdiviziunile}} de grafuri complete și {{Ill-wd|Q905837|3=minorii compleți de graf}}. În special, {{Ill-wd|Q837902|3=teorema lui Kuratowski}} și {{Ill-wd|Q7959587|3=teorema lui Wagner}} caracterizează [[Graf planar|grafurile planare]] prin subdiviziunile și minorii interziși compleți și, respectiv, {{Ill-wd|Q913598|3=bipartiți compleți}}.

== Informatică ==
În [[informatică]], [[problema clicii]] este problema computațională de găsire a unei clici maxime, sau a tuturor clicilor dintr-un anumit graf. Este [[NP-completitudine|NP-completă]], una dintre [[Cele 21 de probleme NP-complete ale lui Karp|cele 21 de probleme NP-complete ale lui Karp]].{{Sfnp|Karp|1972}} Este și {{Ill-wd|Q1570441|3=netractabilă în parametru fix}} și {{Ill-wd|Q5656275|3=greu de aproximat}}. Cu toate acestea, s-au dezvoltat mulți [[Algoritm|algoritmi]] pentru calculul clicilor, care fie rulează în [[Complexitate în timp|timp exponențial]] (cum ar fi {{Ill-wd|Q2031707|3=algoritmul Bron–Kerbosch}}) fie se specializează pe familii de grafuri, cum ar fi [[Graf planar|grafurile planare]] sau {{Ill-wd|Q1187620|3=grafurile perfecte}} pentru care problema poate fi rezolvată în [[Complexitate în timp|timp polinomial]].

== Aplicații ==
Cuvântul „clică”, în utilizarea sa din teoria grafurilor, provine din lucrările lui {{harvtxt|Luce|Perry|1949}}, care au folosit subgrafurile complete pentru a modela [[Clică (științe sociale)|clici]] (grupări de oameni care se cunosc) în [[Rețea socială|rețelele sociale]]. Pentru continuarea eforturilor de a modela clicile sociale în teoria grafurilor, vedeți, de exemplu, {{harvtxt|Alba|1973}}, {{harvtxt|Peay|1974}}, și {{harvtxt|Doreian|Woodard|1994}}.

Multe probleme diferite de [[bioinformatică]] au fost modelate folosind clici.
De exemplu, {{harvtxt|Ben-Dor|Shamir|Yakhini|1999}} modelează problema clusteringului datelor de [[exprimare genetică]] ca fiind una de a găsi numărul minim de modificări necesare pentru a transforma un graf ce descrie datele într-un graf format ca reuniune disjunctă de clici; {{harvtxt|Tanay|Sharan|Shamir|2002}} discută o problemă similară de {{Ill-wd|Q2976575}} pentru date de expresie în care clusterele sunt obligatoriu clici. {{harvtxt|Sugihara|1984}} folosește clicile pentru a modela [[Nișă ecologică|nișe ecologice]] în [[Lanț trofic|rețele trofice]]. {{harvtxt|Day|Sankoff|1986}} descrie problema deducției [[Arbore filogenetic|arborilor evolutivi]] ca una de găsire a clicii maxime într-un graf care are ca noduri caracteristicile speciilor, unde două noduri sunt legate de o muchie dacă există o filogenie perfectă ce combină cele două caracteristici. {{harvtxt|Samudrala|Moult|1998}} modelează predicția structurii proteice ca o problemă de găsire a unor clici într-un graf ale cărui noduri reprezintă poziții ale subunităților de proteine. Și căutând clici într-o rețea de interacțiuni proteină-proteină, {{harvtxt|Spirin|Mirny|2003}} au găsit grupuri de proteine care interacționează strâns între ele și au puține interacțiuni cu proteinele din afara grupului. Power graph analysis este o metodă de simplificare a rețelelor biologice complexe găsind clici și structuri asociate în aceste rețele.

În [[Electrotehnică|ingineria electrică]], {{harvtxt|Prihar|1956}} folosește clicile pentru a analiza rețelele de comunicații, și {{harvtxt|Paull|Unger|1959}} le utilizează pentru a proiecta eficient circuitele care calculează funcții booleene specificate parțial. Clicile au fost utilizate și în generarea de șabloane de testare automată: o clică mare într-un graf de incompatibilități ale unor defecte posibile oferă o limită inferioară cu privire la dimensiunea unui set de teste.<ref>{{harvtxt|Hamzaoglu|Patel|1998}}.</ref> {{harvtxt|Cong|Smith|1993}} descrie o aplicație a clicilor în găsirea unei partiții ierarhice a unui circuit electronic în subunități mai mici.

În [[chimie]], {{harvtxt|Rhodes|Willett|Calvet|Dunbar|2003}} utilizează clicile pentru a descrie substanțe chimice dintr-o bază de date chimică, care au un grad ridicat de similitudine cu o structură țintă. {{harvtxt|Kuhl|Crippen|Friesen|1983}} utilizează clicile pentru a modela pozițiile în care două substanțe chimice se vor lega una de alta.

== Note ==
<references />

== Bibliografie ==
{{refbegin|2}}
*{{citation |doi=10.1080/0022250X.1973.9989826 |first=Richard D. |last=Alba |title=A graph-theoretic definition of a sociometric clique |journal=Journal of Mathematical Sociology |year=1973 |volume=3 |issue=1 |pages=113–126 |url=http://aris.ss.uci.edu/~lin/1.pdf |access-date=2017-06-15 |archive-date=2011-05-03 |archive-url=https://web.archive.org/web/20110503220546/http://aris.ss.uci.edu/~lin/1.pdf |dead-url=yes }}.
*{{citation | last1 = Barthélemy | first1 = J.-P. | last2 = Leclerc | first2 = B. | last3 = Monjardet | first3 = B. | issue = 2 | journal = Journal of Classification | pages = 187–224 | title = On the use of ordered sets in problems of comparison and consensus of classifications | doi = 10.1007/BF01894188 | volume = 3 | year = 1986}}.
*{{citation |first1=Amir |last1=Ben-Dor |first2=Ron |last2=Shamir |first3=Zohar |last3=Yakhini |journal=Journal of Computational Biology |year=1999 |volume=6 |issue=3–4 |pages=281–297 |doi=10.1089/106652799318274 |pmid=10582567 |title=Clustering gene expression patterns.}}.
*{{citation
 | last1 = Chang | first1 = Maw-Shang
 | last2 = Kloks | first2 = Ton
 | last3 = Lee | first3 = Chuan-Min
 | contribution = Maximum clique transversals
 | doi = 10.1007/3-540-45477-2_5
 | mr = 1905299
 | pages = 32–43
 | publisher = Springer, Berlin
 | series = Lecture Notes in Comput. Sci.
 | title = Graph-theoretic concepts in computer science (Boltenhagen, 2001)
 | volume = 2204
 | year = 2001}}.
*{{citation |last1=Cong |first1=J. |last2=Smith |first2=M. |contribution=A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design |title=Proc. 30th International Design Automation Conference |year=1993 |pages=755–760 |doi=10.1145/157485.165119}}.
*{{citation |title=Computational complexity of inferring phylogenies by compatibility |first1=William H. E. |last1=Day |first2=David |last2=Sankoff |journal=Systematic Zoology |volume=35 |issue=2 |year=1986 |pages=224–229 |doi=10.2307/2413432 |jstor=2413432}}.
*{{citation |title=Defining and locating cores and boundaries of social networks |first1=Patrick |last1=Doreian |first2=Katherine L. |last2=Woodard |journal=Social Networks |volume=16 |issue=4 |year=1994 |pages=267–293 |doi=10.1016/0378-8733(94)90013-2}}.
*{{citation |first1=Paul |last1=Erdős |author1-link=Paul Erdős |first2=George |last2=Szekeres |author2-link=George Szekeres |title=A combinatorial problem in geometry |journal=Compositio Mathematica |volume=2 |year=1935 |pages=463–470 |url=http://www.renyi.hu/~p_erdos/1935-01.pdf }}.
*{{citation
 | last1 = Graham | first1 = R. | author1-link = Ronald Graham
 | last2 = Rothschild | first2 = B.
 | last3 = Spencer | first3 = J. H. | author3-link = Joel Spencer
 | location = New York
 | publisher = John Wiley and Sons
 | title = Ramsey Theory
 | year = 1990
 | isbn = 0-471-50046-1}}.
*{{citation |last1=Hamzaoglu |first1=I. |last2=Patel |first2=J. H. |contribution=Test set compaction algorithms for combinational circuits |title=Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design |year=1998 |pages=283–289 |doi=10.1145/288548.288615}}.
*{{citation | last = Karp | first = Richard M. | authorlink = Richard M. Karp | url = http://www.cs.berkeley.edu/~luca/cs172/karp.pdf | contribution = Reducibility among combinatorial problems | title = Complexity of Computer Computations | editor1-first = R. E. | editor1-last = Miller | editor2-first = J. W. | editor2-last = Thatcher | publisher = New York: Plenum | pages = 85&ndash;103 | year = 1972 | access-date = 2017-06-15 | archive-date = 2011-06-29 | archive-url = https://web.archive.org/web/20110629023717/http://www.cs.berkeley.edu/~luca/cs172/karp.pdf | dead-url = yes }}.
*{{citation |first1=F. S. |last1=Kuhl |first2=G. M. |last2=Crippen |first3=D. K. |last3=Friesen |year=1983 |title=A combinatorial algorithm for calculating ligand binding |journal=Journal of Computational Chemistry |doi=10.1002/jcc.540050105 |volume=5 |issue=1 |pages=24–34}}.
*{{citation |first=Kazimierz |last=Kuratowski |authorlink=Kazimierz Kuratowski |language=French |title=Sur le probléme des courbes gauches en Topologie |journal=Fundamenta Mathematicae |volume=15 |year=1930 |pages=271–283 |url=http://matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf }}.
*{{citation
 | last1 = Luce | first1 = R. Duncan | author1-link = R. Duncan Luce
 | last2 = Perry | first2 = Albert D.
 | title = A method of matrix analysis of group structure 
 | journal = Psychometrika | volume = 14 | issue = 2 | year = 1949
 | pages = 95–116 | doi = 10.1007/BF02289146
 | pmid = 18152948}}.
*{{citation
 | last1 = Moon | first1 = J. W. | author2-link = Leo Moser | last2 = Moser | first2 = L.
 | title = On cliques in graphs
 | journal = Israel J. Math.
 | volume = 3
 | year = 1965
 | pages = 23–28
 | mr = 0182577 
 | doi = 10.1007/BF02760024}}.
*{{citation |first1=M. C. |last1=Paull |first2=S. H. |last2=Unger |title=Minimizing the number of states in incompletely specified sequential switching functions |journal=IRE Trans. on Electronic Computers |volume=EC-8 |issue=3 |year=1959 |pages=356–367 |doi=10.1109/TEC.1959.5222697}}.
*{{citation |title=Hierarchical clique structures |first=Edmund R. |last=Peay |journal=Sociometry |volume=37 |issue=1 |year=1974 |pages=54–65 |doi=10.2307/2786466 |jstor=2786466}}.
*{{citation |last=Prihar |first=Z. |title=Topological properties of telecommunications networks |journal={{Ill-wd|Q3021749}} |volume=44 |issue=7 |year=1956 |pages=927–933 |doi=10.1109/JRPROC.1956.275149}}.
*{{citation |first1=Nicholas |last1=Rhodes |first2=Peter |last2=Willett |first3=Alain |last3=Calvet |first4=James B. |last4=Dunbar |first5=Christine |last5=Humblet |journal=Journal of Chemical Information and Computer Sciences |volume=43 |issue=2 |pages=443–448 |year=2003 |doi=10.1021/ci025605o |pmid=12653507 |title=CLIP: similarity searching of 3D databases using clique detection}}.
*{{citation |first1=Ram |last1=Samudrala |first2=John |last2=Moult |title=A graph-theoretic algorithm for comparative modeling of protein structure |journal=Journal of Molecular Biology |volume=279 |issue=1 |year=1998 |pages=287–302 |doi=10.1006/jmbi.1998.1689 |pmid=9636717}}.
*{{citation |first1=Victor |last1=Spirin |first2=Leonid A. |last2=Mirny |title=Protein complexes and functional modules in molecular networks |journal=[[Proceedings of the National Academy of Sciences]] |volume=100 |issue=21 |pages=12123–12128 |doi=10.1073/pnas.2032324100 |year=2003 |pmid=14517352 |pmc=218723}}.
*{{citation |first=George |last=Sugihara |contribution=Graph theory, homology and food webs |year=1984 |pages=83–101 |series=Proc. Symp. Appl. Math. |volume=30 |title=Population Biology |editor-last=Levin |editor-first=Simon A.}}.
*{{citation |first1=Amos |last1=Tanay |first2=Roded |last2=Sharan |first3=Ron |last3=Shamir |title=Discovering statistically significant biclusters in gene expression data |journal=Bioinformatics |volume=18 |issue=Suppl. 1 |year=2002 |pages=S136–S144 |pmid=12169541 |doi=10.1093/bioinformatics/18.suppl_1.S136}}.
*{{citation
 | last = Turán
 | first = Paul | authorlink = Pál Turán
 | year = 1941
 | title = On an extremal problem in graph theory
 | journal = Matematikai és Fizikai Lapok
 | volume = 48
 | pages = 436–452
 | language = Hungarian
 }}
{{refend}}

==Legături externe==
*{{MathWorld|title=Clique|urlname=Clique}}
*{{MathWorld|title=Clique Number|urlname=CliqueNumber}}

[[Categorie:Teoria grafurilor]]