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

13. Графы

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

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

Задание 1 #14464

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

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

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

Закрасим нужный город красным.

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

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

Красным отметим только те дороги, которые так или иначе ведут в красный город. Не будем отмечать вовсе те дороги, которые никак не ведут в него. Напишем зелёным цветом над красным городом кол-во различных путей в него. Теперь мы можем оперировать только им.

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

Ответ: 15

Задание 2 #14467

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

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

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

Закрасим нужный город красным.

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

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

Красным отметим только те дороги, которые так или иначе ведут в красный город. Не будем отмечать вовсе те дороги, которые никак не ведут в него. Напишем зелёным цветом над красным городом кол-во различных путей в него. Теперь мы можем оперировать только им.

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

Ответ: 12

Задание 3 #14466

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

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

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

Закрасим нужный город красным.

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

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

Красным отметим только те дороги, которые так или иначе ведут в красный город. Не будем отмечать вовсе те дороги, которые никак не ведут в него. Напишем зелёным цветом над красным городом кол-во различных путей в него. Теперь мы можем оперировать только им.

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

Ответ: 10

Задание 4 #14465

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

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

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

Закрасим нужный город красным.

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

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

Красным отметим только те дороги, которые так или иначе ведут в красный город. Не будем отмечать вовсе те дороги, которые никак не ведут в него. Напишем зелёным цветом над красным городом кол-во различных путей в него. Теперь мы можем оперировать только им.

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

Ответ: 24

Задание 5 #14468

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

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

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

Закрасим нужный город красным.

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

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

Красным отметим только те дороги, которые так или иначе ведут в красный город. Не будем отмечать вовсе те дороги, которые никак не ведут в него. Напишем зелёным цветом над красным городом кол-во различных путей в него. Теперь мы можем оперировать только им.

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

Ответ: 2

Задание 6 #14463

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

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

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

Закрасим нужный город красным.

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

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

Красным отметим только те дороги, которые так или иначе ведут в красный город. Не будем отмечать вовсе те дороги, которые никак не ведут в него. Напишем зелёным цветом над красным городом кол-во различных путей в него. Теперь мы можем оперировать только им.

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

Ответ: 6

Задание 7 #14462

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

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

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

Закрасим нужный город красным.

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

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

Красным отметим только те дороги, которые так или иначе ведут в красный город. Не будем отмечать вовсе те дороги, которые никак не ведут в него. Напишем зелёным цветом над красным городом кол-во различных путей в него. Теперь мы можем оперировать только им.

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

Ответ: 12