double arrow

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


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

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

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

    v1 v2 v3 v4
v1
S= v2
v3
v4

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

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

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

Из полученной матрицы S3 следует, что имеется один (v1v1)-маршрут длины 3, три (v2v1)-маршрута длины 3, один (v3v1)-маршрут длины 3, два (v4v1)-маршрута длины 3 и т.д.. Все маршруты легко восстанавливаются по матрицам S3, S2 и S. Восстановим, например, (v3v1)-маршрут: элемент , равный единице, был получен в результате умножения элементов и , в свою очередь элемент получился путем умножения и . Тем самым, в формировании элемента участвовали элементы , и матрицы смежности, поэтому (v3v1)-маршрут есть последовательность вершин (3,2,4,1). Наглядным подтверждением полученного решения является рисунок 25.










Сейчас читают про: