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

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

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

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

		v1	v2	v3	v4
	v1
S=	v2
	v3
	v4

г) Если S – матрица смежности графа G, то (i,j)‑ый элемент матрицы S^k равен числу (v_i‑v_j)маршрутов длины k.

Пример: по заданной матрице смежности определить число маршрутов длины 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.