Об алгоритме перечисления остовов связного графа

Автор: Попов Владимир Валентинович

Журнал: Математическая физика и компьютерное моделирование @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.
Статья научная