Решение задач на графах: Подсчет путей (ЕГЭ)

Ниже представлено решение задач со страницы. Для решения используется метод динамического подсчета путей: количество путей в пункт равно сумме путей из всех пунктов, из которых в него ведут стрелки. Задача №17 Условие: Найти количество путей из А в К, не проходящих через пункт В. Решение: Так как путь не должен проходить через В, мы мысленно удаляем этот пункт и все связанные с ним стрелки. \(N_A = 1\) (начальный пункт) \(N_Б = N_A = 1\) \(N_Г = N_A = 1\) \(N_Д = N_Б = 1\) (стрелка из В не учитывается) \(N_Е = N_Д = 1\) (стрелка из В не учитывается) \(N_Ж = N_Д + N_Е = 1 + 1 = 2\) \(N_И = N_Г = 1\) \(N_К = N_Ж + N_И = 2 + 1 = 3\) Ответ: 3. Задача №18 Условие: Найти количество путей из А в М, проходящих через Ж, но не проходящих через К. Решение: 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\) Из Ж можно попасть в Л. \(N_Л = N_Ж = 12\) В пункт М ведут стрелки из И, К и Л. Так как через К идти нельзя, берем только И и Л. \(N_М = N_И + N_Л = 12 + 12 = 24\) Ответ: 24. Задача №19 Условие: Найти количество путей из А в К, проходящих через Ж. Решение: 1. Считаем пути до Ж. \(N_A = 1\) \(N_Б = N_A = 1\) \(N_В = N_A = 1\) \(N_Г = N_Б = 1\) \(N_Д = N_В = 1\) \(N_Ж = N_Б + N_Г + N_Д + N_В = 1 + 1 + 1 + 1 = 4\) 2. Считаем пути от Ж до К. Из Ж можно пойти в Е или сразу в К. \(N_Е = N_Г + N_Ж\). Но так как мы обязаны пройти через Ж, путь А-Б-Г-Е не подходит. Значит, в Е учитываем только стрелку из Ж. \(N_Е = N_Ж = 4\) \(N_К = N_Е + N_Ж + N_Д\). Аналогично, путь через Д должен был пройти через Ж, но из Д в Ж стрелки нет. Значит, пути через Д не могут содержать Ж после посещения Д. Однако, в Ж можно попасть ИЗ Д? Нет, стрелка идет из В в Д и из Д в Ж. Пересчитаем Ж внимательнее: стрелки в Ж идут из Б, Г, Д, В. \(N_Д = N_В = 1\) \(N_Ж = 1(Б) + 1(Г) + 1(Д) + 1(В) = 4\) Теперь пути в К, которые гарантированно прошли через Ж: \(N_Е(через Ж) = N_Ж = 4\) \(N_К = N_Е(через Ж) + N_Ж = 4 + 4 = 8\) (Стрелка Д-К не учитывается, так как она идет в обход Ж). Ответ: 8. Задача №20 Условие: Найти количество путей из А в Л, проходящих через Г. Решение: 1. Пути до Г: \(N_A = 1\) \(N_В = N_A = 1\) \(N_Г = N_A + N_В = 1 + 1 = 2\) 2. Пути от Г до Л (все пути должны включать Г, поэтому игнорируем ветки, идущие в обход Г, например А-Б-Е): \(N_Д = N_Г = 2\) \(N_Ж = N_Г + N_Д = 2 + 2 = 4\) \(N_З = N_Г + N_Ж = 2 + 4 = 6\) \(N_Л = N_З + N_Ж = 6 + 4 = 10\) (Пути через Б, Е, И не учитываются, так как они не проходят через Г). Ответ: 10.