Русская Википедия:Перечисление графов
Перечисление графов — категория задач перечислительной комбинаторики, в которых нужно пересчитать неориентированные или ориентированные графы определённых типов, как правило, в виде функции от числа вершин графаШаблон:Sfn. Эти задачи могут быть решены либо точно (как задача Шаблон:Нп3) или асимптотически. Пионерами в этой области математики были ПойаШаблон:Sfn, Кэли[1] и Шаблон:Нп3Шаблон:Sfn.
Помеченные и непомеченные задачи
В некоторых задачах перечисления графов вершины графов считаются помеченными, делая их отличимыми друг от друга. В других задачах любая перестановка вершин считается тем же графом, так что вершины считаются идентичными или непомеченными. В общем случае, помеченные задачи, как правило, оказываются прощеШаблон:Sfn. Теорема Редфилда — Пойи является важным средством для сведения непомеченной задачи к помеченной — каждый непомеченный класс считается классом симметрии помеченных объектов.
Точные формулы перечисления
Некоторые важные результаты в этой области.
- Число помеченных простых неориентированных графов с n вершинами равно 2n(n − 1)/2Шаблон:Sfn
- Число помеченных простых ориентированных графов с n вершинами равно 2n(n − 1)Шаблон:Sfn
- Число Cn связных помеченных неориентированных графов с n вершинами удовлетворяет рекуррентному соотношениюШаблон:Sfn
- <math>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.</math>
- из которого можно легко вычислить для n = 1, 2, 3, …, что значения Cn равны[2]:
- 1, 1, 4, 38, 728, 26704, 1866256, …
- Число помеченных свободных деревьев с n вершинами равно nn − 2 (формула Кэли).
- Число непомеченных гусениц с n вершинами равноШаблон:Sfn
- <math>2^{n-4}+2^{\lfloor (n-4)/2\rfloor}.</math>
См. также
Примечания
Литература
- ↑ Arthur CayleyШаблон:Недоступная ссылка A Cambridge Alumni Database. University of Cambridge.
- ↑ Шаблон:OEIS