Метод квазиминоров

Тема 6. ХАРАКТЕРИСТИКА МЕТОДОВ МАРШРУТИЗАЦИИ, ИСПОЛЬЗУЕМЫХ НА ЭТАПАХ ФУНКЦИОНИРОВАНИЯ И КОРРЕКТИРОВКИ СЕТИ.

Метод, предложенный Г.Н. Поваровым [] несколько отличается от рассмотренных выше матричных методов и состоит в определении всех путей между заданной парой узлов сети и в последующем распределении их по длине.

Для определения путей между парой узлов сети Г. Н. Поваров предлагает использовать определители особого вида - квазими­норы.

Для получения квазиминора относительно пары узлов y и z сети из структурной матрицы длин вычеркиваются z -я строка и y -й столбец.

Полученная указанным способом матрица обозначается , т. е. для рассмотренного нами примера сети

Квазиминором при элемента в матрице называется сумма , где суммирование производится по всем размещениям, из номеров рядов матрицы . При у = z пред­полагается: . В рассматриваемом примере

.

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

В работах Г. Н. Поварова показано, что если y = z, то

,

где при r = z и при . Это позволяет вычислять квазиминоры путем разложения их на меньшие квазиминоры.

Так, для рассматриваемого примера:

Получив с помощью квазиминора перечень всех путей между парой узлов сети, можно, используя описанные ранее в метоле Шимбела специальные операции, получить длину этих путей и вы­брать минимальный из них.

Так, для путей между узлами 1 и 3 в рассматриваемом примере получим:

Таким образом, описанный метод позволяет получить длину кратчайшего пути между заданной парой узлов сети и, кроме того, в процессе определения кратчайшего пути получить перечень всех путей между данной парой узлов сети, что в некоторых случаях может оказаться полезным.

Дата добавления: 2014-01-07