Enumerarea grafică

Enumerarea grafului este o categorie de  probleme de combinatorică enumerativă în care este necesară enumerarea grafurilor nedirecționate sau direcționate de anumite tipuri, de obicei în funcție de numărul de vârfuri de graf [1] . Aceste probleme pot fi rezolvate fie exact (ca problema enumerarii algebrice) sau asimptotic . Pionierii în această zonă a matematicii au fost Poya [2] , Cayley [3] și Redfield[4] .

Sarcini marcate și nemarcate

În unele probleme de enumerare a graficelor, vârfurile graficelor sunt considerate etichetate , făcându-le distinse unele de altele. În alte probleme, orice permutare a nodurilor este considerată a fi același grafic, astfel încât vârfurile sunt considerate identice sau neetichetate . În general, problemele etichetate tind să fie mai simple [1] . Teorema Redfield-Polyi este un instrument important pentru reducerea unei probleme neetichetate la una etichetată - fiecare clasă neetichetată este considerată o clasă de simetrie a obiectelor etichetate.

Formule de enumerare exactă

Câteva rezultate importante în acest domeniu.

• Numărul de grafice simple nedirecționate etichetate cu n vârfuri este 2 n ( n  − 1)/2 [5]
• Numărul de grafice simple direcționate etichetate cu n vârfuri este 2 n ( n  − 1) [6]
• Numărul C n de grafice nedirecționate etichetate conectate cu n vârfuri satisface relația recursivă [7]

• Numărul de arbori liberi etichetați cu n vârfuri este n n  − 2 ( formula lui Cayley ).
• Numărul de omizi neetichetate cu n vârfuri este [9]

Vezi și

• Teoria grafurilor algebrice
• Teoria grafurilor spectrale
• Teoria grafurilor topologice

Note

1. ↑ 12 Harary , Palmer, 1973 .
2. ↑ Polonia, 1937 , p. 145-254.
3. ↑ Arthur Cayley  (link indisponibil) A Cambridge Alumni Database . Universitatea Cambridge.
4. ↑ Redfield, 1927 , p. 433-455.
5. ↑ Harary, Palmer, 1973 , p. 3.
6. ↑ Harary, Palmer, 1973 , p. 5.
7. ↑ Harary, Palmer, 1973 , p. 7.
8. ↑ Secvența OEIS A001187 _
9. ↑ Harary, Schwenk, 1973 , p. 359–365.

Literatură

• Harary F. , Palmer E.M. Enumerare grafică. - Academic Press , 1973. - ISBN 0-12-324245-2 .
• Harari F., Palmer E. Enumeration of graphs = traducerea în limba rusă a paragrafului precedent. - Lumea , 1977.
• Harary F. , Schwenk AJ Numărul de omizi // Matematică discretă. - 1973. - T. 6 , nr. 4 . — S. 359–365 . - doi : 10.1016/0012-365x(73)90067-8 .
• Pólya G. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen  // Acta Mathematica . - 1937. - Vol. 68. - doi : 10.1007/BF02546665 .  (link indisponibil)
• Theory of group-reduced distributions // American J. Math. - 1927. - T. 49 .