Задание № 22994
На карту нанесены 4 города (А, В, С и D).
Известно, что:
между городами А и С — две дороги,
между городами А и В — три дороги,
между городами В и С — четыре дороги,
между городами С и D — три дороги,
между городами В и D — три дороги.
По каждой из этих дорог можно ехать в обе стороны. Сколькими различными способами можно проехать из А в D, посещая каждый город не более одного раза?
[topic]
Рисуем граф, на котором отмечаем все города и пути между ними, начинаем подсчитывать их количество, помня, что через каждый город посещать не более одного раза
Между A и C 2 дороги, между А и B - три. Между B и C 4 дороги, если ехать по пути A=>C=>B, то количество путей будет 2*4=8, если же A=>B=>C, то 3*4=12
Получается в B можно попасть из А по прямой по 3 дорогам + 8 путей через C, итого 11 путей, а в C из A 2+12=14 путей
В город D из C ведет 3 дороги, как и из B, а это значит что в D попасть можно по 11*3+14*3=33+42=75 путям
Ответ: 75
Ответ: 75Нашли ошибку в задании? Выделите фрагмент и нажмите Ctrl + Enter.