Вывод формул для количества циклов фиксированной длины в графах ладьи
Автор: Воропаев Антон Николаевич
Журнал: Ученые записки Петрозаводского государственного университета @uchzap-petrsu
Рубрика: Физико-математические науки
Статья в выпуске: 8 (129) т.2, 2012 года.
Бесплатный доступ
Рассматривается техника символьных вычислений по явным формулам для подсчета циклов фиксированной длины в неориентированных графах. Детали аналитических преобразований сумм, входящих в формулы, иллюстрируются на примере семейства графов ладьи на досках размера N х N. На основе явных выражений для количества циклов длин 3, 4,..., 7 выведены многочлены, описывающие зависимость данных величин от N в случае графов ладьи.
Подсчет циклов фиксированной длины в неориентированных графах, графы ладьи
Короткий адрес: https://sciup.org/14750282
IDR: 14750282
Список литературы Вывод формул для количества циклов фиксированной длины в графах ладьи
- Воропаев А. Н. Подсчет простых циклов фиксированной длины в графах. Явные формулы для случая малых длин//Научное творчество молодежи: Материалы XIII Всеросс. науч.-практ. конф. (г. Анжеро-Судженск, 14-15 мая 2009 г.). Томск: Изд-во Томского ун-та, 2009. Ч. 1. С. 21-23.
- Воропаев А. Н. Вывод явных формул для подсчета циклов фиксированной длины в неориентированных графах//Информационные процессы. 2011. Т. 11. № 1. С. 90-113.
- Воропаев А. Н., Перепечко С. Н. Количество простых циклов фиксированной длины в неориентированном графе. Явные формулы в случае малых длин//Вестник Российского университета дружбы народов. Сер. «Математика, информатика, физика». 2012. № 2. С. 5-11.
- Alon N., Yuster R., Zwick U. Finding and counting given length cycles//Algorithmica. 1997. Vol. 17. № 3. P. 209-223.
- Chang Y. C., Fu H. L. The number of 6-cycles in a graph//The Bulletin of the Institute of Combinatorics and Its Applications. 2003. Vol. 39. P. 27-30.
- Harary F., Manvel B. On the number of cycles in a graph//Matematicky casopis. 1971. Vol. 21. № 1. P. 55-63.
