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

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

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

Помеченные и непомеченные задачиПравить

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

Точные формулы перечисленияПравить

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

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

$C_n=2^{(\genfrac{}{}{0ex}{}{n}{2})}-<!--\; -\; -->\frac{1}{n}\underset{k=1}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}k(\genfrac{}{}{0ex}{}{n}{k})2^{(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->k}{2})}{C}_k.$$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 вершинами равно

$2^{n-<!--\; -\; -->4}+2^{\lfloor <!--\; \lfloor \; -->(n-<!--\; -\; -->4)/2\rfloor <!--\; \rfloor \; -->}.$$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: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.