Построим матрицу смежности взвешенного графа и найдем длину путей A-B-E и B-D-C-B.
Реши задание на изображении
Сверь числа и знаки с фото.
Построим матрицу смежности взвешенного графа и найдем длину путей A-B-E и B-D-C-B.
[Рисунок: вершины E, A, B, D, C. Рёбра с весами: E—A — 2; E—B — 3; A—B — 1; D—B — 4; D—C — 3; C—B — 2.]
[Таблица: матрица смежности. Столбцы: A, B, C, D, E. Строка A: A — закрашено; B — 1; C — ___; D — ___; E — 2. Строка B: A — 1; B — закрашено; C — 2; D — 4; E — 3. Строка C: A — ___; B — 2; C — закрашено; D — 3; E — ___. Строка D: A — ___; B — ___; C — ___; D — закрашено; E — ___. Строка E: A — ___; B — ___; C — ___; D — ___; E — закрашено.]
Краткий ответ: длина пути \(A-B-E\) равна \(4\), длина пути \(B-D-C-B\) равна \(9\).
В взвешенном графе длина пути — это сумма весов рёбер, а не количество рёбер.
Матрица смежности для порядка вершин \(A,B,C,D,E\):
\[ \begin{array}{c|ccccc} & A&B&C&D&E\\ \hline A&0&1&0&0&2\\ B&1&0&2&4&3\\ C&0&2&0&3&0\\ D&0&4&3&0&0\\ E&2&3&0&0&0 \end{array} \]
Пустые клетки в таблице на фото соответствуют \(0\), то есть ребра нет.
Путь \(A-B-E\): \[ A\to B: 1,\qquad B\to E: 3 \] \[ 1+3=4 \]
Путь \(B-D-C-B\): \[ B\to D: 4,\qquad D\to C: 3,\qquad C\to B: 2 \] \[ 4+3+2=9 \]
Проверка: матрица симметрична, значит граф неориентированный; веса берём прямо из соответствующих клеток матрицы.
