![]() |
![]() |
![]() |
![]() |
Главная -> Гамильтоновы циклы 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 [ 79 ] 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 7. Список литературы 1. Altman S., Beltrami Е., Rappaport S., Schoepfle G. (1971), A nonlinear programming model for household refuse collection, IEEE Trans., SMC-1, p. 289. 2. Altman S., Bhagat N., Bodin L. (1971), Extensions of the Clarke and Wright algorithm for routing garbage trucks. Presented at the 8th International TIMS Meeting, Washington D.C. 3. Bellman R., Cooke K. L. (1969), The Konigsberg bridges problem generalized, /. of Math. Anal, and Appl., 25, p. 1. 4. Beltrami E. J., Bodin L. D. (1972), Networks and vehicle routing for municipal waste collection, Proc. 10th Annual Allterton Conference on Circuit and Systems Theory, University of Illinois, p. 143. 5. Berge C, Ghouila-Houri A. (1965), Programming, game and transportation networks, Methuen, London. 6. Берж К., Теория графов и ее при.\1енения, М., ИЛ., 1962. 7. Басакер Р., Саати Т., Конечные графы и сети, М., Наука, 1974. 8. Christofides N. (1973), The optimum traversal of a graph. Omega- The Int. J. of Management Science, \, p. 1. 9. Edmonds J. (1965), The Chinese postmans problem. Bulletin of the Operations Research Soc. of America, 13, Supplement 1, p. B-73. 10. Edmonds J., Johnson E. (in press). Matching, Euler tours and the Chinese postmans problem. 11. Eilon S., Watson-Gandy, Christofides N. (1971), Distribution Manageme-net:Mathematical modelling and practical analysis. Griffin, London. 12. Even S. (1973), Algorithmic Combinatorics, Macmillan, New York. 13. Fraenkel A. S. (1970), Economic traversal of labyrinths. Mathematical Magazine, 43, p. 125. 14. Fraenkel A. S. (1971), Economic traversal of labyrinths (Correction), Mathematical Magazine, 44, p. 1. 15. Harary F., Nash-Williams C. St. J. A. (1965), On Eulerian and Hamiltonian graphs and line graphs, Canadian Mathematical Bulletin, 8, p. 701. 16. Kaufmann A. (1967), Graphs, dynamic programming and finite games. Academic Press, New York. 17. Kim W. H., Chien R.T.-W. (1962), Topological analysis and synthesis of communication networks, Columbia University Press, New York. 18. Kwan M.-K. (1962), Graphic programming using odd or even points, Chinese Mathematics, 1, 273. 19. Lovasz L. (1968), On covering of graphs, Theorie des Graphs, Dunod, Paris, p. 231. 20. Marshall C. W. (1971), Applied graph theory, Wiley, New York. 21. Seshu S., Reed M. B. (1961), Linear graphs and electrical networks, Addison-Wesley, Reading, Massachusetts. 22. Strieker R. (1970), Public sector vehicle routing - the Chinese postman problem. Ph. D. Thesis, Electrical Eng. Dept., M.I.T. 23. Tarry G. (1895), Le probleme des labyrinths, Nouvelles Ann. de Math., 14, p. 187. 24. Van Aardenne-Ehrenfest Т., de Bruijn N. G. (1951), Circuits and trees in oriented linear graphs, Simon Stevin, 28, p. 203. 25. Voss H. J. (1968), Some properties of graphs containing к independent circuits, Theorie des Graphes, Dunod, Paris, p. 231. 26. Welch J. T. (1966), A mechanical analysis of the cyclic structure of indirec-ted linear graphs, Jl. of ACM, 13, p. 205. Глава 10 ГАМИЛЬТОНОВЫ ЦИКЛЫ, ЦЕПИ И ЗАДАЧА КОММИВОЯЖЕРА 1. Введение В ряде отраслей промышленности, особенно химической и фармацевтической, возникает следуюш,ая основная задача планирования. Нужно произвести ряд (скажем п) продуктов, используя единственный тип аппаратуры или реактор. Аппарат (реактор) должен или не должен быть перенастроен (очищен) после того как произведен продукт pi (но до того, как началось производство продукта Pj), в зависимости от комбинации (pi, pj). Стоимость перенастройки аппаратуры постоянна и не зависит от продукта, который только что произведен, или от продукта, следующего за ним. Разумеется, не требуется никаких затрат, если перенастройка аппаратуры не нужна ). Предположим, что эти продукты производятся в непрерывном цикле, так что после производства последнего из п продуктов снова возобновляется в том же фиксированном цикле производство первого продукта. Возникает вопрос о том, может ли быть найдена циклическая последовательность производства продуктов pi {i - 1, 2, . . ., п), не требующая перенастройки аппаратуры. Пусть G - ориентированный граф, вершины которого представляют продукты, а существование дуги (ж^, Xj) означает, что продукт pj может следовать за продуктом pi без перенастройки аппаратуры. Тогда ответ на поставленный вопрос зависит от того, имеет ли этот орграф гамильтонов цикл ) или нет. (Гамильтонов цикл в орграфе - это ориентированный цикл (контур), проходящий ровно один раз через каждую вершину графа; см. гл. 1.) Если не существует циклической последовательности продуктов, не требующей перенастройки аппаратуры, то какова должна быть последовательность производства с наименьшими затратами на перенастройку, т. е. требующая наименьшего числа необходимых перенастроек? Ответ на этот вопрос может быть получен с помощью итеративного применения алгоритма нахождения гамильтонова цикла в орграфе. Как именно это может быть сделано, обсуждается позже в этой главе. 1) Сформулированная выше задача может возникать в следуюш;их двух случаях. Или стоимость перенастройки действительно не зависит от продукта, или, другая возможность, стоимость в каждом случае неизвестна и в качестве приближения берется средняя постоянная стоимость. Точнее, гамильтонов контур.- Прим. ред. Таким образом, метод, позволяющий ответить на вопрос, содержит ли какой-либо орграф гамильтонов цикл, имеет прямые приложения в задачах упорядочения или планирования операций. В равной степени важно использование такого метода в качестве основного шага в алгоритмах решения других, на первый взгляд далеких от данной тематики, задач теории графов. В этой главе рассматриваются следующие две задачи. Задача i. Дан ориентированный граф G, требуется найти в G гамильтонов цикл (или все циклы), если существует хотя бы один такой цикл. Задача ii. Дан полный орграф G, дугам которого приписаны произвольные веса С = [сц], найти такой гамильтонов цикл (цепь), который имеет наименьший общий вес. Задача нахождения гамильтонова цикла с наименьшим весом хорошо известна в литературе как задача коммивояжера [1, 2, 15]. Следует отметить, что если орграф G не полный, то его можно рассматривать как полный орграф, приписывая отсутствующим дугам бесконечный вес. Алгоритмы решения задачи коммивояжера и ее вариантов имеют большое число практических приложений в различных областях человеческой деятельности. Рассмотрим, например, задачу, в которой грузовик выезжает с центральной базы для доставки товаров данному числу потребителей и возвращается назад на базу. Стоимость перевозки пропорциональна пройденному грузовиком расстоянию, и при заданной матрице расстояний между потребителями маршрут с наименьшими транспортными затратами получается как решение соответствующей задачи коммивояжера. Аналогичные типы задач возникают при сборе почтовых отправлений из почтовых ящиков, составлении графика движения школьных автобусов по заданным остановкам и т. д. Задача очень легко обобщается и на тот случай, когда доставкой (сбором) занимаются несколько грузовиков, хотя эту задачу можно также переформулировать как задачу коммивояжера большей размерности [9]. Другие приложения включают составление расписания выполнения операций на машинах [5], проектирование электрических сетей [Я], управление автоматическими линиями [17] и т. д. Вполне очевидно, что сформулированная выше задача (i) является частным случаем задачи (ii). В самом деле, приписывая случайным образом дугам заданного орграфа G конечные веса получаем задачу коммивояжера ). Если решение для этой задачи, т. е. кратчайший гамильтонов цикл ), имеет конечное значение, то это решение является гамильтоновым циклом орграфа G (т. е. ) Здесь, как обычно, предполагается, что орграф G расширен до некоторого полного орграфа G н дугам, отсутствующим в G, но принадлежащим полному орграфу G, приписаны бесконечные веса.- Прим. ред. 2) Так (для краткости) называется гамильтонов цикл с наименьшим общим весом.- Прим. ред. |
© 2025 Constanta-Kazan.ru
Тел: 8(843)265-47-53, 8(843)265-47-52, Факс: 8(843)211-02-95 |