Enumerare de grafuri

Î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.^[1] 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,^[2] Arthur Cayley^[3] și J. Howard Redfield.^[4]

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.^[5] 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ă,^[6] dar deoarece aproape toate grafurile sunt asimetrice, acest număr este asimptotic față de^[7] ${\frac {2^{\tbinom {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}.^[8]
Numărul de grafuri simple orientate etichetate cu n noduri este 2^n(n −1).^[9]
Numărul C_n de grafuri neorientate conexe etichetate cu n noduri satisface relația de recurență^[10]

C_{n}=2^{n \choose 2}-{\frac {1}{n}}\sum _{k=1}^{n-1}k{n \choose k}2^{n-k \choose 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, ... (Șirul A001187 la Enciclopedia electronică a șirurilor de numere întregi (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^[11]

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

Note

^ Harary, Frank; Palmer, Edgar M. (1973). Graphical Enumeration. Academic Press. ISBN 0-12-324245-2.
^ Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Math. 68 (1937), 145-254
^ Cayley, Arthur în Venn, J. & J. A., Alumni Cantabrigienses, Cambridge University Press, 10 volume, 1922–1958.
^ The theory of group-reduced distributions. American J. Math. 49 (1927), 433-455.
^ Harary și Palmer, p. 1.
^ Șirul A000088 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
^ Cameron, Peter J. (2004), „Automorphisms of graphs”, În Beineke, Lowell W.; Wilson, Robin J., Topics in Algebraic Graph Theory, Encyclopedia of Mathematics and its Applications, 102, Cambridge University Press, pp. 137–155, ISBN 0-521-80197-4
^ Harary și Palmer, p. 3.
^ Harary și Palmer, p. 5.
^ Harary și Palmer, p. 7.
^ Harary, Frank; Schwenk, Allen J. (1973), „The number of caterpillars” (PDF), Discrete Mathematics, 6 (4), pp. 359–365, doi:10.1016/0012-365x(73)90067-8 .

Bibliografie

Polya, G.; Read, R. C. (1987), Combinatorial Enumeration of Groups, Graphs and Chemical Compounds, New York, Berlin Heidelberg: Springer-Verlag
Stanley, Richard P. (1997, 1999), Enumerative Combinatorics, 1, 2, Cambridge, New York, Melbourne, Cape Town: Cambridge University Press Verificați datele pentru: |date= (ajutor)
Graham, R.L.; Groetschel, M.; Lovász, L. (1996), Handbook of Combinatorics, 1, 2, Amsterdam, Cambridge: Elsevier (North-Holland), MIT Press

Legături externe

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

[1] Harary, Frank; Palmer, Edgar M. (1973). Graphical Enumeration. Academic Press. ISBN 0-12-324245-2.

[2] Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Math. 68 (1937), 145-254

[3] Cayley, Arthur în Venn, J. & J. A., Alumni Cantabrigienses, Cambridge University Press, 10 volume, 1922–1958.

[4] The theory of group-reduced distributions. American J. Math. 49 (1927), 433-455.

[5] Harary și Palmer, p. 1.

[6] Șirul A000088 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)

[7] Cameron, Peter J. (2004), „Automorphisms of graphs”, În Beineke, Lowell W.; Wilson, Robin J., Topics in Algebraic Graph Theory, Encyclopedia of Mathematics and its Applications, 102, Cambridge University Press, pp. 137–155, ISBN 0-521-80197-4

[8] Harary și Palmer, p. 3.

[9] Harary și Palmer, p. 5.

[10] Harary și Palmer, p. 7.

[11] Harary, Frank; Schwenk, Allen J. (1973), „The number of caterpillars” (PDF), Discrete Mathematics, 6 (4), pp. 359–365, doi:10.1016/0012-365x(73)90067-8 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]