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