Задание: На рисунке показана схема дорог, связывающих города A, B, C, D, E, F, G, H, I, J. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город J?
Решение: Обратите внимание, чтобы попасть в пункт J из пунктов A..F, нужно обязательно пройти через пункт G, из которого существует три пути в пункт J. То есть мы можем найти все пути из A в G, и умножить их на 3.
Для решения построим граф:
Шаг 1. Из пункта А пути ведут в пункты B, C, D:
Шаг 2. Из пункта B пути ведут в пункты C и E:
Шаг 3. Из пункта C пути ведут в E, G, F, из пункта E — только в пункт G:
Конечный пункт (G) для удобства обведем кружком.
Шаг 4. Из пунктов E и F существует по одному пути в пункт G:
Шаг 5. Как мы видим по построенному графу, из пункта C существует три пути в пункт G. Не будем снова расписывать все пути, просто поставим тройку для пункта C:
Шаг 6. Схема симметрична, логично предположить, что из D в G столько же путей, сколько из B в G, то есть 4. Отметим это на графе:
Остаётся посчитать:
1+1+1+1+3+4 = 11
Но мы искали пути из A в G, а нам нужно количество путей из A в J. Как мы решили в начале, для этого нужно умножить количество путей из A в G на 3:
11*3 = 33
Ответ: 33
