Перечисление графов

Перечисление графов — категория задач перечислительной комбинаторики, в которых нужно пересчитать неориентированные или ориентированные графы определённых типов, как правило, в виде функции от числа вершин графа[1]. Эти задачи могут быть решены либо точно (как задача алгебраического перечисления) или асимптотически. Пионерами в этой области математики были Пойа[2], Кэли[3] и Редфилд[4].

Полный список всех деревьев с 2,3 и 4 помеченными вершинами:

2^{2-2}=1

дерево с 2 вершинами,

3^{3-2}=3

дерева с 3 вершинами и

4^{4-2}=16

деревьев с 4 вершинами.

Помеченные и непомеченные задачи

В некоторых задачах перечисления графов вершины графов считаются помеченными, делая их отличимыми друг от друга. В других задачах любая перестановка вершин считается тем же графом, так что вершины считаются идентичными или непомеченными. В общем случае, помеченные задачи, как правило, оказываются проще[1]. Теорема Редфилда — Пойи является важным средством для сведения непомеченной задачи к помеченной — каждый непомеченный класс считается классом симметрии помеченных объектов.

Точные формулы перечисления

Некоторые важные результаты в этой области.

Число помеченных простых неориентированных графов с n вершинами равно 2^{n(n − 1)/2}[5]
Число помеченных простых ориентированных графов с n вершинами равно 2^n(n − 1)[6]
Число C_n связных помеченных неориентированных графов с n вершинами удовлетворяет рекуррентному соотношению[7]

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}.

из которого можно легко вычислить для n = 1, 2, 3, …, что значения C_n равны[8]:

1, 1, 4, 38, 728, 26704, 1866256, …

Число помеченных свободных деревьев с n вершинами равно n^n − 2 (формула Кэли).
Число непомеченных гусениц с n вершинами равно[9]

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

См. также

Примечания

Harary, Palmer, 1973.
Pólya, 1937, с. 145—254.
Arthur Cayley (недоступная ссылка) A Cambridge Alumni Database. University of Cambridge.
Redfield, 1927, с. 433—455.
Harary, Palmer, 1973, с. 3.
Harary, Palmer, 1973, с. 5.
Harary, Palmer, 1973, с. 7.
последовательность A001187 в OEIS
Harary, Schwenk, 1973, с. 359–365.

Литература

Harary F., Palmer E. M. Graphical Enumeration. — Academic Press, 1973. — ISBN 0-12-324245-2.
Харари Ф., Палмер Э. Перечисление графов = русский перевод предыдущего пункта. — Мир, 1977.
Harary F., Schwenk A. J. The number of caterpillars // Discrete Mathematics. — 1973. — Т. 6, вып. 4. — С. 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. (недоступная ссылка)
The theory of group-reduced distributions // American J. Math. — 1927. — Т. 49.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[_7eeda987f27d18f1-1] Harary, Palmer, 1973.

[_bc7571b89bf36398-2] Pólya, 1937, с. 145—254.

[3] Arthur Cayley (недоступная ссылка) A Cambridge Alumni Database. University of Cambridge.

[_3a1fd16f1096eb37-4] Redfield, 1927, с. 433—455.

[_2af003010a9161b0-5] Harary, Palmer, 1973, с. 3.

[_2af003010a9161b6-6] Harary, Palmer, 1973, с. 5.

[_2af003010a9161b4-7] Harary, Palmer, 1973, с. 7.

[8] последовательность A001187 в OEIS

[_446dc43689f4ba03-9] Harary, Schwenk, 1973, с. 359–365.