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

13. Графы

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

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

Задание 1 #14522

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

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

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

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

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

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

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

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

Ответ: 12

Задание 2 #14525

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

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

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

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

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

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

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

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

Ответ: 8

Задание 3 #14524

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

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

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

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

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

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

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

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

Ответ: 19

Задание 4 #14523

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

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

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

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

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

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

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

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

Ответ: 56

Задание 5 #14526

На рисунке представлена схема дорог города Клонов АР. Сколько существует дорог из пункта А в пункт J, не проходящих через пункт I?

Посчитаем сколькими путями можно придти в каждый пункт:

Отметим красными стрелками те пути, по которым мы не сможем пройти.

Ответ: 18

Задание 6 #14521

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

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

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

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

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

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

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

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

Ответ: 20

Задание 7 #14520

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

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

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

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

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

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

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

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

Ответ: 25