Перечисление графов — категория задач перечислительной комбинаторики, в которых нужно пересчитать неориентированные или ориентированные графы определённых типов, как правило, в виде функции от числа вершин графа. Эти задачи могут быть решены либо точно (как задача ) или асимптотически. Пионерами в этой области математики были Пойа, КэлиArthur Cayley A Cambridge Alumni Database. University of Cambridge. и .
Помеченные и непомеченные задачи В некоторых задачах перечисления графов вершины графов считаются помеченными, делая их отличимыми друг от друга. В других задачах любая перестановка вершин считается тем же графом, так что вершины считаются идентичными или непомеченными. В общем случае, помеченные задачи, как правило, оказываются проще. Теорема Редфилда — Пойи является важным средством для сведения непомеченной задачи к помеченной — каждый непомеченный класс считается классом симметрии помеченных объектов.
Точные формулы перечисления Некоторые важные результаты в этой области. Число помеченных простых неориентированных графов с n вершинами равно 2n(n − 1)/2 Число помеченных простых ориентированных графов с n вершинами равно 2n(n − 1) Число Cn связных помеченных неориентированных графов с n вершинами удовлетворяет рекуррентному соотношению
из которого можно легко вычислить для n = 1, 2, 3, …, что значения Cn равны: 1, 1, 4, 38, 728, 26704, 1866256, … Число помеченных свободных деревьев с n вершинами равно nn − 2 (формула Кэли). Число непомеченных гусениц с n вершинами равно
См. также Алгебраическая теория графов Спектральная теория графов Топологическая теория графов
Примечания
Литература
Категория:Перечисление графов Категория:Перечислительная комбинаторика