11 класс·средний уровень

Сколько существует различных путей из пункта А в пункт С, проходящих

Условие

На рисунке представлена схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П, Р, С. По каждой дороге можно передвигаться только в направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт С, проходящих через пункт Е и при этом не проходящих через пункт М?

Рисунок к задаче

Ответ

Ответ и полный разбор откроются после входа

Посмотреть ответ

Решение по шагам

Как рассуждать
Решение. Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.При этом если путь должен не проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город наоборот обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:А = 1Г = А = 1В = А + Г = 2Б = А + В = 3Е = Б + В + Г = 6Л = Е = 6И = Е = 6Ж = Е + Л + И = 18К = Л + Ж = 24Н = И = 6П = К = 24Р = Н = 6С = К + П + Р = 54 Примечание. Необходимо найти количество различных путей из города А в город С, проходящих через город Е и не проходящих через пункт М. Ответ:

Осталось ещё 1 шаг

Шаг 2

Получить полное решение

Бесплатно · займёт минуту

Другие задачи по теме «Поиск путей в графе»

На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К11 классНа рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К11 классНа рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К11 классНа рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К11 классСколько существует различных путей из пункта А в пункт П, не проходящих11 класс

Похожая задача?Сфотографируйте своё условие — ИИ разберёт его по шагам так же