Об алгоритме перечисления остовов связного графа
Автор: Попов Владимир Валентинович
Журнал: Математическая физика и компьютерное моделирование @mpcm-jvolsu
Рубрика: Прикладная математика
Статья в выпуске: 2 (27), 2015 года.
Бесплатный доступ
Описывается алгоритм перечисления всех остовных деревьев (остовов) связного графа с конечным числом вершин. Приводятся результаты работы компьютерной программы, составленной по этому алгоритму. Обсуждается также вопрос о перечислении всех триангуляций плоского графа.
Связный граф, планарный граф, остовное дерево, число остовных деревьев, триангуляция, число триангуляций, выпуклая оболочка
Короткий адрес: https://sciup.org/14968985
IDR: 14968985 | DOI: 10.15688/jvolsu1.2015.2.1
Список литературы Об алгоритме перечисления остовов связного графа
- Зыков, А.А. Основы теории графов/А.␣А. Зыков. -М.: Наука, 1987. -384 c.
- Зыков, А.А. Теория конечных графов/А.␣А. Зыков. -Новосибирск: Наука, 1969. -554 c.
- Клячин, В.А. Метод цепей для организации хранения многомерных триангуляций/В.␣А. Клячин, В.␣В. Попов//Вестник Волгоградского государственного университета. Серия 1, Математика. Физика. -2013. -№ 2 (19). -C. 71-79.
- Aichholzer, O. On the Number of Plane Geometrical Graphs/O. Aichholzer, T. Hackl, B. Vogtenhuber, C. Huemer, F. Hurtado, H. Krasser//Graphs and Combinatorics. -2007. -№ 23. -P. 67-84.
- Diestel, R. Graph Theory/R. Diestel. -N. Y.: Springer-Verlag, 2000. -384 p.
- Kasahara, Y. Topological evaluation of a system determinants/Y. Kasahara, K. Tezuka, S.␣T. Ling, T/Kitahashi//Technol. Repts. Osaka Univ. -1962. -№ 12. -P. 239-248.