Задание 3. Постройте граф (схему дорог) между городами А, В, С, D, Е. Дороги: А-В, A-C, B-D, C-D, D-E. Сколько существует различных путей из А в Е, не проходящих дважды через одну вершину? Перечислите все пути или укажите их количество.

Решение:

Построим граф согласно условию:

Вершины: А, В, C, D, E.

Ребра (дороги): (А, В), (А, C), (B, D), (C, D), (D, E).

Ищем пути из А в Е, которые не проходят дважды через одну вершину.

Возможные пути:

1. А → B → D → E
2. А → C → D → E

Ответ: Существует 2 различных пути из А в Е, не проходящих дважды через одну вершину. Пути: А-В-D-E и А-C-D-E.