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

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

Условие

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

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

Ответ

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

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

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

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

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

Шаг 2

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

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

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

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

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