Задание 9. Схемы и графы

Простыми словами

Из дома в школу можно пройти разными улицами, и все они односторонние. Сколько разных маршрутов? Перебирать долго и легко сбиться. Есть приём: в каждый перекрёсток ведёт столько путей, сколько суммарно ведёт во все перекрёстки, откуда к нему идут стрелки.

Повышенный уровень, 1 балл. Схема дорог со стрелками — это ориентированный граф: города — вершины, дороги — дуги (рёбра со стрелкой).

Главное правило

где $N_X$ — число путей из начальной вершины в $X$, а $P_1,P_2,\dots$ — вершины, из которых в $X$ ведут стрелки. В начальную вершину — один путь: $N_A=1$.

Разбор: сколько путей из A в G

1. $N_A=1$. В B и D ведут стрелки только из A: $N_B=1$, $N_D=1$.
2. В C ведут стрелки из A, B, D: $N_C=1+1+1=3$.
3. В E — из B и C: $N_E=1+3=4$.
4. В F — из C, D, E: $N_F=3+1+4=8$.
5. В G — из E и F: $N_G=4+8=12$.

Варианты условия

Чтение схемы. Сколько дорог выходит из вершины — число стрелок, начинающихся в ней (из B — 2: в C и в E). Сколько входит — число стрелок, которые в неё упираются (в C — 3: из A, B, D).