10. Написать алгоритм перечисления всех остовов графа без повторений, используя элементарные преобразования дерева (см. [42, 47, 8]).

11. Найти SST графа, показанного на рис. 7.17, двумя алгоритмами - Крускала и Прима.

12. Найти для полного графа на множестве вершин {xj, х^, Хз, xJ, как показано на рис. 7.18, с весами ребер, определенных как евклидовы расстояния:

(i) SST,

(ii) Дерево Штейнера на плоскости. (Использовать свойства точек Штейнера на плоскости, данные в разд. 4, и рассмотреть все возможные топологии (т. е. матрицы инциденций). Решить ту же задачу, полагая веса ребер равными линейным расстояниям между точками.

13. Повторить упражнение 12, добавив дополнительную вершину Xs и оценить увеличение объема вычислений.

6. Список литературы

1. Берж К., Теория графов, М., ИЛ, 1962.

2. Bott R., МауЬеггу J. Р. (1954), Matrices and Trees, Economic Activity Analysis, Wiley, New York.

3. Басакер P, Саати Т., Конечные графы и сети , М., Наука, 1974.

4. Cayley А. (1874), On the mathematical theory of isomers. Philosophical Magazine, 67, p. 444.

5. Cayley A. (1897), Collected papers. Quart. J. of Mathematics, 13, Cambridge, p. 26.

6. Chan S. P., Chan S. G. (1968), Modifications of topological formulae, IEEE Trans., CT-15, p. 84.

7. Change S.-K. (1972), The generation of minimal trees with Steiner topology, /. of ACM, 19, p. 699.

8. Chen W.-K. (1971), Applied Graph Theory, North-Holland, Amsterdam.

9. Chen W.-K. (1966), On the directed trees and directed k-trees of a digraph and their generation, /. of SIAM {Appl. Math.), 14, p. 550.

10. Chen W. K., Li H.-C. (1973), Computer generation of directed trees and complete trees. Int. J. of Electronics, 34, p. 1.

11. Cockayne E. J. (1970), On the efficiency of the algorithm for Steiner minimal trees, /. of SIAM {Appl. Math.), 18, p. 150.

12. Cockayne E. J., Melzak Z. A. (1968), Steiners for problem set terminals. Quart. Applied Mathematics, 26, p. 213.

13. Курант P., Роббинс Г. (1970), Что такое математика?, М., Наука.

14. Coxeter Н. S. М. (1961), Introduction to geometry, Wiley, New York. [Есть русский перевод: Кокстер Г. С. М., Введение в геометрию, М., Наука , 1966.]

15. Cummings R. L. (1966), Hamilton circuits in tree graphs, IEEE Trans., CT-13, p. 82.

16. Брёйн H. Дж. де (1968), Теория перечисления Пойа, сб. Прикладная комбинаторная математики, М., Мир .

17. Dijkstra Е. W. (1959), А note on two problems in connection with graphs. Numerische Mathematik, 1, p. 269.

18. Dreyfus S. Е., Wagner R. A. (1972), The Steiner problem in graphs. Networks, 1, 195.

19. Even S. (1973), Algorithmic combinatorics, Macmillan, New York.

20. Fidler J. K., Horrocks D. H. (1973), On the generation of k-trees, /. of Electronics, 34, p. 185.

21. Floyd R. W. (1962), TREESORT- Algorithm 113, ACM Collected Algorithms.

22. Floyd R. W. (1964), TREESORT 3-Algorithm 245, ACM Collected Algorithms.

23. Fu Y. (1967), Application of linear graph theory to printed circuits, Proc. Asilomar Conf. on Systems and Circuits.

24. Gilbert E. N., Pollack H. 0. (1968), Steiner minimal trees, /. of SIAM (Appl. Math.), 16, p. 1.

25. Glover F., Klingman D. (1970), Locating stepping-stone paths in distribution problems via the predecessor index metnod, Transp. Sci., 4, p. 220.

26. Gower J. C, Ross G. J. S. (1969), Minimum spanning trees and single linkage cluster analysis. Applied Statistics, 18, p. 54.

27. Hakimi S. L. (1971), Steiners problem in graphs and its implications, Networks, 1, p. 113.

28. Hanan M. (1966), On Steiners problem with rectilinear distance, /. of SIAM (Appl. Math.), 14, p. 255.

29. Hanan M. (1972), A counterexample to a theorem of Fu on Steiners problem, IEEE Trans., CT-19, p. 74.

30. Hanan M., Kurzberg J. M. (1972), Placement techniques. Design automation of digital systems, Breuer, Ed., Prentice Gall, New Jersey.

31. Holzmann C. A., Harary F. (1972), On the tree graph of a matroid /. of SIAM (Appl. Math.), 22, p. 187.

32. Johnson E. (1962), Networks and basic solutions. Ops. Res., 14, p. 89.

33. Kamae T. (1967), The existence of Hamiltonian circuits in tree graphs, IEEE Trans., CT-14, p. 279.

34. Kershenbaum A., Van Slyke R. (1972), Computing minimum spanning trees efficiently, Proc. of the Ann. Conf. of ACM, Boston, p. 518.

35. Kevin v., Whitney M. (1972), Algorithm 422-Minimal spanning tree. Comm. of ACM, 15, p. 273.

36. Kirchhoff G. (1847), Annalen der Physik and Chemie, 72, p. 497.

37. Kishi G., Kajitani Y. (1968), On Hamilton circuits in tree graphs, IEEE Trans., CT-15, p. 42.

38. Kishi G., Kajitani Y. (1968), On the realization of tree graphs, IEEE Trans., CT-15, p. 271.

39. Knuth D. E. (1968), The art of computer programming. Vol. 1. Fundamental algorithms, Addison Wesley, Reading, Massachusetts.

40. Kruskal I. B. Jr. (1956), On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. American Mathematical Soc, 7, p. 48.

41. Loberman H., Weinberger A. (1957), Formal procedures for connecting terminals with a minimum total wire length, /. of ACM, 4, p. 428.

42. Mayeda W. (1972), Graph Theory, Wiley-Interscience, New York.

43. Mayeda W., Hakimi S. L., Chen W.-K., Deo N. (1968), Generation of complete trees, IEEE Trans., CT-15, p. 101.

44 Melzak Z. A. (1961), On the problem of Steiner, Canadian Mathematical Bulletin, 4, p. 335.

45. Moon J. W. (1967), Various proofs of Cayleys formula for counting trees, A seminar of graph theory, Harary, Ed., Holt, Rinehart and Winston, New York.

46. Obruca A. (1964), Algorithm 1 - MINTREE, Computer Bulletin, p . 67.

47. Paul A. J. Jr. (1967), Generation of directed trees and 2-trees without duplication, IEEE Trans., CT-14, p. 354.

48. Prim R. С. (1957), Shortest connection networks and some generalizations. Bell Syst. Tech. J., 36, p. 1389.

49. Riordan J. (1958), An Introduction to Combinatorial Analysis, Wiley, New York. [Есть русский перевод: Риордан Дж., Введение в комбинаторный анализ, М., ИЛ, 1963.]

50. Scott А. (1971), Combinatorial programming, spatial analysis and planning, Methuen, London.

51. Shank H. (1968), Note on Hamilton circuits in tree graphs, IEEE Trans., CT-15, p. 86.

52. Srinivasan V., Thompson G. L. (1972), Accelerated algorithms for labelling and relabelling of trees with applications to distribution problems, /. of ACM, 19, p. 712.

53. Trent H. M. (1954), A note on the enumeration and listing of all possible trees in a connected linear graph, Proc. Nat. Acad. Sci. U. S. A., 40, p. 1004.

54. Yang Y. Y., Wing 0. (1972), Suboptimal algorithm for a wire routing problem, IEEE Trans., CT-19, p. 508.