Теорема.Кез келген графты қиылыспайтын байланыс компоненттерінің бірігуімен өрнектеуге болады. Графтың байланыс компоненттеріне жіктелуі бір мәнді анықталады. G=Ui G(Vi)
Сонымен, төбелердің байланысты компоненттері мен мықты компоненттер жиыны төбелер жиындарын бөлшектейді, ал байл. компоненттерінің саны бір мәнді анықталады.
Келесі теорема сыбайлас AG матрицасы бойынша G графының маршруттарын зерттеуге мүмкіндік береді.
Теорема. Егер AG-G графыың іргелестік матрицасы болса, онда матрицасының (i,j)-ші элементі ұзындығы к-ға тең (аi,j)-маршруттарының санын анықтайды.
Салдар. AG+ +…+ матрицасының (i,j)-ші элементі 0-ге тең болмаса ғана n қуатты G графында ai төбесі ішінде болатын (ai,aj) - маршрут (ai≠aj) бар.
Мысалы. Сыбайлас AG матрицаның көмегімен G графында (1,3)маршрутының бар екендігін анықтаймыз.
(1,3)- элемент 0-ге тең, демек ұзындығы 1-ге тең маршрут жоқ
(1,3)-элемент тағыда 0-ге тең. Ұзындығы 2-ге тең (1,3)-маршруты жоқ Ұзындығы 3-ке тең (1,3)-маршруттың саны 1-ге тең
Графтың суретінен бұл маршрут (1, 4, 2, 3) төбелерімен анықталады. Бұл тізбекті іргелестік матрицаны көбейту арқылы алуға болады: матр-ң (1, 3) элементі матр-ң (1, 2) элементімен AG матрицаның (2, 3) элементін көбейткеннен алынады.
Өз кезегінде м-ң (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) шарты орындалса ғана ұзындығы к –ға тең жол бар болады.
Достарыңызбен бөлісу: |