Определение 1. Пусть G – неориентированный граф. Пусть Mc – квадратная матрица, строки и столбцы которой обозначены вершинами неориентированного графа G. Элемент i-ой строки и j-гo столбца матрицы Mc, обозначаемый cij, равен единице, если имеется ребро из i-ой вершины в j-ую вершину, и равен нулю в противном случае. Матрица Mc называется матрицей смежности графа G. Заметим, что для сокращения записи обозначения строк и столбцов в матрицах смежности можно опускать, но рекомендуется их оставлять особенно в матрицах больших размерностей...

Определение. Пусть G – связный неориентированный граф, включающий вершины u и v. Расстоянием d(u, v) между вершинами u и v называется длина самой короткой цепи, соединяющей эти вершины. По определению d(u, u) = 0. Заметим, что введенное таким образом понятие расстояния между вершинами удовлетворяет аксиомам метрики: 1) d(u, v) больше либо равно 0; 2) d(u, v) = 0 тогда и только тогда, когда u = v; 3) d(u, v) = d(v,u); 4) справедливо неравенство треугольника: d(u,w) меньше либо равно d(u,v) + d(v,w)...