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

Задание №1

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

  A B C D
A
B
C
D

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

Решение:

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

Из полученной матрицы S3 следует, что имеется два (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

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

  A B C D E
A
B
C
D
E

Решение:

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

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

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

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

Задание №1

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

Задание №2

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

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

Вариант №1

  A B C D E
A
B
C
D
E

 

Вариант №2

  A B C D E
A
B
C
D
E

 

Вариант №3

  A B C D E
A
B
C
D
E

 

Вариант №4

  A B C D E
A
B
C
D
E

 

Вариант №5

  A B C D E
A
B
C
D
E

 

Вариант №6

  A B C D E
A
B
C
D
E

 

Вариант №7

  A B C D E
A
B
C
D
E

 

Вариант №8

  A B C D E
A
B
C
D
E

 

Вариант №8

  A B C D E
A
B
C
D
E

 

Вариант №10

  A B C D E
A
B
C
D
E

 

Вариант №9

  A B C D E
A
B
C
D
E

 

Вариант №12

  A B C D E
A
B
C
D
E

 

Вариант №11

  A B C D E
A
B
C
D
E

 

Вариант №14

  A B C D E
A
B
C
D
E

 

 

 

Вариант №15

  A B C D E
A
B
C
D
E

 

Вариант №16

  A B C D E
A
B
C
D
E

 

Вариант №17

  A B C D E
A
B
C
D
E

 

Вариант №18

  A B C D E
A
B
C
D
E

 

Вариант №19

  A B C D E
A
B
C
D
E

 

Вариант №20

  A B C D E
A
B
C
D
E