Некоторые свойства маршрутов, путей и циклов

а) В пути все вершины, кроме терминальных, имеют степень 2, а терминальные – 1.

б) Любая вершина цикла имеет степень 2 или другую четную степень.

в) Число вершин в пути на единицу больше, чем ребер, а в простом цикле число ребер равно числу вершин.

Пример: по заданной матрице смежности определить число маршрутов длины 3 между любой парой вершин в графе.

Вычислим последовательно степени матрицы S.

Из полученной матрицы S³ следует, что имеется один (v₁‑v₁)-маршрут длины 3, три (v₂‑v₁)-маршрута длины 3, один (v₃‑v₁)-маршрут длины 3, два (v₄‑v₁)-маршрута длины 3 и т.д.. Все маршруты легко восстанавливаются по матрицам S³, S² и S. Восстановим, например, (v₃‑v₁)-маршрут: элемент , равный единице, был получен в результате умножения элементов и , в свою очередь элемент получился путем умножения и . Тем самым, в формировании элемента участвовали элементы , и матрицы смежности, поэтому (v₃‑v₁)-маршрут есть последовательность вершин (3,2,4,1). Наглядным подтверждением полученного решения является рисунок 25.