11 класс·базовый уровень

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

Условие

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

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

Ответ

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

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

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

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

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

Шаг 2
Шаг 3
Шаг 4

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

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

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

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

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