Тип Д13 B13 № 27300 
Поиск путей в графе. Подсчёт путей с обязательной и избегаемой вершинами
i
На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П. Сколько существует различных путей из пункта А в пункт П, проходящих через пункт Г или через пункт Е, но не через оба этих пункта?
Решение. Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.
При этом если путь должен не проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город наоборот обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.
С помощью этого наблюдения найдём последовательно количество путей до каждого из городов, проходящих через пункт Г, но не проходящих через пункт Е:
А = 1
Б = А = 1
В = А = 1
Г = А + Б + В = 3
Д = Г = 3 (Б не учитываем, поскольку путь должен проходить через Г)
Ж = Д = 3
И = Г = 3
К = И = 3
Л = Д + Ж = 6
М = К + Л = 9
Н = Ж + Л = 9
П = Н + М + Л = 24
Теперь найдём последовательно количество путей до каждого из городов, проходящих через пункт Е, но не проходящих через пункт Г:
А = 1
Б = А = 1
Д = Б = 1
Е = Д = 1
И = Е = 1
Ж = Д = 1
К = И + Е = 2
Л = Е = 1
М = Л + К = 3
Н = Л = 1
П = Л + М + Н = 5
Таким образом, ответ — 24 + 5 = 29.
Приведем другое решение.
Найдем количество путей из пункта А в пункт П, проходящих через Г, но не через Е. Оно равно произведению количества путей из пункта А в пункт Г и количества путей из пункта Г в пункт П, не проходящих через пункт Е.
Найдем количество путей из пункта А в пункт Г:
А = 1
Б = А = 1
В = А = 1
Г = А + Б + В = 3.
Найдем количество путей из пункта Г в пункт П, не проходящих через Е (при этом Г - исходный пункт):
Г = 1
Д = Г = 1
Ж = Д = 1
И = Г = 1
К = И = 1
Л = Д + Ж = 2
М = К + Л = 3
Н = Ж + Л = 3
П = Н + М + Л = 8.
Тогда количество путей из пункта А в пункт П, проходящих через Г, но не через Е, равно 3 · 8 = 24.
Теперь найдем количество путей из пункта А в пункт П, проходящих через Е, но не проходящих через Г. Оно равно произведению количества путей из А в Е и количества путей из Е в П, при этом путь из А в Е не должен проходить через Г.
Заметим, что существует единственный путь из А в Е, не проходящий через Г. Это путь А—Б—Д—Е.
Найдем количество путей из Е в П (при этом Е - исходный пункт):
Е = 1
И = Е = 1
К = Е + И = 2
Л = Е = 1
М = К + Л = 2 + 1 = 3
Н = Л = 1
П = Л + М + Н = 1 + 3 + 1 = 5.
Тогда количество путей из пункта А в пункт П, проходящих через Е, но не через Г, равно 1 · 5 = 5.
Таким образом, ответ — 24 + 5 = 29.
Ответ: 29.
Ответ: 29
