13. Графы
На рисунке представлена схема дорог города Клонов АР. Сколько существует дорог из пункта А в пункт J, не проходящих через пункт I?
Посчитаем сколькими путями можно придти в каждый пункт:
Отметим красными стрелками те пути, по которым мы не сможем пройти.
Ответ: 18
На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, I, J. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города A в город J, проходящих через город C?
Решать будем динамикой.
Закрасим нужный город красным.
Цветом отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все цветные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.
Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.
Красным отметим только те дороги, которые так или иначе ведут в красный город. Не будем отмечать вовсе те дороги, которые никак не ведут в него. Напишем зелёным цветом над красным городом кол-во различных путей в него. Теперь мы можем оперировать только им.
Итого получается, что в пункт J ведут 12 различных путей.
Ответ: 12
На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, H, K, I, J, G. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города A в город G, проходящих через город E?
Решать будем динамикой.
Закрасим нужный город красным.
Цветом отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все цветные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.
Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.
Красным отметим только те дороги, которые так или иначе ведут в красный город. Не будем отмечать вовсе те дороги, которые никак не ведут в него. Напишем зелёным цветом над красным городом кол-во различных путей в него. Теперь мы можем оперировать только им.
Итого получается, что в пункт G ведут 8 различных путей.
Ответ: 8
На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, X, J, Q, P, L, M, O, N. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города A в город N, проходящих через город K?
Решать будем динамикой.
Закрасим нужный город красным.
Цветом отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все цветные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.
Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.
Красным отметим только те дороги, которые так или иначе ведут в красный город. Не будем отмечать вовсе те дороги, которые никак не ведут в него. Напишем зелёным цветом над красным городом кол-во различных путей в него. Теперь мы можем оперировать только им.
Также заметим, что на графе присутствуют лишние дороги, не ведущие в город N, которые нам не нужны, и пути по которым считать не надо.
Итого получается, что в пункт N ведут 18 различных путей.
Ответ: 18
На рисунке представлена схема дорог, связывающих города A, B, D, E, C, H, G, F, I, J, K. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города A в город K, проходящих через город C?
Решать будем динамикой.
Закрасим нужный город красным.
Цветом отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все цветные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.
Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.
Красным отметим только те дороги, которые так или иначе ведут в красный город. Не будем отмечать вовсе те дороги, которые никак не ведут в него. Напишем зелёное число около этого города. Теперь мы можем оперировать только им.
Итого получается, что в пункт K ведут 18 различных путей.
Ответ: 18
На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города A в город H, проходящих через город E?
Решать будем динамикой.
Закрасим нужный город красным.
Цветом отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все цветные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.
Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.
Красным отметим только те дороги, которые так или иначе ведут в красный город. Не будем отмечать вовсе те дороги, которые никак не ведут в него. Напишем зелёным цветом над красным городом кол-во различных путей в него. Теперь мы можем оперировать только им.
Итого получается, что в пункт H ведут 15 различных путей.
Ответ: 15
На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, I, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города A в город H, проходящих через город I?
Решать будем динамикой.
Закрасим нужный город красным.
Цветом отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все цветные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.
Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.
Красным отметим только те дороги, которые так или иначе ведут в красный город. Не будем отмечать вовсе те дороги, которые никак не ведут в него. Напишем зелёным цветом над красным городом кол-во различных путей в него. Теперь мы можем оперировать только им.
Итого получается, что в пункт H ведёт 2 различных пути.
Ответ: 2
