Clică

În domeniul matematic al teoriei grafurilor, o clică este o submulțime de noduri ale unui graf neorientat cu proprietatea că subgraful indus de ele este 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-completă, dar în ciuda acestui rezultat ce relevă dificultatea problemei, s-au studiat mulți algoritmi pentru găsirea de clici.

Un graf cu

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

Deși studiul subgrafurilor complete datează cel puțin de la reformularea teoriei lui Ramsey în termeni de teoria grafurilor de către Erdős & Szekeres (1935), termenul de clică vine de la Luce & Perry (1949), care au folosit subgrafurile complete în rețelele sociale pentru a modela clici^⁠(d) 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 neorientat G = (V, E) este o submulțime de noduri, C ⊆ V, astfel încât fiecare două noduri distincte sunt adiacente. Acest lucru este echivalent cu condiția ca 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.

Numărul de intersecție^⁠(d) 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.

Opusul conceptului de clică este cel de mulțime independentă, în sensul că fiecare clică corespunde unei mulțimi independente în graful complementar^⁠(d). Problema acoperirii de clică^⁠(d) 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 subgraf bipartit complet^⁠(d). Dimensiunea bipartită^⁠(d) 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:

• Teorema lui Turán^⁠(d) dă o limită inferioară^⁠(d) cu privire la dimensiunea unei clici în grafuri dense^⁠(d). Dacă un graf are suficient de multe margini, acesta trebuie să conțină o clică mare. De exemplu, fiecare graf cu n noduri și mai mult de $\scriptstyle \lfloor {\frac {n}{2}}\rfloor \cdot \lceil {\frac {n}{2}}\rceil$ muchii trebuie să conțină clici cu cel puțin trei noduri.
• Teorema lui Ramsey^⁠(d) afirmă că orice graf sau graful său complementar^⁠(d) conține o clică cu cel puțin un număr logaritmic de noduri.
• Potrivit unui rezultat al lui Moon & Moser (1965), un graf cu 3n noduri poate avea cel mult 3ⁿ clici maximale. Grafurile care îndeplinesc această limită sunt grafurile Luna–Moser K_3,3,..., un caz special de grafuri Turán^⁠(d) care rezultă drept cazuri extreme în teorema lui Turán.
• Conjectura lui Hadwiger^⁠(d), încă nedemonstrată, leagă dimensiunea celui mai mare minor de clică într-un graf (numărul Hadwiger^⁠(d)) de 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 graf cluster^⁠(d) este un graf ale cărui componente conexe sunt clici.
• Un graf bloc^⁠(d) este un graf ale cărui componente biconexe^⁠(d) sunt clici.
• Un graf cordal^⁠(d) este un graf ale cărui noduri pot fi ordonate într-o ordine perfectă de eliminare, astfel încât vecinii^⁠(d) fiecărui nod v care vin mai târziu decât v în ordonare formează o clică.
• Un cograf^⁠(d) este un graf ale cărui subgrafuri induse au proprietatea că orice clică maximală intersectează orice mulțime independentă maximală^⁠(d) într-un singur nod.
• Un graf de intervale^⁠(d) 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 graf linie^⁠(d) 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 graf perfect^⁠(d) este un graf în care numărul de clică este egal cu numărul cromatic în orice subgraf indus.
• Un graf împărțit^⁠(d) este un graf în care o clică conține cel puțin o extremitate a fiecărei muchii.
• Un graf fără triunghiuri^⁠(d) 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,

• Complexul de clică^⁠(d) al unui graf G este un complex abstract simplicial^⁠(d) 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 graf median^⁠(d), și este asociat cu o algebră mediană^⁠(d) 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.
• Suma de clică^⁠(d) este o metodă de combinare a două grafuri prin comasarea lor de-a lungul unei clici comune.
• Lățimea de clică^⁠(d) 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.
• Numărul de intersecție^⁠(d) al unui graf este numărul minim de clici necesare pentru a acoperi toate muchiile grafului.
• Graful de clici^⁠(d) al unui graf este graful de intersecție^⁠(d) al clicilor lui maximale.

Concepte strâns legate de subgrafurile complete sunt subdiviziunile^⁠(d) de grafuri complete și minorii compleți de graf^⁠(d). În special, teorema lui Kuratowski^⁠(d) și teorema lui Wagner^⁠(d) caracterizează grafurile planare prin subdiviziunile și minorii interziși compleți și, respectiv, bipartiți compleți^⁠(d).

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-completă, una dintre cele 21 de probleme NP-complete ale lui Karp. Este și netractabilă în parametru fix^⁠(d) și greu de aproximat^⁠(d). Cu toate acestea, s-au dezvoltat mulți algoritmi pentru calculul clicilor, care fie rulează în timp exponențial (cum ar fi algoritmul Bron–Kerbosch^⁠(d)) fie se specializează pe familii de grafuri, cum ar fi grafurile planare sau grafurile perfecte^⁠(d) pentru care problema poate fi rezolvată în timp polinomial.

Aplicații

Cuvântul „clică”, în utilizarea sa din teoria grafurilor, provine din lucrările lui Luce & Perry (1949), care au folosit subgrafurile complete pentru a modela clici^⁠(d) (grupări de oameni care se cunosc) în rețelele sociale. Pentru continuarea eforturilor de a modela clicile sociale în teoria grafurilor, vedeți, de exemplu, Alba (1973), Peay (1974), și Doreian & Woodard (1994).

Multe probleme diferite de bioinformatică au fost modelate folosind clici. De exemplu, 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; Tanay, Sharan & Shamir (2002) discută o problemă similară de Biclustering^⁠(d) pentru date de expresie în care clusterele sunt obligatoriu clici. Sugihara (1984) folosește clicile pentru a modela nișe ecologice în rețele trofice. Day & Sankoff (1986) descrie problema deducției 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. 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ă, 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 ingineria electrică, Prihar (1956) folosește clicile pentru a analiza rețelele de comunicații, și 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. 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, Rhodes et al. (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ă. Kuhl, Crippen & Friesen (1983) utilizează clicile pentru a modela pozițiile în care două substanțe chimice se vor lega una de alta.

Bibliografie

• 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, arhivat din original (PDF) la 3 mai 2011, accesat în 15 iunie 2017 .
• 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, doi:10.1089/106652799318274, PMID 10582567 .
• Chang, Maw-Shang; Kloks, Ton; Lee, Chuan-Min (2001), „Maximum clique transversals”, Graph-theoretic concepts in computer science (Boltenhagen, 2001), Lecture Notes in Comput. Sci., 2204, Springer, Berlin, pp. 32–43, doi:10.1007/3-540-45477-2_5, MR 1905299 .
• Cong, J.; Smith, M. (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, doi:10.2307/2413432, JSTOR 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 Mathematica, 2: 463–470 .
• Graham, R.; Rothschild, B.; Spencer, J. H. (1990), Ramsey Theory, New York: John Wiley and Sons, ISBN 0-471-50046-1 .
• 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”, În Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (PDF), New York: Plenum, pp. 85–103, arhivat din original (PDF) la 29 iunie 2011, accesat în 15 iunie 2017 .
• 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 (în French), 15: 271–283 Mentenanță CS1: Limbă nerecunoscută (link) .
• Luce, R. Duncan; Perry, Albert D. (1949), „A method of matrix analysis of group structure”, Psychometrika, 14 (2): 95–116, doi:10.1007/BF02289146, PMID 18152948 .
• Moon, J. W.; Moser, L. (1965), „On cliques in graphs”, Israel J. Math., 3: 23–28, doi:10.1007/BF02760024, MR 0182577 .
• 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, doi:10.2307/2786466, JSTOR 2786466 .
• Prihar, Z. (1956), „Topological properties of telecommunications networks”, Proceedings of the IEEE^⁠(d), 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, doi:10.1021/ci025605o, PMID 12653507 .
• Samudrala, Ram; Moult, John (1998), „A graph-theoretic algorithm for comparative modeling of protein structure”, Journal of Molecular Biology, 279 (1): 287–302, doi:10.1006/jmbi.1998.1689, PMID 9636717 .
• 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, doi:10.1073/pnas.2032324100, PMC 218723 , PMID 14517352 .
• Sugihara, George (1984), „Graph theory, homology and food webs”, În 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, doi:10.1093/bioinformatics/18.suppl_1.S136, PMID 12169541 .
• Turán, Paul (1941), „On an extremal problem in graph theory”, Matematikai és Fizikai Lapok (în Hungarian), 48: 436–452 Mentenanță CS1: Limbă nerecunoscută (link)

Legături externe

• Eric W. Weisstein, Clique la MathWorld.
• Eric W. Weisstein, Clique Number la MathWorld.