Теория графов и комбинаторика

в случае яоавдографов .диагональные йлачанта матрицы ACS) mryr йыть каравшми нулю (эл&мент АцФ- О , ео™ нмавтоя патлч: в верагане Vl ). Матрвдей смаетости орв^1!тарованного мулътатрафа (лоавдо- графа) называется матрица /1-рхр . C i j ) -2 элемент которой a^j равен числу дуг T i j = (.1Гс,тГ^) , соединяющих вэршину ITj. о вврнганой ' Матрица смеянос|и оографа, вообще говоря, не явжвтоя симметричной ( Д ),_Сймм0триаацш1 орграфа можно. добиться гмметризациой матрщы Д (.6^). Теоремы, аналогячше теореме 5.2, справ9дап!БК и даш муль- графов, поввдографой и орграфов. Например, Р ) - орграф с петлями к кратшли вдгами, то элемент матрицы Л* равен адолу МГ,; ~ ) -путой дашьш У) . Пользуяоь этим у'гв(зр:аден11вм, легко заметить, что йоли c j ' - щеотзует Ио такое, что О пр" =')>i(o , то в ориентированном мультиграйе нет контуров. Покойные разультатк оправеддавы и дам простых графов. §5.4. »атп!1ца пкг^'ОБ Пусть <?•= (V, X ) -граф, вершины и ребра которого перену- морованы. Перенумеруем все проотне цшиш графа • Матрицей циклов называется матргща С(^) ^ ^ ) , отроки которой ооотаототвуют гг^оотым "И1слам, а отолбцы - ped- рам граф?) G , причем элемент , если >- -й цикл сод?-1- жят j -а ребро, п - в противном сл^'чао. В отлитле от матриц/1 ((г) и В (б-) матрзда цшаов С^&) ив определяет граф о точность- до изоморфизма. Например,- ео-'Ч pot3poX' не цриладажит вд одному циклу, то удалэние этого реб­ ра не изменит матрицы CiG). В этом о.чучае С(б^-зс ) , хотя (г - X . Даже если нет таких ребер, то зое равно матрица С на определяет граф о точностью до изоморфизма. Это видно па примере графов, иаображвншк на рио.5.1, которые име­ ют Одинаковые матрицы циклов. Между матрицей циклов • С и мат- . рицай инциденцай Е> существует овязъ. 1±!> <а> а) б) Рио.5.1 36 ,