Контр жеткізу матрицасы.
Төмендегі ережемен анықталғн Q=(qij)-матрицасын анықтаймыз.
Бұл матрицаның анықталуынан, егер С-жеткізу матрицасы болса, Q=CТ. Бұл екі матрицаларды (Q, C) графтың мықты компоненттерін табуға пайдалануға болады.
S=Q*C матрицасын қарастырамыз , мұндағы * операциясы С мен Q матрицаларының сәйкес элементтерін көбейту дегенді көрсетеді, яғни:
sij=qij * сij
матрицаның ai және aj төбелері өзара жеткізетін төбелер болса, яғни ai aj, aj ai болса ғана sij=1.
Демек s матрицасы төмендегідей Е эквивалентті қатынас болып табылады: ai мен ajбірге бір мықты компонентте болса ғана ai Е ajорындалады.Демек, ai төбесі бар мықты компонент sij=1 aj элементтерінен тұрады. Суреттегі графтың жеткізуші С матрица сымен контр жеткізушіQматрицалары төмендегідей:
, ,
S матрицаның екінші жолы бойынша 2-ші төбе кіретін мықты компонент {1,2,3} төбелерінен тұрады.
Достарыңызбен бөлісу: |