If in the Steiner problem on graph the number of terminal nodes is much smaller than that of all graph nodes (say 50 against 1000), then one can see in its solution (the minimum tree) a system of paths on the graph connecting the terminal vertices, rather than a collection of separate edges (or arcs). This path system is similar to the system of segments making up the Steiner tree on the Euclidean plane: the local degree of the terminal nodes usually is 1, and the local degree of some nodes making up the paths is 3 or more. These nodes are the counterparts of the Steiner points in the problem on plane. Structural similarity of the trees in the Steiner problems on the Euclidean plane and on graph enables one to construct the algorithm to solve the Steiner problem on graph along the same lines as in the Steiner problem on the Euclidean plane. On the other hand, the solution of a problem on graph may be regarded as that on the Euclidean plane, provided that the graph satisfies certain requirements.
展开▼
