Присоединиться

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

Сколько существует различных путей из города A в город H?

Условие

На рисунке - схема дорог, связывающих города A, B, C, D, E, F, G H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город H?

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

Ответ

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

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

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

  1. Как рассуждать

    Решение. Начнем считать количество путей с конца маршрута - с города H. N_X — количество различных путей из города А в город X, N — общее число путей. В "H" можно приехать из D, E, или G, поэтому N = N_H = N_D + N_E + N _G (1) Аналогично: N_D = N_C + N_E; N_E = N_C + N_B + N_A + N_F;N_G = N_E + N_F. Добавим еще вершины: N_C = N_B + N_E = 1 + 3 = 4;N_B = N_А = 1;N_F = N_А = 1; Преобразуем вершины: N_D = N_C + N_E = 4 + 3 = 7; N_E = N_B + N_A + N_F = 1 + 1 + 1 = 3;N_G = N_E + N_F = 3 + 1 =

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

  1. Подставим в формулу (1): N = N_К = 7 + 3 + 4 =…

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

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

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

На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К11 классНа рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К11 классНа рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К11 классНа рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К11 классСколько существует различных путей из пункта А в пункт П, не проходящих11 класс
Похожая задача?Сфотографируйте своё условие — ИИ разберёт его по шагам так же
Сколько существует различных путей из города A в город H? — решение с объяснением | Lom Ai