11. Как по весовой матрице определить длину заданного пути в графе (например, длину пути ADEBC в графе, заданном весовой матрицей на рис. 1.15)?

Question

Вопрос:

Фото задания

11. Как по весовой матрице определить длину заданного пути в графе (например, длину пути ADEBC в графе, заданном весовой матрицей на рис. 1.15)?

Accepted Answer

Длина пути в графе равна сумме весов всех рёбер, входящих в этот путь.

Для пути \(A D E B C\) нужно сложить веса рёбер \(AD\), \(DE\), \(EB\) и \(BC\):

\[l(ADEBC)=w_{AD}+w_{DE}+w_{EB}+w_{BC}.\]

Эти значения берут из весовой матрицы: находят элементы, соответствующие парам вершин \((A,D)\), \((D,E)\), \((E,B)\) и \((B,C)\), а затем складывают их.

Числовое значение длины пути определить невозможно, поскольку весовая матрица или рисунок 1.15 на фотографии отсутствует.

Ответ: \(l(ADEBC)=w_{AD}+w_{DE}+w_{EB}+w_{BC}\).