Математика ЕГЭ
Русский язык ЕГЭ
Математика 5-7
Математика ОГЭ
Информатика
Физика
Обществознание
Кликните, чтобы открыть меню

13. Графы

1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения

Поиск количества путей в ориентированном графе

Задание 1 #14538

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

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

Решать будем динамикой.

Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Например, в города B и D можно прийти одним способом из города A. А в город С можно прийти из города B, города A или города C, поэтому количество различных путей в город С равно \( 1+1+1=3. \)

Итого получается, что в пункт J ведут 20 различных путей.

Ответ: 20

Задание 2 #14542

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

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

Решать будем динамикой.

Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Итого получается, что в пункт I ведут 27 различных путей.

Ответ: 27

Задание 3 #14541

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

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

Решать будем динамикой.

Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Итого получается, что в пункт F ведут 11 различных путей.

Ответ: 11

Задание 4 #14540

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

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

Решать будем динамикой.

Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.

Итого получается, что в пункт I ведут 17 различных путей.

Ответ: 17

Задание 5 #14539

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

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

Решать будем динамикой.

Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Итого получается, что в пункт J ведут 8 различных путей.

Ответ: 8

Задание 6 #14536

На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, X, J, Q, P, L, M, O, N. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

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

Решать будем динамикой.

Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Например, в город C можно прийти одним способом из города A, а в города B и D можно прийти одним способом из C. Тогда в город E можно прийти из города B, из города C или из города D, поэтому количество различных путей в город E равно \( 1+1+1=3. \)

Также заметим, что на графе присутствуют лишние дороги, не ведущие в город N, которые нам не нужны, и пути по которым считать не надо.

Итого получается, что в пункт N ведут 54 различных пути.

Ответ: 54

Задание 7 #14534

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

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

Решать будем динамикой.

Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Например, в города B и C можно прийти одним способом из города A. А в город D можно прийти из города B, из города A или из города С, поэтому количество различных путей в город D равно \( 1+1+1=3. \)

Итого получается, что в пункт H ведут 23 различных пути.

Ответ: 23