Дискретная математика

132 Теорема 5.5. Пусть матрице А соответствует граф Gj = (V.Xj), а матрице В - граф Ог = (V.X^). Тогда матрице Л+В соответствует граф, полученный объединением ребер (дуг) графов О/ и G? на том же множестве вершин V. Доказательство. Если А=(ау), В-(Ьу), то A +B=(aij +b,j), следовательно, у графа, соответствующего матрице А+В, вершины v, и Vj соединяет ау+Ьу ребер (дуг из V,- в v,), что получается, если к ребрам (дугам) графа С/ добавить ребра (дуги) графа G2- Теорема доказана. 3, Умножете матриц смежностей. Теорема 5.6. Пусть матрице А соответствует граф Gj = (V,Xj), а матрице В - граф Сг = (V,X^. Тогда матрице АхВ отвечает мультиграф, построенный следующим образом: вершины v, и Vj соединяет столько ребер, сколько существует различных цепей из v,- в vy, составленных из двух ребер, первое из которых принадлежит графу (?/, а второе G2. Доказательство. Пусть А=(щ), B^^fbij) и им соответствуют графы Gj и Gi соответственно. По определению матрицы смежности число различных цепей вида [vi,vk,vj], где (Vi,v ^ €G,, (v^vJeGs равно aucbiy. Общее число цепей из v, в v,-, составленных из двух ребер (первая из G;, а вторая G2), пол^^чается суммированием по всем к: П К=1 ЧТО И дает (у^-элемент матрицы АхВ. Эту теорему можно обобщить и на случай произведения любого конечного числа матриц. Теорема 5.7. Пусть матрице Ai соответствует граф G, = (V.Xi), 1< i<N. Тогда матрице A=AsxA2X:.xAt^ отвечает мультиграф, построенный следующим образом; вершины v, и Vj соединены стольким числом ребер, сколько существует цепей из V( в vj, составленных из N ребер, первое из которых принадлежит G,, второе - G2 и т.д., N-t - G^- Следствие 5.1. Если А''- О, то в графе, соответствующем матрицей, нет цепи длины г. Следствие 5.2. Если G - связный граф с матрицей смежности А, то расстояние между Vj и у, для i ^ j равно наименьшему из целых чисел г, для которых (i,j)-bm элемент матрицы А'' отличен от нуля. Следствие 5.3. Пусть G - помеченный граф с матрицей смежности Л. Тогда (i,j)-vi элемент матрицы А'' равен числу цепей длины г из V( в у,-.