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

13. Графы

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

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

Задание 1 #14506

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

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

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

Зачеркнём те дороги, по которым нам двигаться нельзя. (Те, которые идут в город I или выходят из него)

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

Если по дороге двигаться запрещено, количество путей, проходящих через неё равно нулю.

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

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

Ответ: 4

Задание 2 #14507

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

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

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

Зачеркнём те дороги, по которым нам двигаться нельзя. (Те, которые идут в город D или выходят из него)

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

Если по дороге двигаться запрещено, количество путей, проходящих через неё равно нулю.

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

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

Ответ: 8

Задание 3 #14508

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

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

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

Зачеркнём те дороги, по которым нам двигаться нельзя. (Те, которые идут в город I или выходят из него)

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

Если по дороге двигаться запрещено, количество путей, проходящих через неё равно нулю.

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

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

Ответ: 6

Задание 4 #14509

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

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

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

Зачеркнём те дороги, по которым нам двигаться нельзя. (Те, которые идут в город K или выходят из него)

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

Если по дороге двигаться запрещено, количество путей, проходящих через неё равно нулю.

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

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

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

Ответ: 36

Задание 5 #14510

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

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

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

Зачеркнём те дороги, по которым нам двигаться нельзя. (Те, которые идут в город J или выходят из него)

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

Если по дороге двигаться запрещено, количество путей, проходящих через неё равно нулю.

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

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

Ответ: 10

Задание 6 #14511

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

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

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

Зачеркнём те дороги, по которым нам двигаться нельзя. (Те, которые идут в город K или выходят из него)

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

Если по дороге двигаться запрещено, количество путей, проходящих через неё равно нулю.

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

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

Ответ: 10

Задание 7 #14512

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

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

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

Зачеркнём те дороги, по которым нам двигаться нельзя. (Те, которые идут в город D или выходят из него)

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

Если по дороге двигаться запрещено, количество путей, проходящих через неё равно нулю.

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

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

Ответ: 6