Последовательно-параллельный граф - это граф, не содержащий в качестве нора полный граф с четырьмя вершинами. Такие графы используются при строении надёжных коммуникационных сетей. Получена явная формула для числа помеченных последовательно-параллельных тетрациклических графов с заданным числом вершин. Доказано, что при равномерном распределении вероятностей вероятность того, что помеченный тетрациклический блок является последовательно-параллельным графом, асимптотически равна 3/11.
Скачать электронную версию публикации
Загружен, раз: 90
- Title Число помеченных тетрациклических последовательно-параллельных блоков
- Headline Число помеченных тетрациклических последовательно-параллельных блоков
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 47
- Date:
- DOI 10.17223/20710410/47/5
Ключевые слова
помеченный граф, тетрациклический граф, последовательнопараллельный граф, блок, перечисление, асимптотика, labeled graph, tetracyclic graph, series-parallel graph, block, enumeration, asymptoticsАвторы
Ссылки
Bodirsky M., Gimenez O., Kang M., and Noy M. Enumeration and limit laws of series-parallel graphs // European J. Combinatorics. 2007. V. 28. P. 2091-2105
Radhavan S. Low-connectivity network design on series-parallel graphs // Networks. 2004. V. 43. No. 3. P. 163-176
Takamizawa K., Nishezeki T., and Saito N. Linear-time computability of combinatorial problems on series-parallel graphs // J. ACM. 1982. V. 29. No. 3. P. 623-641
Воблый В. А. Второе соотношение Риддела и следствия из него // Дискретн. анализ и исследование операций. 2019. Т. 26. №1. С. 20-32
Воблый В. А., Мелешко А. М. О числе помеченных последовательно-параллельных трициклических блоков // Материалы XV Междунар. конф. «Алгебра, теория чисел и дискретная геометрия. Современные проблемы и приложения». Тула: Изд-во ТПГУ, 2018. С. 168-170
Ford G. W. and Uhlenbeck G. E. Combinatorial problems in theory graphs. IV // Proc. Nat. Acad. Sci. USA. 1957. V. 43. P. 163-167
Степанов В. Е. О некоторых особенностях строения случайного графа вблизи критической точки // Теория вероятн. и ее применения. 1987. Т. 32. Вып. 4. С. 633-657
Heap B.R. Enumeration homeomorphically irreducible star graphs // J. Math. Phys. 1966. V. 7. No. 7. P. 1582-1587
Прудников А. П. и др. Интегралы и ряды. Т. 1. М.: Наука, ГРФМЛ, 1981. 800 с
Wright E.M. The number of connected sparsely edges graphs. II // J. Graph Theory. 1978. V. 2. P. 299-305
Число помеченных тетрациклических последовательно-параллельных блоков | Прикладная дискретная математика. 2020. № 47. DOI: 10.17223/20710410/47/5
Скачать полнотекстовую версию
Загружен, раз: 314