Главная Бухгалтерия в кармане Учет расходов Экономия на кадровиках Налог на прибыль Как увеличить активы Основные средства
Главная ->  Гамильтоновы циклы 

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

торой нарой вершин Х; и Xj, что абсолютный центр у* графа G лежит в середине этого маршрута.

4. Используя свойство, приведенное выше в задаче 3, найти абсолютный центр в графе, изображенном на рис. 5.12.


5. Определить понятие середина пути и показать, что свой ство, приведенное выше в задаче 3, может быть обобщено на неориентированные графы с произвольными весами вершин {Vj\.

6. Используя алгоритм из разд. 8, найти абсолютный 3-центр графа G, приведенного на рис. 5.12, и показать, что каждая вершина графа G достижима по крайней мере из одной области абсолютного 3-центра в пределах расстояния Я, = 6. Каково наименьшее значение параметра р, обеспечивающее достижимость всех вершин графа G из абсолютного р-центра в пределах расстояния Я = 5,5?




9. ЗАДАЧИ 125

7. Используя алгоритм из разд. 8.5, найти 3-центр графа, изображенного на рис. 5.12, и показать, что к = 8 является наименьшим возможным X, определяющим существование 3-центра.

8. Пусть - /7-центр в неориентированном графе G. Дока* зать утверждение: ребрам графа G можно придать такую ориентацию, что Zp будет внешним р-центром в новом, ориентированном графе и расстояния d {X*, ж;) для всех вершин ж,- останутся неизменными.

9. Показать, что если G - связный неориентированный граф с единичными стоимостями ребер, то наименьшее значение параметра р, обеспечивающее существование р-центра с достижимостью, ограниченной числом к, удовлетворяет неравенству

где [к] - целая часть к (см. [5]). Предполагается, что Я < п.

10. Используя результат задачи 9, показать, что, каково бы ни было целое положительное б, все п вершин связного неориентированного графа G можно покрыть 2 -]-1 подграфами графа G, имеющими диаметры, не превосходящие б (см. разд. 5.4 и работу [5]).

И. Показать, что для связного неориентированного графа G радиус р и диаметр б удовлетворяют соотношению 6/2 pS. Привести примеры графов, для которых обе оценки радиуса являются достижимыми.

12. Показать, что в случае ориентированного графа G неравенства, подобные приведенным в задаче 11, не выполняются.

13. Заново определим число внешнего разделения Sg (у) и внешний абсолютный центр у* графа G:

о(г/)= max [d{y,y)],

у' на G

У* является такой точкой у графа G, для которой о (!/*)= min [So (у)].

у на G

Обобщить методы, приведенные в разд. 5, таким образом, чтобы можно было строить определенные выше внешние абсолютные центры графов.



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

1. Bollobas В. (1968), Graphs of given diameter. Theory of Graphs, Erdos and Katona, Eds., Academic Press, New York.

2. Bosak J., Rosa A., Znam S. (1968), On decomposition of complete graphs, into factors with given diameters. Theory of Graphs, Erdos and Katona, Eds., Academic Press, New York.

3. Christofides N., Viola P. (1971), The optimum location of multi-center on a graph, Opl. Дез. Quart., 22, p. 45.

4. Dijkstra D. (1959), A note an two problems in connection with graphs, Numerische Mathematik, 1, . 269.

5. Erdos P., Gerencser L., Mate A. (1969), Problems of graph theory concerning optimal design, Colloquia Mathematica Societatis Janes Bolyai, No 4, Combinatorial theory and its applications, Bala+onfured (Hungary), p. 317.

6. Frank H., Frisch I. T. (1971), Communication transmission and transportation networks, Addison Wesley, Reading, Massachusetts.

7. Hakimi S. L. (1964), Optimum location of switching centres and the absolut& centres and medians oi a graph. Ops. Res., 12, p. 450.

8. Hakimi S. L. (1965), Optimum distribution of switching centres in a communication network and some related graph theoretic problems. Ops. Res., 13, p. 462.

9. Minieka E. (1970), The m-centre problem, /. of SIAM (review), 12, p. 138.

10. Rosenthal M. R., Smith S. B. (1967), The m-centre problem. Presented at the 31st National ORSA Meeting, New York.

11. Sakowicz A. F. (1970), A planning model for the location of communication centres. Presented at the 38th National ORSA Meeting, Detroit, Michigan.

12. Singer S. (1968), Multi-centres and multi-medians of a graph with an application to optimal warehouse location. Presented at the 16th TIMS Conf.

13. Toregas C, Swain R., Revelle C, Bergman L. (1971), The location of emergency service facilities. Ops. Res , 19, p. 1363.



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

© 2024 Constanta-Kazan.ru
Тел: 8(843)265-47-53, 8(843)265-47-52, Факс: 8(843)211-02-95