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

133 Это следствие позволяет просто (алгоритмически) определить число цепей заданной длины, соединяющих вершины v,- и vj. Рассмотрим примеры. Пусть имеем граф Gi, диаграмма которого представлена на рис. 5.13, а). Матрица смежности/1 / этого графаравна; а) Рис. 5.13 V4 в) Vj ^ 1 1 0 ' '1 1 0^ f l 1 0' А] — 1 0 1 2 и элемент a;j= 0. Вычислим = 1 0 1 X 1 0 1 О о О о ^ .0 1 o j (2 ] Г 1 2 0 . Элемент я/,? полученной матрицы равен единице (больше нуля), J О i j следовательно, расстояние междуЛ-й и 3-й вершинами графа G/ равно 2 {^минимальной степени матрицы А,, при котором (1,3)-й её элемент отличен о т нуля). Более того, имеется ровно одна цепь длины 2, ибо (1 ,3)- Р 1 её элемент равен единице. Рассмотрим граф С;, диаграмма которого представлена на рис. 5.13, б) и , используя матрицу смежности, выясним, чему равно расстояние между 1-й и 4-й вершинами графа Gi. Матрица смежностиА : графа G2 равна; А2 = 1 0 ь 0 1 — г 1 0 lo 0 1 fl 0 1 0'^ 0 2 0 1 1 0 2 0 lo 1 0 1. 0^ 0 1 о Вычислим ^4; 1 0 o"| 0 1 0 0 ^1 0 1 0 X 1 0 1 0 1 0 1 0 1 0 1 0 1 0 lo 0 1 0, Для полученной матрицы (1,4)-й элемент равен нулю,