Выяснение вопросов связности, достижимости и расстояний на графе по матрице смежности.
Пусть G – помеченный граф, V(G) = {1, 2, … , n} и M = (mi,j)
– матрица смежности графа G. Умножим матрицу M на себя, т.е. вычислим элементы
матрицы M2 и выясним их смысл. Элемент 
матрицы M2 в i–той строчке j–том столбце равен:
Произведения mi,kmk,j будут равны единице только в том случае,
когда вершина k является смежной с обеими вершинами i и j, т.е. если существует
маршрут длины 2 соединяющий i через k с j. В остальных случаях mi,kmk,j =
0. Поэтому есть число маршрутов
длины 2, соединяющих вершину i с вершиной j. Диагональные элементы матрицы
M2, в частности, совпадают со степенями соответствующих вершин. Точно так
же можно показать, что элементы матрицы M3 суть количества маршрутов длины
3, соединяющие соответствующие пары вершин; элементы M4 -- количества маршрутов
длины 4, и т.д.
Таким образом, расстояние между вершинами i и j равно наименьшей
степени r матрицы M такой, что (i,j)–элемент матрицы Mr отличен от 0. Так
как расстояния не могут быть больше n-1, где n – порядок графа, то для того,
чтобы найти все расстояния и выяснить другие связанные с ними вопросы, достаточно
рассмотреть степени r≤n-1. Если = 0 для всех 1 ≤ r ≤ n-1, то не существует
маршрута между вершинами i и j, и значит, граф не связан.