Тема 7.9 Достижимость вершин в орграфе.

Вершина А достижима из вершины В, если существует путь от В до А.

Для ориентированного графа Г вводят матрицу достижимости, следующего вида:

где , если вершина достижима из вершины и , если не достижима.

Считается, что вершина достижима сама из себя, т.е. элементы главной диагонали матрицы достижимости равны 1.