Рассмотрите граф и определите количество путей из города А в город М, проходящих через город Ж, и не проходящих через город Л.

30 баллов

Ответ:

9 путей из города А в город М, проходящих через город Ж, и не проходящих через город Л

Объяснение:

Т.к. по условию пути не должны проходить через город Л, то вычеркнем пути входящие в город Л (вычеркиваем ИЛ) и выходящие из города Л (вычеркиваем ЛМ)

Т.к. по условию пути должны проходить через город Ж, то вычеркнем пути не проходящие через город Ж: вычеркиваем ЕИ (т.к. если ехать из города Е в город И, то в город Ж мы не попадаем) и ЗИ (т.к. если ехать из города З в город И, то в город Ж мы не попадаем)

Начало пути (А) - всегда 1 путь

Дальнейшее количество путей рассчитывается как сумма путей городов из которых есть пути (входящие стрелочки) в нужный город.

Вычеркнутые пути не учитываем!!!

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 1 + 1 + 2 = 4

Е = Б = 1

З = Д = 1

Ж = Б + В + Г + Е + З = 1 + 4 + 2 + 1 + 1 = 9

И = Ж = 9 (ЕИ и ЗИ вычеркнуты)

К = И = 9

М = К = 9 (ИЛ и ЛМ вычеркнуты)