Решение основывается на следующем правиле.
Правило сложения. Пусть дан ориентированный граф, не содержащий циклов, и из вершины этого графа выходит ребра которые ведут соответственно в вершины и Пусть далее из вершины в вершину ведет путей, из вершины в вершину ведет путей, из вершины в вершину ведет путей. Пусть – количество путей из вершины в вершину . Тогда Это правило, естественно, может быть переформулировано для любого количества ребер, выходящих из данной вершины.
Имея в виду это правило, построим такую таблицу:
| | | | | | | | | | | | | | |
Вершина | | | | | | | | | | | | | | |
Куда выход | – | | |
|
| | |
|
| |
| ,
| |
|
К-во путей | | | | | | | | | | | | | | |
Во второй строке перечислены вершины, в третьей для каждой вершины указано, куда ведут ребра, выходящие из этой вершины. В четвертой строке
будем записывать количество путей из каждой вершины в вершину эти количества будем вычислять, пользуясь правилом сложения. Из самой вершины есть ровно один путь в себя – это «пустой путь». Порядок обработки вершин определяется следующим правилом: к моменту обработки вершины должно быть известно количество путей для всех вершин, куда из данной вершины ведут ребра. Порядок, в котором вершины указаны в таблице, этому правилу соответствует.
Заполняя таблицу слева направо, пользуясь правилом сложения, получим:
| | | | | | | | | | | | | | |
Вершина | | | | | | | | | | | | | | |
Куда выход | – | | |
|
| | |
|
| |
|
| |
|
К-во путей | | | | | | | | | | | | | | |