Enumerare de grafuri

Lista completă a tuturor arborilor liberi cu 2, 3 și 4 noduri etichetate: $2^{2-2}=1$ arbore cu 2 noduri, $3^{3-2}=3$ arbori cu 3 noduri și $4^{4-2}=16$ arbori cu 4 noduri.

În combinatorică, un domeniu al matematicii, enumerarea de grafuri descrie o clasă de probleme de enumerare combinatorială în care trebuie numărate grafurile orientate sau neorientate de anumite tipuri, de obicei ca o funcție de numărul de noduri ale grafului. Aceste probleme pot fi rezolvate fie exact (drept problemă de enumerare algebrică), fie asimptotic. Pionierii în acest domeniu al matematicii au fost George Pólya, Arthur Cayley și J. Howard Redfield.

Probleme etichetate vs neetichetate

În unele probleme de enumerare de grafuri, nodurile grafului sunt considerate a fi etichetate astfel încât să se poată distinge unele de altele, în timp ce în alte probleme se consideră că orice permutare a nodurilor formează același graf, deci nodurile sunt considerate identice sau neetichetate. În general, problemele etichetate tind să fie mai ușoare. Ca și în cazul enumerării combinatoriale în general, teorema de enumerare a lui Pólya este un instrument important pentru reducerea problemelor neetichetate la cele etichetate: fiecare clasă neetichetată este considerată o clasă de simetrie a obiectelor etichetate.

Numărul de grafuri neetichetate cu $n$ noduri nu este deocamdată cunoscut în formă închisă, dar deoarece aproape toate grafurile sunt asimetrice, acest număr este asimptotic față de $$\frac{2^{(\genfrac{}{}{0ex}{}{n}{2})}}{n!}.$$

Formule de enumerare exacte

Unele rezultate importante în acest domeniu includ următoarele.

• Numărul de grafuri simple neorientate etichetate cu n noduri este 2^{n(n −1)/2}.
• Numărul de grafuri simple orientate etichetate cu n noduri este 2^n(n −1).
• Numărul C_n de grafuri neorientate conexe etichetate cu n noduri satisface relația de recurență

$C_n=2^{(\genfrac{}{}{0ex}{}{n}{2})}-\frac{1}{n}\sum _{k=1}^{n-1}k(\genfrac{}{}{0ex}{}{n}{k})2^{(\genfrac{}{}{0ex}{}{n-k}{2})}{C}_k,$

din care se pot calcula cu ușurință, pentru n = 1, 2, 3, ..., valorile lui C_n. Acestea sunt

1, 1, 4, 38, 728, 26704, 1866256, ... (Format:OEIS)

• Numărul de arbori liberi etichetați cu n noduri este nⁿ⁻² (formula lui Cayley).
• Numărul de omizi neetichetate cu n noduri este

$2^{n-4}+2^{\lfloor (n-4)/2\rfloor }.$

Bibliografie

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

Legături externe

Diverse grupuri de cercetare au furnizat baze de date care listează grafuri de dimensiuni mici cu anumite proprietăți. De exemplu

• The House of Graphs
• Small Graph Database