Подсчёт путей в ориентированном графе
Сколько путей существует из вершины A в вершину S5?
S5 = S1 + S4 =
Сколько путей существует из вершины A в вершину S6?
S6 = S3 + S4 =
Сколько путей существует из вершины A в вершину B?
B = S5 + S4 + S6 =
Решение
Считаем число путей из A в каждую вершину по стрелкам графа. Число путей в вершину равно сумме чисел путей во все вершины, из которых в неё идут стрелки.
В S
В S
В S
В S
В B идут стрелки из S
💡 Почему так
Путь в вершину обязательно заканчивается стрелкой из одной из предыдущих вершин, поэтому числа путей по этим стрелкам складываются.
Ответ
✓ dzmen.ru
S
S
B =
Помогло?
