Построим схему дорог:

Теперь построим по ней граф, с условием, что через каждый пункт можно проходить только один раз, и по дорогам можно двигаться в обоих направлениях:

Количество путей по каждой ветви графа будет равно произведению дорог, которые отображены в этой ветви. Например:

3*4*3

3*3 и т.д.

Общее количество путей равно: 3*4*3 + 3*3 + 2*4*3 + 2*3 = 36 + 9 + 24 + 6 = 75

Ответить