Өз кезегінде  м-ң (1, 2) элементі AG матрицаның (1, 4) эл-н AG (4,2)-ге көбейткеннен алынды. Демек 1-ден 3-ке жылжи отыра үш қадамнан кейін (1, 4, 2, 3) маршруты алынады.
 матриц-да (4, 2) элементі 3 ке тең, демек, ұзындығы 3 ке тең (4, 2)- маршрутының саны үшеу. Олар:(4, 1, 4, 2), (4, 2, 4, 2), (4, 2, 3, 2)
Граф төбелерінің арасында ұзындығы к-ға тең маршруттың (жол) бар жоғын анықтайтын алгоритмді қарастырайық:
Айталық,  төбелері υ1, υ2, υ3, υ4 бағытталған G графының сыбайлас матрицасы болсын. матрицасын қарастырайық. Жалпы алғанда,  орындалатындай к саны бар болса ғана  болады, басқаша айтқанда υі төбесімен υк төбесін және υк төбесімен υі төбелерін қосатын қабырға бар. Сондықтан υі төбесінен υj төбесіне апаратын ұзындығы 2-ге тең жол бар.
Теорема. Айталық, G төбелері υ1, υ2, υ3... υn және сыбайлас А матрицасы берілген бағытталған граф болсын.  мен  төбелерінің арасында  (1≤к≤n) шарты орындалса ғана ұзындығы к –ға тең жол бар болады.
Достарыңызбен бөлісу: |
