A | B | C | D | |
A | 12 | 8 | ||
B | 12 | 5 | 6 | |
C | 8 | 5 | 2 | 4 |
D | 6 | 4 |
Что можно определить при помощи весовой матрицы? Во-первых, можно узнать, имеется ли ребро между двумя вершинами, и если имеется, то какова его длина (вес). Для этого достаточно посмотреть в соответствующую ячейку. Например, между вершинами В и С есть ребро и его вес равен 5. Во-вторых, если предположить, что вес ребер указывает расстояние, можно определить длину пути. Например, длина пути ABCD равна сумме длин ребер AB, BC и CD: 12 + 5 + 4 = 21. И наконец, при помощи весовой матрицы можно начертить сам граф.
Задача
В галактике Млечный Путь на планете Нептун 6 городов, и они последовательно пронумерованы, начиная с 1. Некоторые города соединены дорогами.
Император галактики Максимус принимает решение составить список этих
дорог на планете. Но так как он слаб в математике, просит у вас помощи.
0 | 1 | 1 | 0 | 1 | 0 |
1 | 0 | 1 | 1 | 1 | 0 |
1 | 1 | 0 | 0 | 0 | 0 |
0 | 1 | 0 | 0 | 0 | 1 |
1 | 1 | 0 | 0 | 0 | 1 |
0 | 0 | 0 | 1 | 1 | 0 |
Здесь 1 на пересечении i-й строки и j-го столбца указывает на наличие дороги между соответствующими городами. Если такая дорога имеется, следовательно, на пересечении j-го столбца и i-строки тоже будет 1.