Возникает вопрос, при каком способе соединения центров затраты будут наименьшими? Мы пришли к задаче указанного вида.
Описываемый далее алгоритм решения задачи о минимальном остове состоит из п шагов.
На нулевом (вспомогательном) шаге выбирается произвольная вершина, например вершина 1 и полагается V\ = {l}, R\ - ®.
К началу к-го шага (к = 1,1) даны множества VjaV и
Rl czR, образующие связный граф = (F, i?). Выберем такое ребро {ikJk) У которого начало лежит в множестве Vj, конец - в его дополнении F \ и которое имеет наименьшую длину среди всех таких дуг, т.е.
iik,Jk)eR, ikeVf, дК и су = = min [cij: (i,J)eR, ieVf,, j€Vj,]
После этого полагаем Vj = Vj,, Rj,x = h {(JkJk)] •
Ясно, что ri = (A;+bA;+l) Tb СВЯЗНЫЙ граф, так как новая вершина 7 связана с любой вершиной из множества Vj через вершину .
Поскольку на каждом шаге к множеству Vj добавляется ровно одна вершина, то на шаге к = п-\ мы получим, что Vy = V. При этом, согласно сказанному, Г„ =(F,i?„) есть связный граф, т.е. по определению R является остовом исходного графа, Г =(y,R ).
Теорема. Множество R есть остов минимальной длины. Перед тем
как доказать эту теорему, продемонстрируем работу алгоритма на примере графа, указанного на рис 8.6.
Решение. ШагО. Полагаем = {l}, i?i = ®.
Шаг 1. Минимальным среди чисел q2=4, 3=6, q4=5 является Поэтому полагаем V2 = {1,2}, R2= {(1,2)}.
Шаг 2. Минимальным среди чисел Сз =6, С4 =5, С23 =1, С25 =7 является С23. Поэтому полагаем F3 = {1,2,3}, i?3 = {(1,2),(2,3)}.
ШагЗ. Минимальным среди чисел q4 = 5, С25 = 7, С34 = 2, 35=5, сз5=4 является С34. Поэтому полагаем F4 ={1,2,3,4}, i?4={a2),(2,3),(3,4)}.
Шаг 4. Минимальным среди чисел С35 = 5, С25 = 7, С36 = 4, С45 = 5 является с35.
Поэтому полагаем
F5 ={1,2,3,4,6}, ={(1,2),(2,3),(3,4),(3,6)}.
Шаг 5. Минимальным среди чисел С35 = 5, С25 = 7, 05 = 1 является . Поэтому полагаем
Кб ={1,2,3,4,6,5}, i?6 ={(1,2),(2,3),(3,4),(3,6),(6,5)}.
Таким образом, минимальные затраты на прокладку кабеля достигаются при соединении пар центров из вершины и равны y(i?5)=4 + 1 + 2 + 44- 1 = 12. Минимальный остов изображен на рис. 8.7.
Рис. 8.7
Теперь докажем приведенную теорему, для простоты ограничившись случаем, когда все числа су ((iJ) е R) различны.
Доказательство. Пусть R* - остов наименьшей длины и R R* . Ясно, что не может лежать целиком в R*, так как иначе f{Rn)< /(R*) и, значит, R* не есть решение задачи. Тогда найдется такая дуга (ij) € , что ((/,У) R*. Согласно построению множества R существует такой индекс к е {1, «}, что {iJ) = {ikJk) Поскольку Г* = (К,Л*) - связный граф, то вершины и jj могут быть соединены
некоторым маршрутом, все дуги которого лежат в it. Начало этого маршрута лежит в , а конец д не лежит. Следовательно, найдется та-230
кая дуга (г, s) этого маршрута, что г eVj и s V/, Тогда по определению дуги QkJk) (и с учетом различности чисел с/) имеем
\jk rs(8-4)
Введем множество ребер R = R и {{iJk) \ {()}}» образованное из
R* путем замены ребра (г, s) на ребро Qk,Jk)- Граф Г =являет-
ся связным, поскольку вершины г и s соединены маршрутом, проходящим через дугу (ik,Jic)- В то же время из (8.4) имеем f(R) < f(R*), но это противоречит тому, что R* - остов наименьшей длины. Таким образом, R= R*.
8.5. Задачи распределения ресурсов на сетевых графиках
О способах и методах распределения ресурсов, об их важности для функционирования экономических, экологических, военных и других систем сказано очень много. Тем не менее в области исследования операций и теории игр сложилось ограниченное понимание задач распределения ресурсов. Под этим классом задач понимают в основном задачи типа леммы Гиббса и ее обобщений, оговаривая, однако, что большинство задач линейного программирования (а их многообразие неисчислимо) тоже подпадают под класс задач распределения ресурсов.
Наше понимание этих задач состоит в следующем. При любых математических описаниях функционирующих систем, подвластных человеческому воздействию, на эти системы могут быть наложены ресурсные ограничения, и эволюция этих систем будет зависеть от способов распределения ограниченных ресурсов. Системы могут быть детерминированными, функционирующими при наличии неопределенных факторов (в том числе и при наличии противоборствующей стороны) и адаптивными (со случайными факторами), характеристики которых известны или становятся известными в процессе их функционирования. В наиболее общем описании функционирования больших систем, очевидно, будут присутствовать все факторы. При рассмотрении таких систем способами распределения ресурсов будут выборы скалярных или векторных переменных, вектор-функций и даже мер в зависимости от возможностей оперирующей стороны.