Решение задач на графах: Путь через точку

Ниже представлено решение задач со второй страницы. Для каждой задачи мы используем метод динамического суммирования путей, учитывая обязательные пункты прохождения. Задача №21 Условие: Найти количество путей из А в Л, проходящих через пункт Е. Решение: 1. Считаем пути до Е: \(N_A = 1\) \(N_Б = N_A = 1\) \(N_В = N_A + N_Б = 1 + 1 = 2\) \(N_Е = N_Б + N_В = 1 + 2 = 3\) 2. Считаем пути от Е до Л: Из Е можно попасть в И и в З. \(N_И = N_Е = 3\) \(N_З = N_Е = 3\) (другие стрелки в З не учитываем, так как они идут в обход Е) \(N_Л = N_И + N_З = 3 + 3 = 6\) (Стрелка Ж-Л не учитывается, так как путь через Ж не проходит через Е). Ответ: 6. Задача №22 Условие: Найти количество путей из А в Л, проходящих через пункт З. Решение: 1. Считаем пути до З: \(N_A = 1\) \(N_Б = N_A = 1\) \(N_В = N_A + N_Б = 1 + 1 = 2\) \(N_Г = N_A + N_В = 1 + 2 = 3\) \(N_Д = N_A + N_Г = 1 + 3 = 4\) \(N_Е = N_Б + N_В = 1 + 2 = 3\) \(N_Ж = N_Г + N_Д = 3 + 4 = 7\) \(N_З = N_В + N_Е + N_Ж = 2 + 3 + 7 = 12\) 2. Считаем пути от З до Л: Из З есть только одна прямая стрелка в Л. \(N_Л = N_З = 12\) (Стрелки И-Л и Ж-Л не учитываются, так как они идут в обход З). Ответ: 12. Задача №23 Условие: Найти количество путей из А в Л, проходящих через пункт В. Решение: 1. Считаем пути до В: \(N_A = 1\) \(N_Б = N_A = 1\) \(N_В = N_A + N_Б = 1 + 1 = 2\) 2. Считаем пути от В до Л: \(N_Г = N_В = 2\) (стрелка А-Г не учитывается) \(N_Д = N_Г = 2\) (стрелка А-Д не учитывается) \(N_Е = N_В = 2\) (стрелка Б-Е не учитывается) \(N_Ж = N_Г + N_Д = 2 + 2 = 4\) \(N_З = N_В + N_Е + N_Ж = 2 + 2 + 4 = 8\) \(N_И = N_Е = 2\) \(N_Л = N_И + N_З + N_Ж = 2 + 8 + 4 = 14\) Ответ: 14. Задача №24 Условие: Найти количество путей из А в К, проходящих через пункт В. Решение: 1. Считаем пути до В: \(N_A = 1\) \(N_Б = N_A = 1\) \(N_Г = N_A = 1\) \(N_В = N_Б + N_A + N_Г = 1 + 1 + 1 = 3\) 2. Считаем пути от В до К: \(N_Д = N_В = 3\) (стрелка Б-Д не учитывается) \(N_Е = N_В = 3\) \(N_Ж = N_В = 3\) (стрелка Г-Ж не учитывается) \(N_К = N_Д + N_Е + N_Ж = 3 + 3 + 3 = 9\) Ответ: 9.