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

поэтому вычисляем матрицу 134 S _ (\ 0 1 0 ' ' 0 1 0 0^ 0 2 0 1 •1 0 1 0 X 1 0 2 0 0 1 0 1 .0 1 0 и .0 0 1 0. 0 2 0 п 2 0 3 0 0 3 0 2 1 0 2 0J Для полученной матрицы (1,4)-й элемент равен 1, следовательно, расстояние между 1-й и 4-й вершинами графа равно трём (минимальной степени матрицы Л} при котором (1,4)-й её элемент отличен от нуля) и имеется ровно одна цепь длины 3, ибо (1,4)-й элемент матрицы равен единице. Рассмотрим граф G3, диаграмма которого представлена на рис. 5.13, в). Матрица смежности графа G3 равна: А = О 1 0 л '2 0 2 0^ 0 1 0 0 2 0 2 J 0 . Тогда: А^ = 1 2 0 2 0 0 1 QJ .0 2 0 2. , А V 0 4 0 4 4 0 4 0 0 4 0 4 4 0 4 0 По матрице А^ можно определить, что из вершины v/ до вершины имеется две цеш1 длины 2; v j - v ^ - v ^ n v;-v.#-V3. По матрице можно определить, что из вершины v j до вершины имеется четыре цепи длины Ъ\ v i - V4 -v j - V2. V1-V2- V j - V2,V j - V j - Vi - V j и V j - V 4 - V1-V2. Матрица смежности остовного подграфа G* графа G, очевидно, равна: A(G*)=J - A(GJ, где J - матрица смежности полного графа, состоящая полностью из единиц, за исключением элементов диагонали. Логика стала математической, математика логической. Вследатие этого сегодш совершенно невозможно провести ipanuijy между ними. В сугцности, это одно и то же, Б. Рассел § 7. Матриць? смежности и достижимости Матрицу смежности графа (орграфа) с п вершинами вводят и как логическую пхп м а т р иц у - (4')> тагсую, что: для графа: