Метод возведения в степень матрицы узловых связей

Суть метода возведения матрицы C в степень состоит в следующем. Если возвести матрицу C в квадрат (как обычные вещественные матрицы), то , т.е. элемент матрицы будет содержать все пути от i-ого узла к k-ому, состоящие как из одной дуги, так и из двух. Куб матрицы C позволяет уже получить все пути из одной, двух и трёх друг. Возведя матрицу в степень N-1, где N – размер матрицы, мы получим все возможные пути длиной до N-1 между всем элементами, т.е. все возможные пути:

Поскольку мы ищем путь от узла 1 к узлу 4, то искомая ФРС будет равна:

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

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