Clică (Matematică)

Un graf cu Format:Bulleted list 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 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.

Deși studiul subgrafurilor complete datează cel puțin de la reformularea teoriei lui Ramsey în termeni de teoria grafurilor de către Format:Harvtxt, termenul de clică vine de la Format:Harvtxt, care au folosit subgrafurile complete în rețelele sociale pentru a modela 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 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.

Format:Ill-wd 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.Format:Sfnp

Opusul conceptului de clică este cel de mulțime independentă, în sensul că fiecare clică corespunde unei mulțimi independente în Format:Ill-wd. Problema Format:Ill-wd 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 Format:Ill-wd. Format:Ill-wd 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:

• Format:Ill-wd dă o Format:Ill-wd cu privire la dimensiunea unei clici în Format:Ill-wd.Format:Sfnp Dacă un graf are suficient de multe margini, acesta trebuie să conțină o clică mare. De exemplu, fiecare graf cu Format:Math noduri și mai mult de $\lfloor \frac{n}{2}\rfloor \cdot \lceil \frac{n}{2}\rceil$ muchii trebuie să conțină clici cu cel puțin trei noduri.
• Format:Ill-wd afirmă că orice graf sau Format:Ill-wd conține o clică cu cel puțin un număr logaritmic de noduri.Format:Sfnp
• Potrivit unui rezultat al lui Format:Harvtxt, 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 Format:Ill-wd care rezultă drept cazuri extreme în teorema lui Turán.
• Format:Ill-wd, încă nedemonstrată, leagă dimensiunea celui mai mare minor de clică într-un graf (Format:Ill-wd) 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 Format:Ill-wd este un graf ale cărui componente conexe sunt clici.
• Un Format:Ill-wd este un graf ale cărui Format:Ill-wd sunt clici.
• Un Format:Ill-wd este un graf ale cărui noduri pot fi ordonate într-o ordine perfectă de eliminare, astfel încât Format:Ill-wd fiecărui nod v care vin mai târziu decât v în ordonare formează o clică.
• Un Format:Ill-wd este un graf ale cărui subgrafuri induse au proprietatea că orice clică maximală intersectează orice Format:Ill-wd într-un singur nod.
• Un Format:Ill-wd 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 Format:Ill-wd 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 Format:Ill-wd este un graf în care numărul de clică este egal cu numărul cromatic în orice subgraf indus.
• Un Format:Ill-wd este un graf în care o clică conține cel puțin o extremitate a fiecărei muchii.
• Un Format:Ill-wd 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,

• Format:Ill-wd al unui graf G este un Format:Ill-wd 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 Format:Ill-wd, și este asociat cu o Format:Ill-wd 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.
• Format:Ill-wd este o metodă de combinare a două grafuri prin comasarea lor de-a lungul unei clici comune.
• Format:Ill-wd 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.
• Format:Ill-wd al unui graf este numărul minim de clici necesare pentru a acoperi toate muchiile grafului.
• Format:Ill-wd al unui graf este Format:Ill-wd al clicilor lui maximale.

Concepte strâns legate de subgrafurile complete sunt Format:Ill-wd de grafuri complete și Format:Ill-wd. În special, Format:Ill-wd și Format:Ill-wd caracterizează grafurile planare prin subdiviziunile și minorii interziși compleți și, respectiv, Format:Ill-wd.

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.Format:Sfnp Este și Format:Ill-wd și Format:Ill-wd. Cu toate acestea, s-au dezvoltat mulți algoritmi pentru calculul clicilor, care fie rulează în timp exponențial (cum ar fi Format:Ill-wd) fie se specializează pe familii de grafuri, cum ar fi grafurile planare sau Format:Ill-wd 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 Format:Harvtxt, care au folosit subgrafurile complete pentru a modela clici (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, Format:Harvtxt, Format:Harvtxt, și Format:Harvtxt.

Multe probleme diferite de bioinformatică au fost modelate folosind clici. De exemplu, Format:Harvtxt 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; Format:Harvtxt discută o problemă similară de Format:Ill-wd pentru date de expresie în care clusterele sunt obligatoriu clici. Format:Harvtxt folosește clicile pentru a modela nișe ecologice în rețele trofice. Format:Harvtxt 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. Format:Harvtxt 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ă, Format:Harvtxt 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ă, Format:Harvtxt folosește clicile pentru a analiza rețelele de comunicații, și Format:Harvtxt 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. Format:Harvtxt descrie o aplicație a clicilor în găsirea unei partiții ierarhice a unui circuit electronic în subunități mai mici.

În chimie, Format:Harvtxt 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ă. Format:Harvtxt utilizează clicile pentru a modela pozițiile în care două substanțe chimice se vor lega una de alta.

Bibliografie

• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation

Legături externe

• Format:MathWorld
• Format:MathWorld