Қазақстан республикасының білім және ғылым министірлігі

1. А матрицасының бірінші бағанын қарап шығыңыз. Бұл бағаннан 1 бар жолды табыңыз да оған бірін жолды қосыңыз.

2. (1) пунктте құрылған матрицаның 2 бағанын қараңыз. Бұл бағаннан 1 бар жолды тауып, оған 2-жолды қосыңыз.

3.(2) пунктте құрылған матрицаның 3 бағанын қараңыз. Бұл бағаннан 1 бар жолды тауып оған 3- жолды қосыңыз.

4.Осылайша алдыңғы қадамда құрылған матрицаның келесі бағандарын қарауды жалғастырасыз. Одан 1 бар жолды тауып, оған зерттеліп отырған бағанға сәйкес жолды қосасыз.

5. Барлық бағандар қарастырылып болғанша жалғастырасыз.

Бұл С матрицасы егер G-Н-граф болса байланыстық матрица деп аталады, ал G-бағытталған граф болса жеткізуші матрица деп аталады. G графында C_ij=1 болса ғана (a_i, a_j) i≠j маршрут бар болады.

Сонымен С матрицасында G графының әр түрлі элементтерінің арасындағы байланыстың бар я жоқ екендігі турлы ақпарат болады(маршруттар арқылы).

Егер G_i-бағытталмаған байланысты граф болса, онда С байланыс матрицасының барлық элементтері 1-ге тең.

Жалпы (жағдайда) алғанда бағытталмаған графтың байланыс матрицасы граф төбелері жиынын байланыс компоненттеріне бөлетін эквиваленттік қатынас матрицасы болып табылады.

Контр жеткізу матрицасы.

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

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

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

s_ij=q_{ij *} с_ij

i

j

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

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