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

По каждой дороге можно передвигаться только в направлении, указанном

Условие

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

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

Ответ

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

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

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

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

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

Полный разбор с проверкой ответа

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

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

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

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

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