На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Построим таблицу. В первую строку таблицы запишем наименование всех вершин в следующем порядке. Сначала запишем вершину К. Затем те вершины, из которых в К ведёт прямой путь и из которых в вершину К можно попасть только через уже просмотренные вершины. Далее вершины, из которых в уже просмотренные вершины ведёт прямой путь и из которых можно попасть только через уже просмотренные вершины. Получим:
| К | И | Е | З | Ж | Б | В | Г | Д | А |
Вторую строку таблицы заполним числами, соответствующими количеству исходящих путей Px(K) из просматриваемой вершины x в K. Если из вершины x выходит несколько путей, например, в вершины x1, x2, и x3, то количество путей, ведущих из этой вершины в К, будет равно сумме путей, ведущих из x1, x2, и x3 в К.
То есть Px(K) = Px1(K) + Px2(K) + Px3(K).
Например, из вершины Ж выходят пути в вершины Е, З и К. Следовательно, PЖ(K) = PЕ(K) + PЗ(K) + PК(K) = 1 + 2 + 1 = 4. Получим:
| К | И | Е | З | Ж | Б | В | Г | Д | А |
| 1 | 1 | 1 | 2 | 4 | 1 | 6 | 6 | 7 | ‘20 |
Ответ: 20