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

Полный список всех деревьев с 2,3 и 4 помеченными вершинами: ${\displaystyle 2^{2-2}=1}$ дерево с 2 вершинами, ${\displaystyle 3^{3-2}=3}$ дерева с 3 вершинами и ${\displaystyle 4^{4-2}=16}$ деревьев с 4 вершинами.

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

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

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

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

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

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

${\displaystyle 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]

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

См. также

• Алгебраическая теория графов
• Спектральная теория графов
• Топологическая теория графов

Примечания

1. Harary, Palmer, 1973.
2. Pólya, 1937, с. 145—254.
3. Arthur Cayley (недоступная ссылка) A Cambridge Alumni Database. University of Cambridge.
4. Redfield, 1927, с. 433—455.
5. Harary, Palmer, 1973, с. 3.
6. Harary, Palmer, 1973, с. 5.
7. Harary, Palmer, 1973, с. 7.
8. последовательность A001187 в OEIS
9. 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.