На этом шаге мы рассмотрим Назначение и особенности матрицы достижимости.

    Рассмотрим, следуя монографии [1, с. 439], степени матрицы смежностей ориентированного графа G=(V,E). Единица в i-й строке и j-м столбце матрицы смежностей A указывает на наличие дуги (v_i,v_j), т.е. на наличие пути длины 1 из вершины v_i в вершину v_j. Обозначим элементы матрицы A² через a⁽²⁾_ij. Тогда

    Для каждого k=1, 2, ..., n условие a_ik*a_kj=1 выполняется тогда и только тогда, когда оба элемента a_ik и a_kj равны 1, т.е. в графе имеются дуги (v_i,v_k) и (v_k,v_j). Для каждого такого k мы получаем "единичный вклад" в сумму. Наличие дуг (v_i,v_k) и (v_k,v_j), означает, что существует путь из v_i в v_j длины 2. Тем самым a⁽²⁾_ij равно числу различных путей длины 2 из v_i в v_j. Аналогично диагональный элемент a⁽²⁾_ii указывает число циклов длины 2 в вершине i для любого i=1, 2, ..., n.

    С помощью подобной аргументации мы можем показать, что элемент в i-й строке и j-м столбце матрицы A³ задает количество путей длины 3 из вершины v_i в вершину v_j.

    В общем случае может быть доказано следующее утверждение.

Теорема.

Пусть A - матрица смежностей ориентированного графа G. Элемент на пересечении i-й строки и j-го столбца матрицы Aⁿ равен количеству путей длины n из i-й вершины в j-ю вершину.

    Ясно, что получив матрицу B_n=A + A²+ ... + Aⁿ, можно определить количество путей из v_i в v_j длины, меньшей или равной n.

    Если бы требовалось определить, достижима ли вершина v_j из вершины v_i, было бы необходимо исследовать, существует ли путь любой длины из вершины v_i в вершину v_j. Чтобы решить этот вопрос с помощью матрицы смежностей, мы должны были бы рассмотреть все возможные A^k для k=1, 2, ...; однако этот метод не является рациональным.

    Пусть G=(V,E) - ориентированный граф, содержащий n вершин.

Определение.

Матрица P размерности n × n, элементы которой задаются выражением

        ⌈ 1, если существует путь из вершины vi в вершину vj;
 pij ⇔ 
        ⌊ 0, в противном случае.
   

называется  матрицей достижимости (путевой матрицей) графа G.

    Матрица достижимости лишь показывает, имеется или отсутствует по крайней мере один путь между парой вершин графа, а также имеется или отсутствует контур в любой вершине. Вместе с тем, она не определяет все пути, которые могут существовать. В этом смысле матрица достижимости не дает столь полной информации о графе, как матрица смежностей. Однако матрица достижимости важна сама по себе.

    Её можно получить из матрицы B_n, положив

        ⌈ 1, если bij ∈ Bn и bij ≠ 0;
 pij ⇔ 
        ⌊ 0, в противном случае.
   

    Например, если

    На следующем шаге мы рассмотрим другие матричные представления.

Предыдущий шаг Содержание Следующий шаг