Clique (teoria graficelor)

K ₅ , un grafic complet. Dacă apare ca un subgraf indus al unui grafic, vârfurile sale formează o fisură de dimensiunea 5.

În teoria graficelor , o clică (sau o clică) este un set V de vârfuri într-un grafic neorientat G, astfel încât, pentru fiecare pereche de vârfuri din V, există un arc care le conectează. În mod echivalent, subgraful indus de V s-ar putea spune că este un grafic complet . Mărimea unei fisuri este definită ca numărul de vârfuri pe care le conține. Unii autori numesc fiecare subgraf complet care are dimensiunea maximă o clică ^[1] .

Problema găsirii, dacă există, a unei fisuri a unei dimensiuni fixe într-un grafic se numește problema fisurii și este completă cu NP .

Conceptul complementar cu cel de clică estesetul independent , în sensul că fiecare clică corespunde unei seturi independente din graficul complementului .

Desi studiul subgrafurilor complet merge înapoi , cel puțin la reformularea a graficului teoriei cu teoria Ramsey de Erdős & Szekeres (1935) , ^[2] termenul „clica“ vine de la Luce & Perry (1949) , care a folosit subgrafurilor complet în socială rețele pentru modelarea clicelor (în engleză clici ) ale oamenilor, adică grupuri mici de oameni care se cunosc toți. Fisurile au multe aplicații în știință și în special în bioinformatică .

Definiții

O fisură într-un grafic indirect G = ( V , E ) este un subset al setului de vârfuri C ⊆ V , astfel încât pentru fiecare două vârfuri din C , există o margine care le conectează. Acest lucru este echivalent cu a spune că subgraful indus de C este complet (în unele cazuri, termenul crack poate face referire și la subgraf).

O fisură maximă este o fisură care nu poate fi extinsă prin includerea unui alt vârf adiacent, adică o fisură care nu există exclusiv în cadrul vârfurilor unei fisuri mai mari.

O fisură maximă este o fisură de cea mai mare dimensiune posibilă într-un grafic dat. Numărul de fisură ω ( G ) al unui grafic G este numărul de vârfuri într-o fisură maximă în G. Numărul de intersecție al lui G este cel mai mic număr de fisuri care acoperă împreună toate marginile lui G.

Opusul unei clici este unset independent , în sensul că fiecare clică corespunde unei mulțimi independente din graficul complementului . Problema de acoperire a fisurilor constă în găsirea cât mai multor fisuri posibil, care să includă fiecare vârf în grafic. Un concept înrudit este un bicricca ( biclique în engleză), un subgraf bipartit complet . Dimensiunea bipartită a unui grafic este numărul minim de bicricciuri necesare pentru a acoperi toate marginile graficului.

Matematica

Rezultatele matematice referitoare la fisuri includ următoarele.

Teorema lui Turán (1941) oferă o limită inferioară mărimii unei fisuri în grafice dense . Dacă un grafic are un număr suficient de mare de muchii, acesta trebuie să conțină o clică mare. De exemplu, orice grafic cu $n$ ${\ displaystyle n}$ $n$ vârfuri și mai mult de $\scriptstyle \lfloor {\frac {n}{2}}\rfloor \cdot \lceil {\frac {n}{2}}\rceil$ ${\ displaystyle \ scriptstyle \ lfloor {\ frac {n} {2}} \ rfloor \ cdot \ lceil {\ frac {n} {2}} \ rceil}$ $\ scriptstyle \ lfloor {\ frac {n} {2}} \ rfloor \ cdot \ lceil {\ frac {n} {2}} \ rceil$ marginile trebuie să conțină o fisură cu trei vârfuri.
Teorema Ramsey Graham, Rothschild & Spencer (1990) afirmă că fiecare grafic sau graficul său complement conține o clică cu cel puțin un număr logaritmic de vârfuri.
Conform unui rezultat al lui Moon & Moser (1965) , un grafic cu 3 n vârfuri poate avea cel mult 3 ⁿ fisuri maxime. Graficele care îndeplinesc această limită sunt graficele Moon - Moser K _{3,3, ...} , un caz special al graficelor Turan care apar ca cazuri extremale ale teoremei lui Turán.
Conjectura lui Hadwiger , încă nedovedită, leagă mărimea celei mai mari clici a unui minor dintr-un grafic ( numărul lui Hadwiger ) de numărul său cromatic .
Conjectura Erdős - Faber - Lovász este o altă afirmație nedovedită care leagă colorarea graficului de fisuri.

Diferite clase importante de grafice pot fi definite prin fisurile lor:

Un grafic acordal este un grafic ale cărui vârfuri pot fi ordonate într-o ordonare perfectă de eliminare, o ordonare astfel încât vecinii fiecărui vârf v care vin după v în ordonare formează o clică.
Un cograf este un grafic ale cărui subgrafe induse au toate proprietatea că orice clică maximă intersectează orice set independent maxim la un singur vârf.
Un grafic de interval este un grafic ale cărui fisuri maxime pot fi ordonate în așa fel încât, pentru fiecare vârf v , fisurile care conțin v să fie consecutive în ordonare.
Un grafic liniar este un grafic ale cărui margini pot fi acoperite de fisuri cu marginile disjuncte în așa fel încât fiecare vârf să aparțină exact două dintre fisurile din capac.
Un grafic perfect este un grafic în care numărul fisurii este egal cu numărul cromatic din fiecare subgraf indus .
Un grafic împărțit este un grafic în care unele fisuri conțin cel puțin o extremă a fiecărei muchii.
Un grafic fără triunghiuri este un grafic care nu are fisuri distincte de vârfurile și muchiile sale.

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

Complexul fisurilor unui grafic G este un complex simplicial abstract X ( G ) cu un simplex pentru fiecare fisură din G
Un grafic simplu este un grafic indirect κ ( G ) cu un vârf pentru fiecare fisură dintr-un grafic G și o margine care leagă două fisuri care diferă de un singur vârf. Este un exemplu de grafic median și este asociat cu o algebră mediană pe fisurile unui grafic: mediana m ( A , B , C ) a trei fisuri A , B și C este fisura ale cărei vârfuri aparțin cel puțin două dintre fisurile A , B și C. ^[3]
Crack Sum este o metodă de combinare a două grafice prin fuzionarea lor de-a lungul unui crack comun.
Lățimea fisurii este o noțiune a complexității unui grafic în ceea ce privește numărul minim de etichete de vârf distincte necesare pentru a construi graficul pornind de la uniri disjuncte, operații de reetichetare și operații care conectează toate perechile de vârfuri cu etichete la locul dvs. Graficele cu o lățime de fisură de una sunt exact uniunile disjuncte ale fisurilor.
Numărul de intersecție al unui grafic este numărul minim de fisuri necesare pentru a acoperi toate marginile graficului.

Conceptele strâns legate de subgrafele complete sunt subdiviziunile graficelor complete și minorii complecți ai graficelor. În special, teorema lui Kuratowski și teorema lui Wagner caracterizează graficele plane, respectiv, prin intermediul unor subdiviziuni și minori bipartite complet interzise și complete .

Informatică

Același subiect în detaliu: Problema clică .

În informatică , problema clicii este problema de calcul a găsirii unei clici maxime, sau a tuturor clicurilor, într-un grafic dat. Este NP-complet , una dintre cele 21 de probleme ale lui Karp NP-complete ( M. Richard Karp , 1972 ). Este, de asemenea, intratabil cu parametri fixi și dificil de aproximat. Cu toate acestea, mulți algoritmi au fost dezvoltați pentru a calcula fisuri, fie operând în timp exponențial (cum ar fi algoritmul Bron-Kerbosch ), fie specializați în familii de grafice, cum ar fi grafice plane sau grafice perfecte, pentru care problema poate fi rezolvată în polinomul timpului .

Programe gratuite pentru căutarea clicii maxime

Nume	Licență	Limbajul API	Informații scurte
NetworkX	BSD	Piton	soluție aproximativă, vezi rutina max_clique ^{[ link rupt ]}
maxClique	CRAPL	Java	algoritmi exacți și instanțe DIMACS
OpenOpt	BSD	Piton	soluții exacte și aproximative, posibilitatea de a specifica nodurile care trebuie să fie inclus / exclus; vezi clasa MCP Arhivat 3 octombrie 2013 la Internet Archive . pentru mai multe detalii și exemple

Aplicații

Cuvântul „clică”, în utilizarea sa în teoria graficelor, a apărut din lucrarea lui Luce & Perry (1949) , care a folosit subgrafe pentru a modela clici (grupuri de oameni care se cunosc toți) în rețelele sociale . Pentru continuarea încercărilor de modelare a clicelor sociale din punctul de vedere al teoriei graficelor, a se vedea de ex. Alba (1973) , Peay (1974) și Doreian & Woodard (1994) .

Multe probleme bioinformatice diferite au fost modelate folosind fisuri. De exemplu, Ben-Dor, Shamir și Yakhini (1999) modelează problema grupării datelor privind expresia genelor ca fiind găsirea numărului minim de modificări necesare pentru a transforma un grafic care descrie datele într-un grafic format ca uniunea disjunctă a fisurilor; Tanay, Sharan și Shamir (2002) discută o problemă similară de bi-grupare pentru datele de expresie în care grupurile trebuie să fie clici. Sugihara (1984) folosește clici pentru a modela nișe ecologice în rețelele alimentare . Sankoff descrie problema deducerii arborilor evolutivi ca fiind găsirea fisurilor maxime într-un grafic ale cărui vârfuri sunt caracteristicile speciei, în care două vârfuri au o margine dacă există o filogenie perfectă care combină aceste două caractere. Samudrala și Moult (1998) modelează predicția structurii proteinelor ca o problemă a găsirii fisurilor într-un grafic ale cărui vârfuri reprezintă poziții ale subunităților în proteină. Și căutând fisuri într-o rețea de interacțiune proteină-proteină , Spiron și 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 clusterului. Analiza graficului de putere este o metodă de simplificare a rețelelor biologice complexe prin găsirea fisurilor și structurilor relative în aceste rețele.

În ingineria electrică , Prihar (1956) folosește clici pentru a analiza rețelele de comunicații, iar Paull , 1959 le folosește pentru a proiecta circuite eficiente pentru calculul funcțiilor booleene parțial specificate. Crăpăturile au fost, de asemenea, utilizate în generarea de programe de testare automate : o crăpătură mare într-un posibil grafic de incompatibilitate a eșecului oferă o limită inferioară pentru dimensiunea unui set de testare. ^[4] Cong1993 , Cong & Smith (1993) descriu o aplicație de fisuri pentru a găsi o partiție ierarhică a unui circuit electronic în subunități mai mici.

În chimie , Rhodes, Willett, Calvet și Dunbar (2003) folosesc fisuri pentru a descrie substanțele chimice dintr-o bază de date chimică care au un grad ridicat de asemănare cu o structură țintă. Kuhl, Crippen și Friesen (1983) folosesc fisuri pentru a modela pozițiile în care două substanțe chimice se vor lega între ele.

Notă

^ Harary, F. Teoria graficelor. Reading, MA: Addison-Wesley, 1994
^ Lucrarea anterioară a lui Kuratowski , care caracteriza graficele plane prin subgrafe bipartite complete și complete de tip interzis, a fost inițial formulată în termeni topologici, mai degrabă decât grafico-teoretici.
^ Barthélemy, Leclerc & Monjardet (1986) , p. 200.
^ Hamzaoglu și Patel (1998) .

Bibliografie

Richard D. Alba, A graph-theoretic definition of a sociical clique ( PDF ), în Rivista of Mathematical Sociology , vol. 3, nr. 1, 1973, 113–126, DOI : 10.1080 / 0022250X.1973.9989826 .
J.-P. Barthélemy, B. Leclerc și B. Monjardet, Despre utilizarea seturilor ordonate în probleme de comparație și consens de clasificări , în Rivista de clasificare , vol. 3, nr. 2, 1986, 187-224, DOI : 10.1007 / BF01894188 .
Amir Ben-Dor, Ron Shamir și Zohar Yakhini, Clustering patterns expression gene. , în Journal of Computational Biology , vol. 6, 3-4, 1999, 281-297, DOI : 10.1089 / 106652799318274 , PMID 10582567 .
Cong J. și Smith M., Un algoritm de clustering paralel de jos în sus cu aplicații pentru partiționarea circuitelor în proiectarea VLSI , în Proc. 30th International Design Automation Conference , 1993, 755–760, DOI : 10.1145 / 157485.165119 .
William HE Day și David Sankoff, Complexitatea computațională a deducerii filogeniei prin compatibilitate , în Zoologie sistematică , vol. 35, nr. 2, 1986, 224-229, DOI : 10.2307 / 2413432 , JSTOR 2413432 .
Patrick Doreian și Katherine L. Woodard, Definirea și localizarea nucleelor și limitelor rețelelor sociale , în Rețelele sociale , vol. 16, nr. 4, 1994, 267–293, DOI : 10.1016 / 0378-8733 (94) 90013-2 .
Paul Erdős și George Szekeres , O problemă combinatorie în geometrie ( PDF ), în Compositio Math. , vol. 2, 1935, 463-470.
R. Graham , B. Rothschild și JH Spencer , Teoria Ramsey , New York, John Wiley și Sons, 1990, ISBN 0-471-50046-1 .
I. Hamzaoglu și JH Patel, Test set algoritmi de compactare pentru circuite combinaționale , în Proc. 1998 IEEE / ACM International Conference on Computer-Aided Design , 1998, 283-289, DOI : 10.1145 / 288548.288615 .
Richard M. Karp , Reducibilitatea printre problemele combinatorii ( PDF ), în RE Miller și JW Thatcher (eds), Complexity of Computer Computations , New York: Plenum, 1972, 85-103.
FS Kuhl, GM Crippen și DK Friesen, Un algoritm combinatoriu pentru calcularea legării ligandului , în Journal of Computational Chemistry , vol. 5, nr. 1, 1983, 24-34, DOI : 10.1002 / jcc.540050105 .
( FR ) Kazimierz Kuratowski ,Sur le probléme des courbes gauches en Topologie ( PDF ), în Fundamenta Mathematicae , vol. 15, 1930, 271-283.
R. Duncan Luce și Albert D. Perry, O metodă de analiză matricială a structurii grupului , în Psychometrika , vol. 14, n. 2, 1949, 95–116, DOI : 10.1007 / BF02289146 , PMID 18152948 .
JW Moon și L. Moser , Despre clici în grafice , în Israel J. Math. , vol. 3, 1965, 23-28, DOI : 10.1007 / BF02760024 , MR 0182577 .
MC Paull și SH Unger, Minimizarea numărului de stări în funcțiile de comutare secvențială incomplet specificate , în IRE Trans. pe calculatoare electronice , EC-8, n. 3, 1959, 356–367, DOI : 10.1109 / TEC.1959.5222697 .
Edmund R. Peay, Structuri ierarhice de clică , în Sociometrie , vol. 37, n. 1, 1974, 54-65, DOI : 10.2307 / 2786466 , JSTOR 2786466 .
Z. Prihar, Proprietăți topologice ale rețelelor de telecomunicații , în Proceedings of the IRE , vol. 44, nr. 7, 1956, 927–933, DOI : 10.1109 / JRPROC.1956.275149 .
Nicholas Rhodes, Peter Willett, Alain Calvet, James B. Dunbar și Christine Humblet, CLIP: căutare similară a bazelor de date 3D utilizând detectarea clicelor, în Rivista of Chemical Information and Computer Sciences , vol. 43, nr. 2, 2003, 443–448, DOI : 10.1021 / ci025605o , PMID 12653507 .
Ram Samudrala și John Moult, Un algoritm grafic-teoretic pentru modelarea comparativă a structurii proteinelor , în Rivista of Molecular Biology , vol. 279, nr. 1, 1998, 287-302, DOI : 10.1006 / jmbi.1998.1689 , PMID 9636717 .
Victor Spirin și Leonid A. Mirny, Complexe proteice și module funcționale în rețele moleculare , în Proceedings of the National Academy of Sciences , vol. 100, nr. 21, 2003, 12123–12128, DOI : 10.1073 / pnas.2032324100 , PMC 218723 , PMID 14517352 .
George Sugihara, Teoria graficelor, omologia și rețelele alimentare , în Simon A. Levin (ed.), Population Biology , Proc. Symp. Aplic. Math., Vol. 30, 1984, 83-101.
Amos Tanay, Roded Sharan si Ron Shamir, Descoperirea biclusters semnificative statistic a datelor expresia genelor , în bioinformatică, voi. 18, Supliment. 1, 2002, S136 - S144, DOI : 10.1093 / bioinformatics / 18.suppl_1.S136 , PMID 12169541 .
( HU ) Paul Turán , Despre o problemă extremă în teoria graficelor , în Matematikai és Fizikai Lapok , vol. 48, 1941, 436-452.

Elemente conexe

linkuri externe

(EN) Eric W. Weisstein, Clique , în MathWorld Wolfram Research.

Portal IT

Portalul de matematică

[1] Harary, F. Teoria graficelor. Reading, MA: Addison-Wesley, 1994

[2] Lucrarea anterioară a lui Kuratowski , care caracteriza graficele plane prin subgrafe bipartite complete și complete de tip interzis, a fost inițial formulată în termeni topologici, mai degrabă decât grafico-teoretici.

[3] Barthélemy, Leclerc & Monjardet (1986) , p. 200.

[4] Hamzaoglu și Patel (1998) .

[1]

[2]

[3]

[4]