3.5 Графтардың матрицалары

 

Если G= (M, N) графтың ілмектері болмаса, онда оған кейбір B(G) матрицаны сәйкестікке қоюға болады. Бұл матрицаның қатарларына графтың төбелері, ал бағандарына – доғалары сәйкес келеді. , егер j-ші доға i-ші төбеде басталса, , егер j-ші доға i-ші төбеде аяқталса,  қалған жағдайларда. Мұндай матрица графтың түйістілік матрицасы деп аталады.

Мысал.

Сурет 8. Граф және оның түйістілік матрицасы.

 

G=(M, N) графтың еселі доғалары болмаса, онда оған графтың сыбайластық матрицасы деп аталатын A(G) матрицасын сәйкестікке қоюға болады. Бұл |M| өлшемді квадратты 0-1 матрица.  , егер i-ші төбеден  j-ші төбеге доға бар болса.