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

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

Условие

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

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

Ответ

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

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

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

Как рассуждать
Решение. Заметим, что дорогу В-Е можно не учитывать, так как она приводит к повторению пунктов прохождения. Тогда, посчитаем количество путей до каждого из городов:Е = Ж = 1.Д = К + Е = 1 + К.А = Д + Е = 2 + К.Б = А = 2 + К.В = Б = 2 + К.Г = Ж + В − К = 3.И = Г = 3.Н = И = 3.М = Н + И = 6.Л = М = 6.К = Л =

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

Заметим, что из полученных К для Д, А, Б и В…

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

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

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

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

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