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

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

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

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

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