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

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

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

См. также

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