miniatura| Lista completă a tuturor arborilor liberi cu 2, 3 și 4 noduri etichetate: arbore cu 2 noduri, arbori cu 3 noduri și 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,Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Math. 68 (1937), 145-254 Arthur Cayley și J. Howard Redfield.The theory of group-reduced distributions. American J. Math. 49 (1927), 433-455.
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.Harary și Palmer, p. 1. 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 noduri nu este deocamdată cunoscut în formă închisă, dar deoarece aproape toate grafurile sunt asimetrice, acest număr este asimptotic față de
Formule de enumerare exacte Unele rezultate importante în acest domeniu includ următoarele.
Numărul de grafuri simple neorientate etichetate cu n noduri este 2n(n −1)/2.Harary și Palmer, p. 3. Numărul de grafuri simple orientate etichetate cu n noduri este 2n(n −1).Harary și Palmer, p. 5. Numărul Cn de grafuri neorientate conexe etichetate cu n noduri satisface relația de recurențăHarary și Palmer, p. 7.
din care se pot calcula cu ușurință, pentru n = 1, 2, 3, ..., valorile lui Cn. Acestea sunt 1, 1, 4, 38, 728, 26704, 1866256, ... () Numărul de arbori liberi etichetați cu n noduri este nn−2 (formula lui Cayley). Numărul de omizi neetichetate cu n noduri este.
Note
Bibliografie
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
Categorie:Teoria grafurilor