Уоршалл алгоритмі.
1. А матрицасының бірінші бағанын қарап шығыңыз. Бұл бағаннан 1 бар жолды табыңыз да оған бірін жолды қосыңыз.
2. (1) пунктте құрылған матрицаның 2 бағанын қараңыз. Бұл бағаннан 1 бар жолды тауып, оған 2-жолды қосыңыз.
3.(2) пунктте құрылған матрицаның 3 бағанын қараңыз. Бұл бағаннан 1 бар жолды тауып оған 3- жолды қосыңыз.
4.Осылайша алдыңғы қадамда құрылған матрицаның келесі бағандарын қарауды жалғастырасыз. Одан 1 бар жолды тауып, оған зерттеліп отырған бағанға сәйкес жолды қосасыз.
5. Барлық бағандар қарастырылып болғанша жалғастырасыз.
Жеткізу матрицасы. (bij)=E+AG+A2G+…+A2n матрицасынан төменде берілген ережемен n ретті C=(сij) матрицасын құрамыз:
Бұл С матрицасы егер G-Н-граф болса байланыстық матрица деп аталады, ал G-бағытталған граф болса жеткізуші матрица деп аталады. G графында Cij=1 болса ғана (ai, aj) i≠j маршрут бар болады.
Сонымен С матрицасында G графының әр түрлі элементтерінің арасындағы байланыстың бар я жоқ екендігі турлы ақпарат болады(маршруттар арқылы).
Егер Gi-бағытталмаған байланысты граф болса, онда С байланыс матрицасының барлық элементтері 1-ге тең.
Жалпы (жағдайда) алғанда бағытталмаған графтың байланыс матрицасы граф төбелері жиынын байланыс компоненттеріне бөлетін эквиваленттік қатынас матрицасы болып табылады.
Контр жеткізу матрицасы.
Төмендегі ережемен анықталғн Q=(qij)-матрицасын анықтаймыз.
Бұл матрицаның анықталуынан, егер С-жеткізу матрицасы болса, Q=CТ. Бұл екі матрицаларды (Q, C) графтың мықты компоненттерін табуға пайдалануға болады.
S=Q*C матрицасын қарастырамыз , мұндағы * операциясы С мен Q матрицаларының сәйкес элементтерін көбейту дегенді көрсетеді, яғни:
sij=qij * сij
матрицаның ai және aj төбелері өзара жеткізетін төбелер болса, яғни aiaj, ajai болса ғана sij=1.
Демек s матрицасы төмендегідей Е эквивалентті қатынас болып табылады: ai мен aj бірге бір мықты компонентте болса ғана ai Е aj орындалады. Демек, ai төбесі бар мықты компонент sij=1 aj элементтерінен тұрады. Суреттегі графтың жеткізуші С матрица сымен контр жеткізуші Q матрицалары төмендегідей:
, ,
S матрицаның екінші жолы бойынша 2-ші төбе кіретін мықты компонент {1,2,3} төбелерінен тұрады.
Достарыңызбен бөлісу: |