Транзитивное замыкание

В ряде задач интерес представляет только сам факт существования пути, длиной не меньше 1, от вершины i до вершины j. Для решения таких задач применяется алгоритм Уоршелла.

Предположим, что матрица стоимостей С совпадает с матрицей смежности для данного орграфа G, т.е. C[i, j] =1 только в том случае, если есть дуга , и C[i, j] =0, если такой дуги не существует. Требуется определить матрицу А такую, что А[i, j] =1 тогда и только тогда, когда существует путь от вершины i до вершины j длиной не менее 1 и А[i, j] =0 – в противном случае. Такую матрицу А часто называют транзитивным замыканием матрицы смежности.

На рис. 45 показано транзитивное замыкание матрицы смежности орграфа из рис. 43.

Рис. 45 – Транзитивное замыкание матрицы смежности

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

Эта формула устанавливает, что существует путь от вершины i до вершины j, проходящих через вершины с номерами, не превышающими k, только в следующих случаях.

1. Уже существует путь от вершины i до вершины j, который проходит через вершины с номерами, не превышающими к -1.

2. Существует путь от вершины i до вершины к, проходящий через вершины с номерами, не превышающими к-1, и путь от вершины к до вершины j, который проходит через вершины с номерами, не превышающими к -1.

Не нашли, что искали? Воспользуйтесь поиском: