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

131 При другой нумерации вершин получим другую матрицу, получающуюся из А перестарювкой строк и столбцов. Но в результате всегда получится симметричная матрица из неотрицательных целых чисел, обладающая тем свойством, что сумма чисел в любой г-й строке или г'-м столбце равна локальной степени соответствующей вершины v „ 1< i< п. Здесь калсдая петля учитывается в степени вершины только один раз, Обратно, по любой заданной симметричной матрице А из неотрицательных целых чисел легко построить граф (единственный с точностью до изоморфизма), матрицей смежности которого будет матрица^. Таким образом, вместо графов можно исследовать матрицы смежности либо наоборот. Для орграфа G матрица смежности есть пт матрица^4 =fa/P, где ау - число д у г , и д ущи х из V,- в Vj. На рис. 5.12 приведён пример орграфа, а справа от него построена .Матрица смежности этого орграфа. Сумма элементов по г-й строке матрицы равна полустепени исхода j'-й вершины орграфа, а сумма элементов по7-му столбцу - полустепени захода /—й вершины. Легко видеть, что матрица смелшости А орграфа уже не является симметричной матрицей. Но это - матрица целых неотрицательных чисел и д л я любой такой матрицы А можно построить граф (с точностью до изоморфизма), матрица смежности которого равна^4. В результате видим, что исследование графов равносильно исследованию матриц смежностей, составленных из целых неотрицательных чисел. Выясним, каким операциям над графами соответствуют операции над матрицами смежностей. 1. Умножению матрицы смежности А на целое число а соответствует TOiviy, что в 13)афе каждое ребро заменяется а ребрами. 2. При сложение матриц смежностей А+В (одного и того же порядка пхп) имеет место следующая теорема. А = 'О I 1 Л1=5 0 0 10 J 0 0 0 0 О [О О J 0) 1 О 1 3 1 Рис. 5.12