Numărul de intersecție al unui grafic este cel mai mic număr de elemente din reprezentarea unui grafic dat ca un grafic de intersecție cu mulțime finită sau, echivalent, cel mai mic număr de clicuri necesare pentru a acoperi toate marginile graficului [1] [2] [ 3] .
Fie F o familie de mulțimi (este permis să se repete mulțimi în F ). Atunci graficul de intersecție F este un grafic nedirecționat având un vârf pentru fiecare membru al lui F și o muchie între oricare două mulțimi care au o intersecție nevidă. Orice grafic poate fi reprezentat ca un grafic de intersecție [4] . Numărul de intersecție al unui grafic este cel mai mic număr k astfel încât să existe o reprezentare a unui tip pentru care unirea mulțimilor F are k elemente [1] . Problema găsirii unei reprezentări sub forma unui grafic de intersecție cu un număr dat de elemente este cunoscută ca problema găsirii bazei graficului de intersecție [5] .
O definiție alternativă a numărului de intersecție al unui grafic G este cel mai mic număr de clicuri din G ( subgrafe complete ale lui G ) care acoperă toate marginile lui G [1] [6] . Un set de clicuri cu această proprietate este numit edge clique coverage și, prin urmare, numărul de intersecții este uneori numit edge clique coverage number [7] .
Egalitatea numărului de intersecții și a numărului de acoperire a marginilor de către clicuri se dovedește „directă”. Într-o direcție, să presupunem că G este graficul de intersecție al unei familii F de mulțimi a căror unire U are k elemente. Apoi, pentru orice element x din U , submulțimea de vârfuri ale graficului G corespunzătoare mulțimilor care conțin x formează o clică - oricare două vârfuri ale acestei submulțimi sunt adiacente, deoarece mulțimile lor corespunzătoare au o intersecție nevidă care conține x . În plus, orice muchie din G este conținută într-una dintre aceste clicuri, deoarece o muchie corespunde unei intersecțiuni nevide, iar o intersecție este nevidă dacă conține cel puțin un element U . Astfel, muchiile lui G pot fi acoperite de k clicuri, câte una pentru fiecare element al lui U . În cealaltă direcție, dacă graficul G poate fi acoperit de k clicuri, atunci fiecare vârf al graficului G poate fi reprezentat printr-o mulțime de clicuri care conțin vârful [8] .
Evident, un grafic cu m muchii are un număr de intersecții care nu depășește m - orice muchie formează o clică, iar aceste clicuri acoperă împreună toate muchiile [9] .
De asemenea, este adevărat că orice graf cu n vârfuri are cel mult n 2/4 intersecții . Mai strict, muchiile oricărui graf cu n vârfuri pot fi împărțite în cel mult n 2/4 clicuri , care sunt fie muchii simple, fie triunghiuri [2] [8] . Acest lucru generalizează teorema Mantel afirmând că un graf fără triunghi are cel mult n 2/4 muchii . Pentru graficele fără triunghiuri, acoperirea optimă a clicei de margine are o clică pentru fiecare muchie și, prin urmare, numărul de intersecții este egal cu numărul de muchii [2] .
O constrângere și mai puternică este posibilă dacă numărul de muchii este strict mai mare decât n 2 /4 . Fie p numărul de perechi de vârfuri neconectate prin muchii în graficul dat G , și fie t numărul pentru care t ( t − 1) ≤ p < t ( t + 1) . Atunci numărul de intersecții ale graficului G nu depășește p + t [2] [10] .
Graficele care sunt complemente ale graficelor rare au un număr mic de intersecții — numărul de intersecții ale oricărui grafic G cu n vârfuri i nu depășește 2 e 2 ( d + 1) 2 ln n , unde e este baza logaritmului natural de , d este gradul maxim al graficului complementar G [11 ] .
Verificarea faptului că pentru un grafic G dat numărul de intersecții nu depășește un număr dat k este o problemă NP-completă [12] [13] [14] . Astfel, este o problemă dificilă NP să se calculeze numărul de intersecție al unui grafic dat.
Problema calculării numărului de intersecții este însă fix-parametric rezolvabilă . Adică, există o funcție f astfel încât, atunci când numărul de intersecții este egal cu numărul k , timpul de calcul al acestui număr nu depășește produsul lui f ( k ) cu un polinom din n . Acest lucru poate fi demonstrat observând că în grafic există cel mult 2k cartiere închise distincte . Două vârfuri aparținând aceluiași set de clicuri au aceiași vecini, iar apoi graficul format prin alegerea unui vârf pentru fiecare vecinătate închisă are același număr de intersecții ca și graficul original. Prin urmare, în timp polinomial, intrarea poate fi redusă la un nucleu mai mic cu maximum 2k vârfuri. Aplicarea algoritmului de backtracking cu timp de rulare exponențial pentru acest nucleu are ca rezultat o funcție f care este exponentul dublu al lui k [15] . Dependența dublă exponențială de k nu poate fi redusă la o simplă dependență exponențială prin extragerea unui nucleu de dimensiune polinomială până când ierarhia polinomială dispare [16] , iar dacă ipoteza timpului exponențial este corectă, dependența dublă exponențială nu poate fi evitată dacă folosim nucleu extracție sau nu [ 17] .
Algoritmi mai eficienți sunt cunoscuți pentru anumite clase speciale de grafice. Numărul de intersecții ale unui grafic de interval este întotdeauna egal cu numărul de clicuri maxime ale graficului, care pot fi calculate în timp polinomial [18] [19] . Mai general, numărul de intersecții ale graficelor cordale poate fi calculat printr-un algoritm care construiește ordinea în care sunt excluse vârfurile graficului. La fiecare pas, pentru fiecare vârf v , formăm o clică pentru vârful v și vecinii săi și excludem vârful dacă există muchii care sunt incidente cu v dar care nu sunt încă acoperite de clicuri [19] .