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

136 Следовательно, матрица достижимости равна: 'Л и л л"' л и и"- ' Л л и Л ' л л и и л л и л л л л л V V ~ Л л л л л л л л л л л л U л и л, .л л л Л) .л л л Л) (Л И И И\ ^ Л Л И И " Л Л Л Л ' ^Л Л И Л^ По матрицеi ' видно, что из вершины v, достижимы вершины v^, vj и v/, из вершины V2 - вермньг v j и v^; из вершины V3 ни одна вершина недостижима, а из вершины V4 достижима только веришна V3. Пусть G = (V,X) - орграф с п вершинами V/, v2,....,v „ и его матрица смежности есть некоторая матрица L. При больших значениях числа п вычисление степеней матрицы L лучше осуществлять на ЭВМ. Для этого существует алгоритм Уоршелла. Этот алгоритм генерирует последовательность матриц Wg = Z, Wj, причём элемент матрицы W). (к> 1), стоящий на пересечении /-й строки и J-ro столбца WkftJ), равен И в том и только в том случае, когда существует путь (произвольной длины) из вершины V, в вершину vj с внутренними вершинами из множества [vj, v2,...,v „}. Матрица W „ является искомой матрицей достгокимости исходного графа; L* = W „. Алгоритм Уоршелла-. begin W:=L-, for A=1 to n do for ;=1 to n do for J=l to n do v ( i j ) или {w(i,k) и w(kj)); end Мы часто ищем сложности вегцей. Где истина лежит совсем простая. С. Щтачев § 8. Критерии ИЗОМСрфиЗГпа Грефов Теорема 5.8 (критерий изохМорфизма графов). Графы G=(V,X) и G'-(V',X') с матрицами смежностей (aij) и (Оц) соответственно изоморфны