На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Определите количество различных путей не нулевой длины, которые начинаются и заканчиваются в городе Е, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза.
Для начала давайте выясним сколько путей начинается в городе Е. Т.е. находим те пути которые выходят из города Е.
Видим что есть два пути - это ЕЛ и ЕВ. Дальше нужно найти количество путей выходящих из города Л и В. Видим что в город В ведет только один путь из города Е. А вот в город Л мы пока не знаем сколько путей ведёт, потому что мы не знаем сколько путей ведёт в город И.
Дальше смотрим куда ведут пути из города В. Это города Г, А, Б, Д.
Обратите внимание что в город А можно попасть только из города В, а так как в город В ведёт только один путь, то и в А тоже ведет только один путь.
Дальше в города Б и Г можно попасть из городов А(1) и В(1). Посчитаем количество путей ведущих в Б = 1(А) + 1(В) = 2 (количество путей ведущих в город Б). Точно так же и в город Г ведет два пути Г =1(А) + 1(В) = 2.
Из города Г можно попасть в город Е (это конечная точка и считать её нужно в последнюю очередь, когда будут известны все пути из всех возможных городов. В точке Ж мы пока тоже не можем посчитать количество путей, пока не узнаем сколько путей ведет в город Л.
Поэтому нам нужно найти количество путей ведущих в город Д. В него мы можем попасть из города В(1) и города Б(2). Считаем Д = 1(В) + 2 (Б) = 3 пути.
Тут мы можем сразу написать, что количество путей ведущих в город И равно трем, потому что в город И можно попасть только из города Д.
Вот мы и дошли до города Л. А в него можно попасть из трех городов - это города Е(1), Д(3), И(3). Считаем Л= 1(Е) + 3(Д) + 3(И) = 7 путей, ведет в город Л.
В город К можно попасть только из города Л, значит в него ведёт 7 пцутей. А в город Ж можно попасть из городов К(7), Л(7), Г(2_. Ж=2 + 7 + 7 = 16 путе ведёт в город Ж.
Теперь у нас есть все данные, для того чтобы найти количество путей ведущих в город Е. Е = 2(Г) + 3(Д) + Ж(16) = 21 путь ведёт из города Е в город Е.
Подписывайтесь на мой канал! Пишите в комментариях, разборы каких заданий вы хотите увидеть на моём канале!
