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

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

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

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

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

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

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

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

$C_n=2^{(\genfrac{}{}{0ex}{}{n}{2})}-\frac{1}{n}\sum _{k=1}^{n-1}k(\genfrac{}{}{0ex}{}{n}{k})2^{(\genfrac{}{}{0ex}{}{n-k}{2})}{C}_k.$

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

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

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

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:СтатьяШаблон:Недоступная ссылка
• Шаблон:Статья