33. Теорема о приведения матрицы расстояний в зк. Оценка маршрута снизу (нижняя граница).

Если из всех элементов каждой строки матрицы, а затем из всех элементов каждого столбца вычесть минимальные элементы каждой строки (каждого столбца), то получим новую матрицу, в каждой строке и каждом столбце которой будет хотя бы по одному нулю. Полученная таким образом матрица называется приведенной, а процесс ее получения - приведением.

Сумма всех вычитаемых в процессе приведения элементов называется

приводящей константой. Обозначим эту константу ω .

Процесс приведения можно записать следующим образом.

Пусть Cij=minCi,j= ∀i=1,n, тогда Cij= Cij-Ci,j(i)

Пусть C¹i(j)minC¹ij, ∀j =1,n тогда C²ij=C¹ij-Ci(j)j,

где C²ij -элемент приведенной матрицы.

Приводящая константа

Оптимальные маршруты в задаче с приведенной матрицей (C² ij) совпадут с оптимальными маршрутами исходной задачи. Приводящая константа исходной матрицы и явится нижней границей всего множества возможных маршрутов