Question

На карту нанесены 4 города A B C и D известно, что:
между городами A и C - две дороги.
между городами А и В - две дороги
между городами C и D - три дороги
между городами B и D - четыре дороги.
По каждой из этих дорог можно ехать в обе стороны. Сколькими различными можно проехать из А в D, посещая каждый город не более одного раза​

Answer 1

Для решения этой задачи, сперва построим граф, где вершинами будут города, а ребрами - дороги между ними. Затем, с помощью глубокого поиска (DFS) или алгоритма поиска в ширину (BFS), посчитаем количество путей из города A в город D.

Для начала построим граф:

A
/ \
B C
\ /
D

У нас есть 4 города (A, B, C и D), и нам нужно посетить каждый город не более одного раза. То есть, после прохода через город, мы не можем вернуться в него снова.

Так как между городами A и C есть две дороги, мы можем выбрать любую из них. Пусть мы выбрали одну из этих дорог:

A <---> C
/ \
B C
\ /
D

Теперь, мы можем выбрать любую из двух дорог, чтобы попасть из A в B. Пусть выберем одну из них:

A <---> C
/ \
B C
\ /
D

Теперь, чтобы попасть в город D, нам необходимо выбрать одну из четырех дорог, ведущих от B к D:

A <---> C
/ \
B C
\ ---> /
D

Таким образом, мы попадем в город D.

Используя эту комбинацию дорог, мы можем проехать из города A в город D, посетив каждый город по одному разу.

Теперь давайте рассмотрим другие возможные комбинации дорог:

1) Если мы выберем вторую дорогу между городами A и C вместо первой и взглянем на оставшуюся часть графа, у нас будет следующая ситуация:

A <---> C
/ \
B C
\
D

Здесь мы снова можем выбрать одну из двух дорог, чтобы попасть из A в B:

A <---> C
/ \
B C
\
D

И, наконец, мы можем выбрать одну из четырех дорог, чтобы попасть в D. Таким образом, мы снова найдем путь из A в D, посетив каждый город по одному разу.

2) Если мы рассмотрим третью дорогу между городами A и C, остальной граф будет выглядеть так:

A <---> C
\ / \
B C C
\ /
D

Снова, мы выбираем одну из двух дорог, чтобы попасть из A в B, и одну из четырех дорог, чтобы попасть из B в D. Мы снова обнаруживаем путь из A в D с посещением каждого города только один раз.

3) Если мы рассмотрим последнюю, четвертую дорогу между городами A и C, остальной граф будет выглядеть так:

A <---> C
\ / \
B C C
\ /
D

Точно также, мы можем выбрать одну из двух дорог, чтобы попасть из A в B, и одну из четырех дорог, чтобы попасть из B в D. Мы получаем путь из A в D с посещением каждого города только один раз.

Итак, мы обнаружили, что существует 4 различных пути из города A в город D, посещая каждый город не более одного раза.