A Simple Algorithm for Listing All the Trees of a Graph
A Simple Algorithm for Listing All the Trees of a Graph
复制标题
DOI：
10.1109/tct.1965.1082385
复制
发表时间：
1965-03
期刊：
影响因子：
--
通讯作者：
G. Minty
中科院分区：
文献类型：
--
作者：
G. Minty
“树”指的是不包含回路(简单的闭合曲线)的最大线集合；我们请读者注意，当图形没有连接时，这意味着什么。我们建议列出一个给定图的所有树。这个问题与解线性电网络的Kirchhoff-Feussner方法[I]有关。Feussner的论文[2]包含了本方法思想的萌芽。这里描述的方法很容易修改，以生成包含给定树枝的所有树。当某些阻抗不是常量(数字)而是变量时，Kirchhoff-Feussner方法特别有价值，因为矩阵求逆是一个繁琐的过程，除非输入的是常量。所要描述的算法是为数字计算机实现而设计的；其速度几乎完全受打印输出的限制，因此应利用“矩阵-树定理”[3]对树的数目进行初步计数，以确定该程序是否可行。计算机的内存需求相当低，只要在发现树时一次打印出一棵树，或者(如果计算中需要中间结果)在列出下一棵树之前使用并擦除它们。该算法所基于的基本原理如下：如果图G的分支b是可区分的，则可以将这些树分类为wh。我包含分支和那些不包含分支的分支。如果设g1和gz是通过将b收缩到一个点并删除b而得到的图，则类别1的每棵树由G1+b的树组成，而类别2的每棵树由Gz的树组成，只要6既不是自环也不是桥(即不是电路元件的分支)。如果b是一个循环，则可以在不改变树的情况下删除它，而如果它是一座桥，则G的树是G1加B的树。算法如下：想象在一张纸上画的图；所有的树枝都有编号(或者用标识标记)。删除所有的自环；删除所有的桥，在纸的底部写下它们的编号。使用这张纸生成另外两张纸，如下所示：区分任何树枝并将其命名为b。在一张新纸上绘制Gz。在另一张纸上画g1，并在纸的底部写上分支b的编号。现在，通过擦除所有自环来减少G1和Gz；同时擦除所有电桥，但在相应表格的底部写下删除的每个电桥的编号。将原始纸张底部的数字转移到两个新纸张的底部，并丢弃原始纸张。
By “tree” is meant a maximal collection of lines which contains no circuit (simple closed curve); we ask the reader to notice what this means when the graph is not connected. We propose to list all the trees of a given graph. This problem is of interest in connection with the Kirchhoff-Feussner method [I] of solving linear electrical networks. Feussner’s paper [2] contains the germ of the idea of the present method. The method described here is easily modified to produce all the trees containing a given branch also. The Kirchhoff-Feussner method is especially valuable when some of the impedances are not constants (numbers) but variables, since matrix inversion is a tedious process unless the entries are constants. The algorithm to be described is designed for implementation by digital computer; the speed is limited almost entirely by print-out, so that a preliminary count of the number of trees should be made, using the “matrix-tree theorem”[3], to determine whether the procedure is feasible. Memory requirements for the computer are quite low, provided the trees are printed out one-at-a-time as they are found, or (if needed as intermediate results in a computation) used and erased before listing the next tree. The fundamental principle on which the algorithm is based is the following: if a branch b of a graph G is distinguished, the trees can be classified into those wh. ich contain the branch and those which do not contain the branch. If we let G1 and Gz be the graphs obtained by shrinking b to a point and deleting b, every tree of category 1 consists of a tree of G1 plus b, while every tree of category 2 consists of a tree of Gz, provided 6 is neither a self-loop nor a bridge (ie, branch which is not a circuit element). If b is a loop, it can be deleted without changing the trees, whereas, if it is a bridge, the trees of G are the trees of G1 plus b.The algorithm is as follows: imagine the graph drawn on a sheet of paper; all the branches are numbered (or otherwise marked with identification). Delete all self-loops; delete all bridges, writing their numbers at the bottom of the sheet. Use the sheet of paper to generate two other sheets, as follows: distinguish any branch and call it b. Draw Gz on one new sheet. Draw G1 on the other sheet and write the number of the branch b on the bottom of the sheet. Now reduce G1 and Gz by erasing all self-loops; also erase all bridges, but write the number of each bridge deleted at the bottom of the corresponding sheet. Transfer the numbers at the bottom of the original sheet to the bottoms of both new sheets, and discard the original.