Град 14452 шифр 01. На территории города имеется три телефонных станции А, б и В. Незадействованные емкости станций составляют на станции а q
![]()
|
В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения. После операции приведения матрица примет вид:
Чтобы исключить подциклы, запретим следующие переходы: (4,5). Поскольку нижняя граница этого подмножества (5,4) меньше, чем подмножества (5*,4*), то ребро (5,4) включаем в маршрут. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
Наибольшая сумма констант приведения равна (5+1) = 6 для ребра (2,5), следовательно, множество разбивается на два подмножества (2,5) и (2*,5*). Нижняя граница гамильтоновых циклов этого подмножества:
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения. После операции приведения сокращенная матрица будет иметь вид:
Чтобы исключить подциклы, запретим следующие переходы: (3,2), (4,3) Поскольку нижняя граница этого подмножества (2,5) меньше, чем подмножества (2*,5*), то ребро (2,5) включаем в маршрут. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
|