Автор — Лада Борисовна Есакова.
Подсчет путей в ориентированном графе. ЗАДАЧА № 15.
В этой задаче требуется подсчитать количество путей, ведущих из одной вершины графа в другую. Обычно задачу решают преобразованием графа в дерево. Однако, при сложной структуре графа такое решение становится очень трудоемким. Велика вероятность ошибки.
Рассмотрим простой и эффективный способ решения.
В этой задаче мы имеем дело с ориентированным графом (графом, у которого ребра имеют направление). Т.е. ребра имеют вид стрелок. Две вершины, соединенные напрямую стрелкой, называются смежными. Вершина, из которой выходит стрелка, называется предком, а вершина, в которую входит стрелка – потомком.
Несложно понять, что количество путей, которыми можно попасть в некоторую вершину, равно сумме количеств путей предков этой вершины.
Пример:
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
Решение:
Каждой вершине, начиная с начальной (A), поставим в соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A (начало пути) индекс всегда равен 1 (в начало пути можно попасть единственным образом – никуда не двигаясь). Теперь сформулируем правило: индекс вершины равен сумме индексов его предков. Исходя из этого индекс Б равен 1 (предок у Б один – вершина A).
У вершины Д предками являются А и Б, значит индекс вершины Д равен 1+1=2.
Очевидно, что мы можем посчитать индекс только тех вершин, индексы предков которых уже посчитаны. Например, мы не можем посчитать индекс Г, пока не посчитан индекс В. Двигаясь последовательно, мы рассчитаем индексы всех вершин.
Индекс вершины Ж и будет ответом задачи.
Ответ: 11
Спасибо за то, что пользуйтесь нашими публикациями.
Информация на странице «Задача №15. Графы. Поиск количества путей.» подготовлена нашими авторами специально, чтобы помочь вам в освоении предмета и подготовке к ЕГЭ и ОГЭ.
Чтобы успешно сдать нужные и поступить в высшее учебное заведение или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий.
Также вы можете воспользоваться другими материалами из разделов нашего сайта.
Публикация обновлена:
07.05.2023
На уроке рассмотрен материал для подготовки к ОГЭ по информатике, рассмотрены примеры того, как решать 9 задание. Дан теоретический материал по теме «Анализирование информации, представленной в виде схем и поиск количества путей».
Содержание:
- ОГЭ по информатике 9 задания объяснение
- Поиск количества путей
- 9 задание как решать
- Актуальное
- Тренировочные
9-е задание: «Анализирование информации, представленной в виде схем».
Уровень сложности — повышенный,
Максимальный балл — 1,
Примерное время выполнения — 4 минуты.
* до 2020 г — это было задание № 11 ОГЭ
Поиск количества путей
- Если в город R из города A можно добраться только из городов X, Y и Z, то количество различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть:
- где NR — это количество путей из вершины A в вершину R
- Число путей не бесконечно, исключением является только схема, в которой есть циклы – замкнутые пути.
- Часто подобные задания целесообразней решать с конца (рассмотрим пример ниже).
NR = NX + NY + NZ
9 задание как решать
-
Подробный видеоразбор по ОГЭ 9 задания:
- Рассмотрено 3 задачи. Перемотайте видеоурок на решение нужной задачи.
Актуальное
Решение задания 9.3. Демонстрационный вариант огэ по информатике 2022 г.:
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город К, проходящих через город В?
✍ Решение:
-
✎ 1 способ (дерево):
- Поскольку нас интересуют пути, проходящие через город В, то вычеркнет те дороги, которые минуют город В:
- Как видим, таких дорог получилось две — Б->Д и А->Г. Учтем это при дальнейших расчетах.
- Решим задание с конца. Т.е. так как траектория поиска путей — от А до K, то мы будем рассматривать сначала город K.
- В город K можно попасть из трех городов — Д, E и Ж; запишем это так:
K = Д + Е + Ж
Д = В (Б -> Д не учитываем) Е = Д + В Ж = В + Г
К = Д + Е + Ж Д = В Е = Д + В Ж = В + Г ----- Б = А = 1 A = 1 В = Б + А Д = B Ж = B + Г Г = В (А - Г не учитываем) Теперь возвращаемся, подставляя найденные значения: ↑ В = Б + А = 2 Г = В = 2 Д = В = 2 Ж = B + Г = 2 + 2 = 4 Е = Д + В = 2 + 2 = 4
К = Д + Е + Ж = 2 + 4 + 4 = 10
✎ 2 способ (дерево):
К Д - Е - К -------------- Е - К Д - К Б - В - Е - К Ж - К Г - Ж - К А ---------------- Д - К Е - К В - Е - К Ж - К Г - Ж - К ---------------- Г - Ж - К
К Д - Е - К -------------- Е - К Д - К Б - В - Е - К Ж - К Г - Ж - К А ---------------- Д - К Е - К В - Е - К Ж - К Г - Ж - К ---------------- Г - Ж - К
Ответ: 10
Решение задания 9.4:
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город К, проходящих через город Ж?
✍ Решение:
-
✎ 1 способ (с конца):
- Поскольку нас интересуют пути, проходящие через город Ж, то вычеркнем те дороги, которые минуют город Ж:
- Решим задание с конца. Т.е. так как траектория поиска путей — от А до K, то мы будем рассматривать сначала город K.
- В город K можно попасть из трех городов — И, E и Ж; запишем это так:
K = И + Ж
И = Ж Ж = Д + В + Е
К = И + Ж И = Ж Ж = Д + В + Е ----- Д = Б + В Е = В + Г В = Б + А + Г А = 1 Г = А = 1 Б = А = 1 Теперь возвращаемся, подставляя найденные значения: ↑ В = Б + А + Г = 1 + 1 + 1 = 3 Д = Б + В = 1 + 3 = 4 Е = В + Г = 3 + 1 = 4 Ж = Д + В + Е = 4 + 3 + 4 = 11 И = Ж = 11 К = И + Ж = 22
Ответ: 22
Тренировочные
Решение задания 9.1:
На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город H?
Типовые задания для тренировки
✍ Решение:
- Решим задание с конца. Т.е. так как траектория поиска путей от А до Н, то мы будем рассматривать сначала город Н.
- В город Н можно попасть из трех городов — C, D и G; запишем это так:
H = C + D + G
C = D + A D = A + E G = D + E + F
Далее, рассмотрим каждый город, дойдя до первого — города А. Для него существует только одни путь. Также, для городов, выходящих только из города А, тоже существует только 1 путь. Таким образом имеем:
H = C + D + G C = D + A D = A + E G = D + E + F ----- D = Е + A A = 1 E = A + B F = B B = 1 Теперь возвращаемся, подставляя найденные значения: ↑ F = B = 1 E = A + B = 1 + 1 = 2 D = Е + A = 2 + 1 = 3 G = D + E + F = 3 + 2 + 1 = 6 D = A + E = 1 + 2 = 3 C = D + A = 3 + 1 = 4 H = C + D + G = 4 + 3 + 6 = 13
Ответ: 13
Решение задания 9.2:
На карту нанесены 4 города (A, B, C и D).
Известно, что:
между городами A и C — три дороги,
между городами C и B — две дороги,
между городами A и B — две дороги,
между городами C и D — две дороги,
между городами B и D — четыре дороги.
По каждой из этих дорог можно ехать в обе стороны.
Сколькими различными способами можно проехать из A в D, посещая каждый город не более одного раза?
Типовые задания для тренировки
✍ Решение:
- Построим все возможные ветви для движения из города A. Будем выполнять произведение количества дорог для каждой ветви, так как движение возможно в обе стороны:
A * B * C * D = 2 * 2 * 2 = 8 (A и B - две дороги, C и B - две дороги, C и D - две дороги) A * B * D = 2 * 4 = 8 (A и B - две дороги, B и D - четыре дороги) A * C * D = 3 * 2 = 6 (A и C - три дороги, C и D - две дороги) A * C * B * D = 3 * 2 * 4 = 24 (A и C - три дороги, C и B - две дороги, B и D - четыре дороги)
8 + 8 + 6 + 24 = 46
Ответ: 46
Пройти тестирование по этим заданиям
Вернуться к каталогу заданий
Версия для печати и копирования в MS Word
1
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город В?
2
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З и И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И, проходящих через город В?
3
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И, проходящих через город В?
4
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И, проходящих через город Ж?
5
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И, проходящих через город Ж?
Пройти тестирование по этим заданиям
Характеристика задания
1. Тип ответа: числовой.
2. Структура содержания задания: дана текстовая задача и схема к ней, нужно определить количество путей из начальной точки до конечной по схеме.
3. Уровень сложности: повышенный.
4. Примерное время выполнения: (3) минуты.
5. Количество баллов: (1).
6. Требуется специальное программное обеспечение: нет.
7. Задание проверяет умение представлять и считывать данные в разных типах информационных моделей.
Основной способ решения задания разобран в предыдущей теории. С (2022) года появилось задание, которое вызвало затруднение на экзамене, хотя способ решения остался тот же: нужно подсчитать количество путей, но ограничения другие. Разберём это задание.
ЕГЭ-(2022). На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определи количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе Е, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза.
Рис. (1). Схема к заданию (2022)
Решение: из точки Е ведут только три дороги: в сторону В, И и К.
Рис. (2). Варианты движения
Рассмотрим их в отдельности.
Направление ЕВ.
Рис. (3). Количества маршрутов в направлении ЕВ
В (=) Е (= 1),
А (=) В (=1),
Г (=) А (+) В (=2),
Б (=) А (=1),
Д (=) Б (+) В (=2+1=3),
З (=) Д (=3),
К (=) Д (+) З (=3+3=6),
И (=) К (=6),
Ж (=) Г (+) И (+) В (=2+6+1=9),
Е (=) Ж (+) Д (=12).
Итого (12) маршрутов.
Теперь рассмотрим направление ЕК.
Рис. (4). Количества маршрутов в направлении ЕК
Е (=1),
К (=) Е (=1),
И (=) К (=1),
Ж (=) И (=1),
Е (=) Ж (=1).
Всего (1) маршрут.
Также в направлении ЕИ — тоже (1) маршрут.
Складываем (12+1+1=14).
Ответ: (14).
В Демоверсии (2023) года вариант аналогичный.
Рассмотрим ещё один тип заданий.
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого длинного пути из города А в город М?
Длиной пути считать количество дорог, составляющих этот путь.
Рис. (5). Схема к заданию
Можно сказать, что вес каждого ребра равен единице, и поэтому, проходя по ребру, мы добавляем к предыдущему значению (1).
Начало отсчёта — в точке А, окончание пути — в точке М.
Просчитаем маршруты от точки А до Ж.
Помним, что маршрут должен быть максимальный, поэтому рассмотрим варианты:
в вершину В можно прийти:
А—В (=1),
А—Б—В (=2),
А—Г—В (=2),
А—Д—Г—В (=3).
Выберем А—Д—Г—В.
В вершину Е:
А—Д—Г—В—Е (=4), с учётом предыдущего выбора, все остальные пути короче.
Поэтому в вершину Ж будет путь А—Д—Г—В—Е—Ж(=5), самый длинный.
И (=5)(Ж) (+) (1=6),
К (=6)(И) (+) (1=7),
М (=7)(К) (+) (1=8).
Ответ: (8).
Источники:
Рис. 1. Схема к заданию 2022. © ЯКласс.
Рис. 2. Варианты движения. © ЯКласс.
Рис. 3. Количества маршрутов в направлении ЕВ. © ЯКласс.
Рис. 4. Количества маршрутов в направлении ЕК. © ЯКласс.
Рис. 5. Схема к заданию. © ЯКласс.
1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения
Поиск количества путей в ориентированном графе
На рисунке представлена схема дорог, связывающих города 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
На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, J, I. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города A в город I?
Решать будем динамикой.
Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.
Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.
Итого получается, что в пункт I ведут 27 различных путей.
Ответ: 27
На рисунке представлена схема дорог, связывающих города A, B, C, D, E, G, F. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города A в город F?
Решать будем динамикой.
Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.
Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.
Итого получается, что в пункт F ведут 11 различных путей.
Ответ: 11
На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, I. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города A в город I?
Решать будем динамикой.
Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.
Итого получается, что в пункт I ведут 17 различных путей.
Ответ: 17
На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, I, J. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города A в город J?
Решать будем динамикой.
Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.
Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.
Итого получается, что в пункт J ведут 8 различных путей.
Ответ: 8
На рисунке представлена схема дорог, связывающих города 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
На рисунке представлена схема дорог, связывающих города 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
УСТАЛ? Просто отдохни