词条 | Graph enumeration |
释义 |
In combinatorics, an area of mathematics, graph enumeration describes a class of combinatorial enumeration problems in which one must count undirected or directed graphs of certain types, typically as a function of the number of vertices of the graph.[1] These problems may be solved either exactly (as an algebraic enumeration problem) or asymptotically. The pioneers in this area of mathematics were George Pólya,[2] Arthur Cayley [3] and John Howard Redfield.[4] Labeled vs unlabeled problemsIn some graphical enumeration problems, the vertices of the graph are considered to be labeled in such a way as to be distinguishable from each other, while in other problems any permutation of the vertices is considered to form the same graph, so the vertices are considered identical or unlabeled. In general, labeled problems tend to be easier.[5] As with combinatorial enumeration more generally, the Pólya enumeration theorem is an important tool for reducing unlabeled problems to labeled ones: each unlabeled class is considered as a symmetry class of labeled objects. Exact enumeration formulasSome important results in this area include the following.
from which one may easily calculate, for n = 1, 2, 3, ..., that the values for Cn are 1, 1, 4, 38, 728, 26704, 1866256, ...{{OEIS|id=A001187}}
References1. ^{{cite book|last1 = Harary | first1 = Frank | author1-link = Frank Harary | first2 = Edgar M. | last2 = Palmer | year = 1973| title = Graphical Enumeration | publisher = Academic Press | isbn = 0-12-324245-2}} 2. ^Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Math. 68 (1937), 145-254 3. ^{{acad|id=CLY838A|name=Cayley, Arthur}} 4. ^The theory of group-reduced distributions. American J. Math. 49 (1927), 433-455. 5. ^Harary and Palmer, p. 1. 6. ^Harary and Palmer, p. 3. 7. ^Harary and Palmer, p. 5. 8. ^Harary and Palmer, p. 7. 9. ^{{citation | last1 = Harary | first1 = Frank | author1-link = Frank Harary | last2 = Schwenk | first2 = Allen J. | issue = 4 | journal = Discrete Mathematics | pages = 359–365 | title = The number of caterpillars | volume = 6 | year = 1973 | doi=10.1016/0012-365x(73)90067-8}}. 2 : Graph enumeration|Enumerative combinatorics |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。