Дәріс тақырыбы: Графтар теориясы (5 сағат) Негізгі сұрақтар

Төмендегі ережемен анықталғн Q=(q_ij)-матрицасын анықтаймыз.

Бұл матрицаның анықталуынан, егер С-жеткізу матрицасы болса, Q=C^Т. Бұл екі матрицаларды (Q, C) графтың мықты компоненттерін табуға пайдалануға болады.

S=Q*C матрицасын қарастырамыз , мұндағы * операциясы С мен Q матрицаларының сәйкес элементтерін көбейту дегенді көрсетеді, яғни:

s_ij=q_{ij *} с_ij

матрицаның a_i және a_j төбелері өзара жеткізетін төбелер болса, яғни a_i a_j, a_j a_i болса ғана s_ij=1.

Демек s матрицасы төмендегідей Е эквивалентті қатынас болып табылады: a_i мен a_jбірге бір мықты компонентте болса ғана a_i Е a_jорындалады.Демек, a_i төбесі бар мықты компонент s_ij=1 a_j элементтерінен тұрады. Суреттегі графтың жеткізуші С матрица сымен контр жеткізушіQматрицалары төмендегідей:

S матрицаның екінші жолы бойынша 2-ші төбе кіретін мықты компонент {1,2,3} төбелерінен тұрады.