Решение задачи: Найти количество маршрутов из А в К, не проходящих через Г

Задача: Найти количество маршрутов из А в К, не проходящих через пункт Г. Решение: Для решения задачи воспользуемся методом динамического программирования, последовательно вычисляя количество путей в каждую вершину графа. Так как по условию маршрут не должен проходить через пункт Г, мы исключаем этот пункт и все связанные с ним ребра из рассмотрения. Обозначим \( N(X) \) — количество путей из вершины А в вершину X. 1. Начальная точка: \( N(A) = 1 \) 2. Пункт В (в него ведет стрелка из А): \( N(B) = N(A) = 1 \) 3. Пункт И (в него ведут стрелки из А и В): \( N(И) = N(A) + N(B) = 1 + 1 = 2 \) 4. Пункт Б (в него ведут стрелки из А и И): \( N(Б) = N(A) + N(И) = 1 + 2 = 3 \) 5. Пункт Д (в него ведет стрелка из В): \( N(Д) = N(B) = 1 \) 6. Пункт Г исключаем по условию задачи, поэтому \( N(Г) = 0 \). Все пути, идущие в Г или из Г, не учитываются. 7. Пункт Е (в него ведут стрелки из И, Д и Г). Так как Г исключен: \( N(Е) = N(И) + N(Д) = 2 + 1 = 3 \) 8. Пункт Ж (в него ведет стрелка из Е): \( N(Ж) = N(Е) = 3 \) 9. Пункт З (в него ведет стрелка из Е): \( N(З) = N(Е) = 3 \) 10. Пункт К (в него ведут стрелки из З, Е и Ж): \( N(К) = N(З) + N(Е) + N(Ж) = 3 + 3 + 3 = 9 \) Ответ: 9.