Матрица достижимости

Матрица достижимости (Reachability matrix) — квадратная [math]\displaystyle{ \,(0,1) }[/math]-матрица [math]\displaystyle{ \,R(G) }[/math] размером [math]\displaystyle{ n \times n }[/math] ([math]\displaystyle{ \,n }[/math] — число вершин в [math]\displaystyle{ \,G }[/math]), [math]\displaystyle{ \,(i,j) }[/math]-й элемент [math]\displaystyle{ \,r_{ij} }[/math] которой равен [math]\displaystyle{ \,1 }[/math], если в [math]\displaystyle{ \,G }[/math] существует путь из [math]\displaystyle{ \,v_{i} }[/math] в [math]\displaystyle{ \,v_{j} }[/math] (вершина [math]\displaystyle{ \,v_{j} }[/math] достижима из [math]\displaystyle{ \,v_{i} }[/math], и равен [math]\displaystyle{ \,0 }[/math] в противном случае.

См.

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

Литература

• Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.

• Харари Ф. Теория графов. — М.: Мир, 1973.