17.Постройте матрицы смежности для каждой весовой матрицы и граф a b c d e f g a 0 0 0 0 0 0 0 b 1 0 0 0 1 0 1 c 2 5 0 0 0 0 0 d 0 1 0 1 0 0 0 e 0 0 1 0 2 0 0 f 0 2 0 0 0 0 1 g 0 0 0 2 0 0 0 a b c d e f g a 4 4 0 0 1 1 0 b 2 0 0 0 1 0 1 c 0 2 2 1 0 0 1 D 0 0 0 0 1 0 0 E 1 0 0 0 0 0 0 F 0 2 0 3 0 0 5 G 0 0 0 0 1 0 0

Для построения матриц смежности нам необходимо учитывать, что в графах могут присутствовать как ориентированные (весовые), так и неориентированные связи между вершинами.

1. Матрица смежности для первой весовой матрицы:

Данная матрица весов выглядит следующим образом:

     a b c d e f g
a [  0 0 0 0 0 0 0 ]
b [  1 0 0 0 1 0 1 ]
c [  2 5 0 0 0 0 0 ]
d [  0 1 0 1 0 0 0 ]
e [  0 0 1 0 2 0 0 ]
f [  0 2 0 0 0 0 1 ]
g [  0 0 0 2 0 0 0 ]

Чтобы построить матрицу смежности, мы будем учитывать, что если в весовой матрице есть ненулевая ячейка, то между соответствующими вершинами существует связь. Мы можем представить её следующим образом (1 - связь существует, 0 - отсутствует):

Матрица смежности:

     a b c d e f g
a [  0 0 0 0 0 0 0 ]
b [  1 0 0 0 1 0 1 ]
c [  1 1 0 0 0 0 0 ]
d [  0 1 0 1 0 0 0 ]
e [  0 0 1 0 1 0 0 ]
f [  0 1 0 0 0 0 1 ]
g [  0 0 0 1 0 0 0 ]

2. Матрица смежности для второй весовой матрицы:

Вторая весовая матрица:

     a b c d e f g
a [  4 4 0 0 1 1 0 ]
b [  2 0 0 0 1 0 1 ]
c [  0 2 2 1 0 0 1 ]
d [  0 0 0 0 1 0 0 ]
e [  1 0 0 0 0 0 0 ]
f [  0 2 0 3 0 0 5 ]
g [  0 0 0 0 1 0 0 ]

Также составим матрицу смежности (где 1 - связь, 0 - отсутствует):

Матрица смежности:

     a b c d e f g
a [  0 1 0 0 1 1 0 ]
b [  1 0 0 0 1 0 1 ]
c [  0 1 1 1 0 0 1 ]
d [  0 0 0 0 1 0 0 ]
e [  1 0 0 0 0 0 0 ]
f [  0 1 0 1 0 0 1 ]
g [  0 0 0 0 1 0 0 ]

Обратите внимание

В отличие от простых матриц смежности, весовая матрица сохраняет информацию о весах, а в матрицах смежности она подразумевает наличие или отсутствие связи, не учитывая вес. Если в ваших расчетах вес имеет значение, учитывайте это в соответствующем контексте задачи.