Для графа G=(Y,V) (рис.1) построить матрицы смежностей и инциденций, и по матрице смежностей – матрицу достижимостей, выделить связные (сильные) компоненты, и построить конденсацию графа. Найти число путей длиной 3 из Y₆ в Y₂
     

     
                       Рис. 1

Решение
     
Матрица смежностей:

   
     
Матрица инциденций:

  
     
Матрица достижимостей:

   
     
Матрица контрдостижимостей:

   
     
Прямое или декартовое произведение матриц:

   
     
Связные (сильные) компоненты:

{y4, y5, y6}=f
     
Конденсация графа:
     
    
     
Hайдем число путей длиной 3 из y6 в y2.