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

Определите количество различных путей ненулевой длины, которые

Условие

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

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

Ответ

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

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

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

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

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

Шаг 2

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

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

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

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

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