начертить граф

Кратко:

1. 6 км — маршрут \(A \to D \to C \to E\): \(1+3+2=6\).
2. 10 км — маршрут \(A \to E \to D\): \(5+5=10\).

1. Граф и решение

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

Рёбра графа 1: \[ A-B=2,\quad A-C=5,\quad A-D=1,\quad B-C=1,\quad C-D=3,\quad C-E=2. \]

Примерная схема:

        B
       / \
      2   1
     /     \
    A---5---C---2---E
     \     /
      1   3
       \ /
        D

Нужно идти из \(A\) в \(E\), обязательно через \(D\).

• \(A \to D\): кратчайший путь \(A-D=1\).
• \(D \to E\): кратчайший путь \(D-C-E=3+2=5\).
• Итого: \(1+5=6\) км.

Маршрут: \(A \to D \to C \to E\).

Путь \(A-B-C-E=2+1+2=5\) короче, но он не проходит через \(D\), поэтому не подходит.

2. Граф и решение

Рёбра графа 2: \[ A-B=5,\quad A-C=6,\quad A-D=10,\quad A-E=5, \] \[ B-D=4,\quad C-D=2,\quad C-E=7,\quad D-E=5. \]

Можно нарисовать пятиугольник \(A-B-D-C-E\):

• стороны: \(A-B=5\), \(B-D=4\), \(D-C=2\), \(C-E=7\), \(E-A=5\);
• диагонали: \(A-D=10\), \(A-C=6\), \(D-E=5\).

Нужно идти из \(A\) в \(D\) через \(E\).

• \(A \to E\): кратчайший путь \(A-E=5\).
• \(E \to D\): кратчайший путь \(E-D=5\).
• Итого: \(5+5=10\) км.

Маршрут: \(A \to E \to D\).

Важно: сам по себе кратчайший путь \(A \to D\) равен \(8\) км: \(A-C-D=6+2=8\), но он не проходит через \(E\).

Ответ: 1) \(6\) км; 2) \(10\) км.