3. На рисунке приведена схема дорог между населенными пунктами. По каждой дороге можно передвигаться только в одном направлении, указанном стрелкой. Определите количество путей из пункта А в пункт Н, не проходящих через пункт И. Опишите решение. 33
Ниже приведён один из вариантов рассуждения, который приводит к ответу 33.
Представим схему в виде ориентированного ациклического графа, где вершины – пункты, а дуги – дороги, по которым можно двигаться только в указанном направлении.
Метод решения основан на том, что для каждой вершины можно определить количество путей от пункта A до неё. Обозначим через f(X) число путей из A в пункт X. При этом f(A) = 1 (так как стартуем из A).
Вычисляем f(·) для всех пунктов в порядке, соответствующем топологической сор...