Clic (teoria grafurilor)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 11 aprilie 2022; verificările necesită 4 modificări .

O clică a unui graf nedirecționat este un subset al vârfurilor sale, dintre care două sunt conectate printr-o muchie. Clicile sunt unul dintre conceptele de bază ale teoriei grafurilor și sunt folosite în multe alte probleme matematice și construcții de grafuri. Clicile sunt, de asemenea, studiate în informatică  - problema de a determina dacă există o clică de o dimensiune dată într-un grafic ( problema Cliquei ) este NP-complet . În ciuda acestei dificultăți, mulți algoritmi pentru găsirea clicurilor sunt în curs de studiu.

Deși studiul subgrafelor complete a început cu formularea teoremei lui Ramsey în termenii teoriei grafurilor de către Erdős și Székeres [1] [2] . Termenul de „clică” provine din lucrările lui Luc și Peri [3] , care au folosit subgrafe complete atunci când studiau rețelele sociale pentru a modela clicuri de oameni , adică grupuri de oameni care se cunosc [4] . Click-urile au multe alte aplicații în știință și în special în bioinformatică .

Definiții

O clică într- un graf nedirecționat este un subset de vârfuri astfel încât pentru oricare două vârfuri din există o muchie care le conectează. Acest lucru este echivalent cu a spune că subgraful generat de este complet .

O clică maximă  , sau clică maximă prin includere , este o clică care nu poate fi extinsă prin adăugarea de vârfuri la ea. Cu alte cuvinte, acest grafic nu conține o clică mai mare căreia îi aparține.

Cea mai mare clică  sau clică care are dimensiunea maximă este clica cu dimensiunea maximă pentru graficul dat.

Numărul clicei al unui grafic  este numărul de vârfuri din cea mai mare clică a graficului . Numărul de intersecție al unui grafic  este cel mai mic număr de clicuri care acoperă împreună toate marginile graficului .

Opusul unei clici este o multime independenta in sensul ca fiecare clica corespunde unei multimi independente din graficul complementar . Problema acoperirii clicurilor este de a găsi cel mai mic număr posibil de clicuri care conțin toate vârfurile graficului.

Un termen înrudit  este biclique, un subgraf complet bipartit . Dimensiunea bipartită a unui grafic este numărul minim de biclicuri necesare pentru a acoperi toate marginile graficului.

Matematică

Rezultatele matematice privind clicurile includ următoarele.

• Teorema lui Turan [5] dă o limită inferioară a numărului de clicuri din graficele dense . Dacă un grafic are suficiente muchii, trebuie să conțină o clică. De exemplu, orice grafic cu vârfuri și mai mult decât muchii trebuie să aibă o clică de trei vârfuri.
• Teorema lui Ramsey [6] afirmă că orice graf sau graful său complementar conține o clică cu cel puțin un număr logaritmic de vârfuri.
• Conform rezultatelor lui Moon și Moser [7] , un grafic cu vârfuri poate conține maximum cele mai mari clicuri. Graficele care satisfac această limită sunt grafice Moon-Moser ,  un caz special de grafice Turan care apar ca un caz extrem al teoremei lui Turan.
• Conjectura Hadwiger , care rămâne nedovedită, leagă dimensiunea celei mai mari clicuri a unui minor dintr-un grafic (numărul său Hadwiger ) de numărul cromatic .
• Conjectura Erdős-Faber-Lovas  este o altă afirmație nedovedită despre relația dintre colorarea graficelor și clicuri.

Unele clase de grafice importante pot fi definite prin clicurile lor:

• Un graf cordal  este un graf ale cărui vârfuri pot fi ordonate în ordinea eliminării perfecte; ordinea în care vecinii fiecărui vârf vin după vârf .
• Un cograf  este un graf, ale cărui subgrafe generate au proprietatea că orice clică cea mai mare intersectează orice cea mai mare mulțime independentă la un singur vârf.
• Un grafic de interval  este un grafic ale cărui clicuri cele mai mari pot fi ordonate în așa fel încât pentru orice vârf , clicurile care conțin , merg secvenţial.
• Un graf cu linii  este un graf ale cărui muchii pot fi acoperite de clicuri fără margini comune, în plus, fiecare vârf va aparține exact două clicuri.
• Un grafic perfect  este un grafic în care numărul clicei este egal cu numărul cromatic din fiecare subgraf generat .
• Un grafic divizat  este un grafic în care un set de clicuri conține cel puțin un vârf de la fiecare muchie.
• Un grafic fără triunghiuri  este un grafic în care nu există alte clicuri în afară de vârfuri și muchii.

În plus, multe alte construcții matematice implică clicuri grafice. Printre ei:

• Colecția de clicuri a unui grafic este o colecție abstractă simplex cu un simplex pentru fiecare clică în;
• Un graf simplex  este un graf nedirecționatcu vârfuri pentru fiecare clică din graficși muchii care conectează două clicuri care diferă cu un vârf. Acest grafic este un exemplu de grafic median și este legat de algebra medianelor pe clicurile graficului — mediana atreiclicuriși este o clică ale cărei vârfuri aparțin a cel puțin două clicuri din,și [8] ;
• Suma la clic  este o metodă de a combina două grafice prin îmbinarea lor la clic;
• Lățimea clicului  este o categorie de complexitate a graficului în ceea ce privește numărul minim de etichete distincte de vârfuri necesare pentru a construi un grafic din seturi disparate folosind operații de marcare și operații de îmbinare pentru toate perechile de vârfuri cu aceeași etichetă. Graficele cu o lățime de clic de unu sunt exact seturi disparate de clicuri;
• Numărul de intersecție a graficului este numărul minim de clicuri necesare pentru a acoperi toate marginile graficului.

Un concept apropiat de subgrafele complete este împărțirea graficelor în subgrafe complete și minore de grafice complete . În special, teorema lui Kuratowski și teorema lui Wagner caracterizează grafurile plane interzicând subgrafele bipartite complete și, respectiv, minore.

Informatica

În informatică , problema clicei  este problema de calcul de a găsi clica sau clicurile maxime într-un grafic dat. Problema este NP-complet , una dintre cele 21 de probleme NP-complete ale lui Karp [9] . De asemenea, este dificil pentru aproximarea parametrică și dificil de aproximat . Cu toate acestea, au fost dezvoltați mulți algoritmi de clică care fie rulează în timp exponențial (cum ar fi algoritmul Bron-Kerbosch ), fie sunt specializați în familii de grafuri, cum ar fi grafurile plane sau grafurile perfecte , pentru care problema poate fi rezolvată în timp polinomial .

Software gratuit pentru găsirea clicei maxime

Mai jos este o listă de software gratuit pentru a găsi clica maximă.

Nume	Licență	Limbajul API	scurta descriere
NetworkX	BSD	Piton	soluție aproximativă, vezi procedura max_clique  (link descendent)
maxClique	CRPL	Java	algoritmi exacti, implementari DIMACS Arhivat 23 septembrie 2015 la Wayback Machine
openopt	BSD	Piton	soluții exacte și aproximative, capacitatea de a specifica marginile care urmează să fie incluse ( MCP )

Aplicație

Multe probleme de bioinformatică diferite sunt modelate cu clicuri. De exemplu, Ben-Dor, Shamir și Yahini [10] au modelat problema grupării expresiei genelor ca problema de a găsi numărul minim de modificări necesare pentru a transforma un grafic de date într-un grafic format din seturi deconectate de clicuri. Tanay, Sharan și Shamir [11] discută o problemă similară de biclustering a datelor despre expresia genelor, în care clusterele trebuie să fie clicuri. Sugihara [12] a folosit clicuri pentru a modela nișe ecologice în lanțurile trofice . Day și Sankow [13] descriu problema descrierii arborilor evoluționari ca fiind problema găsirii clicurilor maxime într-un grafic în care vârfurile reprezintă caracteristici și două vârfuri sunt conectate printr-o muchie dacă există o istorie de dezvoltare ideală care le combină . doua caracteristici. Samudrala și Molt [14] au modelat predicția structurii proteinei ca o problemă de găsire a clicurilor într-un grafic ale cărui vârfuri reprezintă pozițiile părților proteinelor și prin căutarea clicurilor în schema de interacțiune proteină-proteină . Spirit și Mirni [15] au descoperit grupuri de proteine ​​care interacționează strâns unele cu altele și au puține interacțiuni în afara clusterului. Analiza cardinalității grafice  este o metodă de simplificare a sistemelor biologice complexe prin găsirea clicurilor și a structurilor aferente în aceste sisteme.

În inginerie electrică , Prihar [16] a folosit clicuri pentru a analiza rețelele de comunicații, iar Paul și Unger [17] le-au folosit pentru a dezvolta circuite eficiente pentru calcularea funcțiilor booleene parțial definite. Clicuri sunt, de asemenea, folosite în generarea automată a modelelor de testare  - o clică mare în graficul de incompatibilitate a posibilelor defecte oferă o limită inferioară a setului de teste [18] . Kong și Smith [19] descriu utilizarea clicurilor pentru a căuta structuri ierarhice în circuitele electrice.

În chimie , Rhodes și colaboratorii [20] au folosit clicuri pentru a descrie compuși chimici dintr-o bază de date chimică care au un grad ridicat de similitudine. Kuhl, Kripen și Friesen [21] au folosit clicuri pentru a modela pozițiile în care doi compuși chimici se leagă unul de celălalt.

Vezi și

• Complexul steagului

Note

1. ↑ Erdős, Szekeres, 1935 .
2. ↑ Lucrările anterioare ale lui Kazimir Kuratowski Kuratowski, 1930 privind caracterizarea grafurilor plane prin interzicerea subgrafelor bipartite complete și complete sunt formulate mai degrabă în termeni topologici decât în ​​termeni de teoria grafurilor
3. ↑ Luce, Perry, 1949 .
4. ↑ Pentru lucrări suplimentare în modelarea clicurilor sociale folosind teoria grafurilor, vezi Alba Alba, 1973 , Pius Peay, 1974 și Dorian și Woodard Doreian, Woodard, 1994.
5. ↑ Turan, 1941 .
6. ↑ Graham, Rothschild, Spencer, 1990 .
7. ↑ Moon, Moser, 1965 .
8. ↑ J.-P. Barthelemy, B. Leclerc, B. Monjardet. Despre utilizarea multimilor ordonate in probleme de comparatie si consens de clasificari // Journal of Classification. - 1986. - T. 3 , nr. 2 . - S. 200 . - doi : 10.1007/BF01894188 .
9. ↑ Karp, 1972 .
10. ↑ Ben-Dor, Shamir, Yakhini, 1999 .
11. ↑ Tanay, Sharan, Shamir, 2002 .
12. ↑ Sugihara, 1984 .
13. ↑ Day, Sankoff, 1986 .
14. ↑ Samudrala, Moult, 1998 .
15. ↑ Spirin, Mirny, 2003 .
16. ↑ Prihar, 1956 .
17. ↑ Paull, Unger, 1959 .
18. ↑ I. Hamzaoglu, JH Patel. Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design. - 1998. - S. 283-289 . doi : 10.1145 / 288548.288615 .
19. ↑ Cong, Smith, 1993 .
20. ↑ Rhodos, Willett, Calvet, Dunbar, Humblet, 2003 .
21. ↑ Kuhl, Crippen, Friesen, 1983 .

Literatură

• Paul Erdős, George Szekeres. O problemă combinatorică în geometrie // Compositio Math. - 1935. - T. 2 . - S. 463-470 .
• Luce R. Duncan, Albert D. Perry. O metodă de analiză matriceală a structurii grupului // Psihometrie. - 1949. - Vol. 2 , numărul. 14 . - S. 95-116 . - doi : 10.1007/BF02289146 . — PMID 18152948 .
• Moon, JW, Leo Moser. Pe clicuri în grafice // Israel J. Math .. - 1965. - T. 3 . — S. 23–28 . - doi : 10.1007/BF02760024 .
• Ronald Graham, B. Rothschild, Joel Spencer. Teoria Ramsey. - New York: John Wiley and Sons, 1990. - ISBN 0-471-50046-1 .
• Paul Turan. Despre o problemă extremă în teoria grafurilor  (maghiară)  // Matematikai és Fizikai Lapok. - 1941. - T. 48 . - S. 436-452 .
• Richard D. Alba. O definiție teoretică grafică a unei cliche sociometrice // Journal of Mathematical Sociology. - 1973. - T. 3 , nr. 1 . - S. 113-126 . - doi : 10.1080/0022250X.1973.9989826 .
• Edmund R. Peay. Structuri de clică ierarhică // Sociometrie. - 1974. - T. 37 , nr. 1 . - S. 54-65 . - doi : 10.2307/2786466 . — .
• Patrick Doreian, Katherine L. Woodard. Definirea și localizarea nucleelor ​​și limitelor rețelelor sociale // Rețelele sociale. - 1994. - T. 16 , nr. 4 . - S. 267-293 . - doi : 10.1016/0378-8733(94)90013-2 .
• Richard M. Karp. Complexitatea calculelor computerizate / RE Miller, JW Thatcher. - New York: Plenum, 1972. - p. 85–103 .
• Amir Ben-Dor, Ron Shamir, Zohar Yakhini. Clustering gene expression patterns // Journal of Computational Biology. - 1999. - V. 6 , nr. 3-4 . - S. 281-297 . doi : 10.1089 / 106652799318274 . — PMID 10582567 .
• Amos Tanay, Roded Sharan, Ron Shamir. Descoperirea de biclustere semnificative statistic în datele despre expresia genelor // Bioinformatică. - 2002. - T. 18 , nr. Suppl. 1 . - S. S136-S144 . - doi : 10.1093/bioinformatics/18.suppl_1.S136 . — PMID 12169541 .
• George Sugihara. Biologia populației / editor: Simon A. Levin. - 1984. - T. 30 . - S. 83-101 .
• William HE Day, David Sankoff. Complexitatea computațională a deducerii filogeniilor prin compatibilitate // Zoologie sistematică. - 1986. - T. 35 , nr. 2 . - S. 224-229 . - doi : 10.2307/2413432 . — .
• Ram Samudrala, John Moult. Un algoritm teoretic grafic pentru modelarea comparativă a structurii proteinelor // Journal of Molecular Biology. - 1998. - T. 279 , nr. 1 . - S. 287-302 . - doi : 10.1006/jmbi.1998.1689 . — PMID 9636717 .
• Victor Spirin, Leonid A. Mirny. Complexe de proteine ​​și module funcționale în rețele moleculare // Proceedings of the National Academy of Sciences . - 2003. - T. 100 , nr. 21 . - S. 12123-12128 . - doi : 10.1073/pnas.2032324100 . — PMID 14517352 .
• Z. Prihar. Proprietățile topologice ale rețelelor de telecomunicații // Proceedings of the IRE . - 1956. - T. 44 , nr. 7 . - S. 927-933 . - doi : 10.1109/JRPROC.1956.275149 .
• MC Paull, SH Unger. Minimizarea numărului de stări în funcțiile de comutare secvenţială incomplet specificate. - 1959. - Vol. EC-8. - Problemă. 3 . - S. 356-367 . - doi : 10.1109/TEC.1959.5222697 .
• J. Cong, M. Smith. Proc. A 30-a Conferință Internațională de Automatizare a Designului. - 1993. - S. 755-760 . - doi : 10.1145/157485.165119 .
• Nicholas Rhodes, Peter Willett, Alain Calvet, James B. Dunbar, Christine Humblet. CLIP: căutarea similarității bazelor de date 3D folosind detectarea clicurilor // Journal of Chemical Information and Computer Sciences. - 2003. - T. 43 , nr. 2 . - S. 443-448 . - doi : 10.1021/ci025605o . — PMID 12653507 .
• FS Kuhl, GM Crippen, DK Friesen. Un algoritm combinatoriu pentru calcularea legării ligandului // Journal of Computational Chemistry. - 1983. - V. 5 , nr. 1 . — S. 24–34 . - doi : 10.1002/jcc.540050105 .
• Kazimierz Kuratowski. Sur le probleme des courbes gauches en Topologie  (franceză)  // Fundamenta Mathematicae. - 1930. - T. 15 . - S. 271-283 .

Link -uri

• Weisstein, Eric W. Clique  (engleză) pe site-ul Wolfram MathWorld .
• Weisstein, Eric W. Clique Number  (engleză) pe site-ul web Wolfram MathWorld .