A Note on Two Problems in Connexion with Graphs-英文文献.pdf

Numerische Mathematlk l, 269- 27I (l 959) Two in with Graphs A Note on Problems Connexion by E.W. DrrKsrRA We considera points (nodes),someor all pairs of which are connectedby a branch; the length of each branch is given. We restrict ourselvesto the case where at least one path exists between any two nodes. We now consider two problems. Problem 1. Construct the tree of minimum total length betweenthe n nodes. (A tree is a graph with one and only one path betweenevery two nodes.) In the course ol the construction that we present here, the branches are subdivided into three sets: to the tree under construction (they will I. the branchesdefinitely assigned form a subtree); IL the branchesfrom which the next branch to be added to set I, will be selected; III. the rernaining branches (rejectedor not yet considered) The nodes are subdivided into two sets: A. the nodesconnectedby the branchesof set I, B. the remaining nodes (one and only one branch of set II will lead to each of these nodes). We stalt the construction by choosingan arbitrary node as the only member of set A, and by placing all branchesthat end in this node in set II. To start with, set I is empty. From then onwalalswe Pedorm the following two steps repeatedly. Step 1. The shortest branch of set II is removedfrom this set and added to set I. As a result one node is transferredfrom set B to set I . Slep 2. Considerthe branchesleadingfrom the node,that hasjust beentrans- ferred to set A, to the nodesthat are still in set B. If the branch under con-