On algorithm of numbering the spanning trees in a connected graph
Автор: Popov Vladimir Valеntinovich
Журнал: Математическая физика и компьютерное моделирование @mpcm-jvolsu
Рубрика: Прикладная математика
Статья в выпуске: 2 (27), 2015 года.
Бесплатный доступ
Let ?? = (??,??) be a finite connected graph without multiple edges or loops. We consider the task about the numbering of all the spanning trees of ??. In [2, p. 180, p. 191] described a method of solution of this task, based on the properties of minors of an incidence matrix of ??. In the same place (p. 191-193) gave algorithm of four Japanese mathematicians (Kasahara Y., Tezuka K., Ling Shun Tong, Kitahashi T., [6]), reduced the task to removal of brackets in the product of formal sums of edges of ??. Here we concider the method based on lexicographical order on the set of all sequences of edges of ??. We will remind that a spanning tree ?? of the graph ?? is a tree consisting of edges of ?? and connecting all the vertices of ??. We shall assume that ?? = {1, 2,..., ??}, where ?? is a number of vertices of ??. If ??, ?? ? ??, then (??, ??) will be designated the edge with end-points ?? and ??. Let ?? be a spanning in ??. Then the set of his edges can be written in the form (??1, ??1), (??2, ??2),..., (?????1, ?????1), (??) where ????
Connected graph, planar graph, spanning tree, number of spanning trees, triangulation, number of triangulations
Короткий адрес: https://sciup.org/14968985
IDR: 14968985 | DOI: 10.15688/jvolsu1.2015.2.1