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

Решение:

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

Теперь найдём все пути из города А в город Е, не проходящие через одну вершину дважды:

1. А → В → Д → Е
2. А → С → Д → Е

Существует 2 различных пути.

Ответ: 2 пути (А-В-Д-Е, А-С-Д-Е).