ГлавнаяАрхивПеречисление 2-деревьев с ориентированными ячейками

Перечисление 2-деревьев с ориентированными ячейками | Прикладная дискретная математика. 2026. № 71. DOI: 10.17223/20710410/71/5

Рассматривается задача о перечислении 2-деревьев с ориентированными ячейками с точностью до изоморфизма. Под 2-деревом мы понимаем простой граф, полученный из K3 последовательным добавлением вершин, соединенных с концами некоторого ребра. Будем говорить, что ячейки 2-дерева ориентированы, если в каждой ячейке (треугольнике) вершины независимо перенумерованы числами 1, 2, 3. Ячейки частично ориентированы, если в каждой ячейке независимо отмечена одна вершина. При помощи теоремы Редфилда - Пойа и характеристики неподобия для корневых структур вычислены производящие функции для числа 2-деревьев с ориентированными и частично ориентированными ячейками.
  • Title Перечисление 2-деревьев с ориентированными ячейками
  • Headline Перечисление 2-деревьев с ориентированными ячейками
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 71
  • Date:
  • DOI 10.17223/20710410/71/5
Ключевые слова
2-деревья, теория перечисления Пойа, производящие функции
Авторы
Ссылки
McKay В. D. and Piperno A. Practical graph isomorphism. II // J. Symbolic Comput. 2014. V.60. P. 94-112.
Xapapu Ф., Палмер Э. Перечисление графов. M.: Мир. 1977. 328 с.
Fowler Т., Gessel I. М., Labelle G., and Leroux Р. The specification of 2-trees // Adv. Appl. Math. 2002. V.28. No. 2. P. 145-168.
Labelle G., Lamathe C., and Leroux P. Labelled and unlabelled enumeration of k-gonal 2-trees // J. Combinat. Theory. Ser. A. 2004. V. 106. No. 2. P.193-219.
Gainer-Dewar A. and Gessel I. M. Counting unlabeled k-trees // J.Combinat. Theory. Ser. A. 2014. V. 126. P. 177-193.
Qian J. Enumeration of unlabeled directed hypergraphs // Electronic J.Combinatorics. 2013. V. 20. Iss.l. Article no. P46.
Qian J. Enumeration of unlabeled uniform hypergraphs // Discrete Math. 2014. V. 326. P. 6674.
Polya G. and Read R. C.H.Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds. Berlin; Heidelberg: Springer, 1987.
Ландо C.K. Лекции о производящих функциях. М.: МЦМНО, 2007. 144с.
https://github.com/VVerdenko/oriented-2-trees - Вычисление производящих функций для 3-ориентированных и частично 3-ориентированных 2-деревьев. 2025.
Перечисление 2-деревьев с ориентированными ячейками | Прикладная дискретная математика. 2026. № 71. DOI: 10.17223/20710410/71/5
Перечисление 2-деревьев с ориентированными ячейками | Прикладная дискретная математика. 2026. № 71. DOI: 10.17223/20710410/71/5