Тема: Маршруты, циклы, связность.

Задание №1

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

Восстановить маршрут из вершины С в вершину А.

Решение:

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

Из полученной матрицы S ³ следует, что имеется два (A-A)-маршрута длины 3, четыре (B-A)-маршрута длины 3, один (C-A)-маршрут длины 3, три (D-A)-маршрута длины 3, т.е. число в (i, j) ячейке определяет количество маршрутов длины 3 из i-ой вершины в j-ую вершину.

Восстановим (C-A)-маршрут: элемент , равный единице, был получен в результате умножения элементов и , в свою очередь элемент получился путем умножения и . Тем самым, в формировании элемента участвовали элементы , и матрицы смежности, поэтому (C-A)-маршрут есть последовательность вершин (C, B, D, A).

Задание №2

По заданной матрице определить сильные компоненты связности графа:

Решение:

Максимальная степень, в которую надо возвести матрицу смежность для определения сильных компонент связности равна диаметру графа. Для данного графа диаметр равен 3. Возведём матрицу смежности в 3 степень:

Компоненте сильной связности в матрице достижимости соответствует подматрица максимального размера, каждый элемент которой не равен 0. В данной матрице можно выделить три подматрицы: , (2), (2).

Это значит, что граф, описанный матрицей смежности имеет три сильные компоненты: {A, B, C}, {D}, {E}.

Задания для самостоятельного решения:

Задание №1

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

Задание №2

По заданной матрице определить сильные компоненты связности графа

Варианты заданий: