Контрольная работа по «Экономико-математические методы и модели в отрасли связи»

Сумма констант приведения φ(Г)=2+7+6+2+14+7+4+7=49. 

     Обозначим полученную матрицу через С₁ и найдём в ней самый тяжёлый нуль. Заметим, что замена нулевого элемента на ¥ приводит к изменению лишь двух слагаемых суммы констант приведения φ(Г) – по одному при приведении строк и столбцов. Поэтому вес нуля можно определить суммированием наименьших элементов его строки и столбца.

     Например, вес нуля в первой строке и четвёртом столбце складывается из минимума по первой строке, равного 6 (c_А,Г=c_А,Д=6), и минимума по четвёртому столбцу Г, равного 0 (c_Г,В=0), без учета самого c_А,Г.

     Итак, запишем приведённую матрицу  еще раз, указывая рядом с каждым нулем его вес: 

Самым тяжелым  оказывается нуль в клетке (А,Г).

     Разобьём  множество Г на две части: множество  (все циклы, проходящие через дугу (А,Г)) и (все циклы, не проходящие через дугу (А,Г)). Такое ветвление определяет необходимость выбора одного из этих вариантов. Множеству соответствует матрица С_1,1, полученная вычёркиванием соответствующих строки (строку А) и столбца (столбец Г). У оставшихся строк и столбцов сохраним их исходные номера. Разумеется, вместе с вычёркиванием строки и столбца, в матрице надо заменить на ∞ ; числа в определённых клетках так, чтобы не получалось коротких циклов (длиной меньше n). В данном случае из города Г мы уже не можем проехать в город А, поэтому в клетке (А,Г) ставим знак ∞. 
 
 

     Сумма констант приведения матрицы С_1,1 здесь равна 7, поэтому φ(Г_{(А,Г)})= φ_{А,Г}=49+7=56. Сопоставим результат φ(Г_{(i,j)}) множеству Г_{(i,j)}, (в нашем случае Г_{(А,Г)}).

     Множеству (в нашем случае ), в свою очередь, соответствует другая матрица – С_1,2, полученная заменой на ∞ элемент с_А,Г в матрице С₁:

     Сумма констант последнего приведения равна 6, так что φ( )=49+6=55. Теперь выберем между множествами Г_{(i,j)} и то, на котором минимальна функция j. В нашем случае из множеств, которому соответствует меньшее из чисел φ(Г_{(А,Г)})=56 и φ( )=55 .Поэтому дальнейшей разработке подвергнется множество . Итак, выделена определенная дуга (А,Г) графа и построены новые матрицы, к которым, очевидно, можно применить описанную выше процедуру. При каждом таком повторном применении будет фиксироваться очередная дуга графа, которая в конечном итоге войдёт в искомый гамильтонов цикл , если данная ветвь будет продолжена до конца и иметь минимальный вес. В матрице С_1,2,1 подсчитаем веса нулей (веса нулей указаны в скобках): 

      Самым тяжёлым является нуль с номером (В,Г), так что теперь следует рассматривать множества и . Обратимся к первому из них. Необходимо заменить на ¥ числа во всех тех клетках, которые соответствуют ребрам, заведомо не принадлежащим тем циклам, которые проходят через уже отобранные ранее ребра.

     Поскольку, вычеркнув строку В и столбец Г в матрице С_1,2, нужно также заменить на ∞ числа в определённых клетках так, чтобы не получалось коротких циклов (длиной меньше n), то в клетке с номером (В,Г) надо поставить символ ∞. Получим матрицу С_1,2,1:

     Сумма констант остается неизменной, так как матрица не требовала приведения φ( )=55