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

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

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

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

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

• Число помеченных простых неориентированных графов с n вершинами равно 2 ^{n ( n − 1)/2}
• Число помеченных простых ориентированных графов с n вершинами равно 2 ^{n ( n − 1)}
• Число C _n связных помеченных неориентированных графов с n вершинами удовлетворяет рекуррентному соотношению

${\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 равны :

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

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

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

См. также

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

Примечания

Литература

• 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 : .
• Pólya G. // Acta Mathematica . — 1937. — Vol. 68. — doi : . (недоступная ссылка)
• The theory of group-reduced distributions // American J. Math. — 1927. — Т. 49 .