Меню Главная Случайная статья Настройки Перечисление графов Материал из https://ru.wikipedia.org Перечисление графов — категория задач перечислительной комбинаторики, в которых нужно пересчитать неориентированные или ориентированные графы определённых типов, как правило, в виде функции от числа вершин графа[1]. Эти задачи могут быть решены либо точно (как задача алгебраического перечисления[англ.]) или асимптотически. Пионерами в этой области математики были Пойа[2], Кэли[3] и Редфилд[англ.][4]. Содержание 1 Помеченные и непомеченные задачи 2 Точные формулы перечисления 3 См. также 4 Примечания 5 Литература Помеченные и непомеченные задачи В некоторых задачах перечисления графов вершины графов считаются помеченными, делая их отличимыми друг от друга. В других задачах любая перестановка вершин считается тем же графом, так что вершины считаются идентичными или непомеченными. В общем случае, помеченные задачи, как правило, оказываются проще[1]. Теорема Редфилда — Пойи является важным средством для сведения непомеченной задачи к помеченной — каждый непомеченный класс считается классом симметрии помеченных объектов. Точные формулы перечисления Некоторые важные результаты в этой области. Число помеченных простых неориентированных графов с n вершинами равно 2n(n  1)/2[5] Число помеченных простых ориентированных графов с n вершинами равно 2n(n  1)[6] Число Cn связных помеченных неориентированных графов с 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, …, что значения Cn равны[8]: 1, 1, 4, 38, 728, 26704, 1866256, … Число помеченных свободных деревьев с n вершинами равно nn  2 (формула Кэли). Число непомеченных гусениц с n вершинами равно[9] ${\displaystyle 2^{n-4}+2^{\lfloor (n-4)/2\rfloor }.}$ См. также Алгебраическая теория графов Спектральная теория графов Топологическая теория графов Примечания 1 2 Harary, Palmer, 1973. Plya, 1937, с. 145—254. Arthur Cayley (недоступная ссылка) A Cambridge Alumni Database. University of Cambridge. Redfield, 1927, с. 433—455. Harary, Palmer, 1973, с. 3. Harary, Palmer, 1973, с. 5. Harary, Palmer, 1973, с. 7. последовательность A001187 в OEIS Harary, Schwenk, 1973, с. 359–365. Литература Harary F., Palmer E. M. Graphical Enumeration. — Academic Press, 1973. — ISBN 0-12-324245-2. Harary F., Schwenk A. J. The number of caterpillars // Discrete Mathematics. — 1973. — Т. 6, вып. 4. — С. 359–365. — doi:10.1016/0012-365x(73)90067-8. Plya G. Kombinatorische Anzahlbestimmungen fr 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.