Умение анализировать информацию, представленную в виде схем · 52 задания
- Задание №9№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Ско…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой.…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Ско…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города A , B , C , D , E , F , G , H . По каждой дороге можно двигаться только в одном направлении, указанном ст…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Ско…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города А, B, C, D, E, G, H, F. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой. С…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой.…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой.…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Ско…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К иЛ. По каждой дороге можно двигаться только в одном направлении, указанном с…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой.…
Графы
- Задание №9№9
На рисунке – схема дорог, связывающих города А, B, C, D, E, F, G, H. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой. С…
Графы
На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G, H. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город D?
Правильный ответ
10
Пояснение
Решение. Для решения этой задачи мы воспользуемся методом динамического подсчёта путей. Суть метода заключается в том, что количество способов добраться в конкретный город равно сумме способов добраться во все города, из которых в него ведут прямые дороги.
Обозначим через N(X) количество различных путей из города А в город X.
Шаг 1. Начальная точка.
Для города А, который является началом пути, принимаем:
N(A)=1.
Шаг 2. Расчёт для промежуточных городов.
Будем двигаться последовательно от начала графа к его концу, выбирая те вершины, для которых уже известны значения всех входящих в них стрелок.
1. В город B ведёт только одна дорога из A:
N(B)=N(A)=1.
2. В город E ведёт только одна дорога из A:
N(E)=N(A)=1.
3. В город F ведут дороги из A и E:
N(F)=N(A)+N(E)=1+1=2.
4. В город G ведут дороги из E и F:
N(G)=N(E)+N(F)=1+2=3.
5. В город H ведут дороги из F и G:
N(H)=N(F)+N(G)=2+3=5.
Шаг 3. Расчёт для городов верхней ветки и финиша.
6. В город C ведут дороги из B и F:
N(C)=N(B)+N(F)=1+2=3.
7. Теперь мы можем найти количество путей в финальный город D. В него ведут дороги из городов C, F и H:
N(D)=N(C)+N(F)+N(H).
Подставим найденные значения:
N(D)=3+2+5=10.
Таким образом, существует 10 различных путей из города А в город D.
Ответ: 10
Источник: ФИПИ