ОГЭ Задание 9

Типы заданий № 9

В этой статье будет разобрано задание 9.

Рассмотрим типовые задачи из девятого задания ОГЭ по информатике.

Данное задание относится к повышенному уровню сложности.

Время выполнения задания ≈ 4 минуты.

Прежде чем решать задачи, полезно знать теорию(ссылка на статью ниже):

Ссылка на статью: Теория графов.

Задача 1 (Классическая)

Дана схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л, М. По каждой дороге можно двигаться только в направлении, указанном стрелкой. Сколько возможно различных путей из города А в город М?

Решение:

1. Возле города А записываем единицу. Это — некое "стартовое" значение, поскольку уж один-то путь из А в М есть всегда.
2. Смотрим город Б. В этот узел графа входит только одна стрелка, которая идёт от узла А со значением 1. Поэтому возле узла Б тоже записываем единицу.
3. То же с городами (узлами) В и Г — в них по единственной входящей стрелке "переносится" всё та же единица из узла А.

4. Смотрим город Д. В него входят уже две стрелки. Одна идёт из узла Б и "несёт с собой" оттуда единицу. Вторая же аналогичным способом переносит единицу по стрелке из узла В. Итого в узле Д в сумме получается значение 1+1=2.
5. То же самое получается и для узла Е, куда по соответствующим двум стрелкам "приходят" единицы из узлов В и Г.

6. В узел Ж тоже входят две стрелки. Одна (из узла Б) "приносит" туда единицу. А вторая (из узла Д) "приносит" уже двойку. Итого в сумме получаем: 1+2=3.
7. Для узла К история та же — рядом с ним тоже записываем 3 (1 по стрелке из узла Г плюс 2 по стрелке из узла Е).
8. Для узла же И две стрелки "принесут" с собой из узлов Б и Г по единице каждая, итого в сумме получаем 2.

9. Теперь находим сколько путей будет у узла Л. В него входят три стрелки. Первая, из узла Ж, "переносит" в Л тройку. Вторая, из узла К, "переносит" тоже тройку. И, наконец, третья, из узла И, "переносит" в Л двойку. В сумме для Л получаем: 3+2+3=8.

10. Остаётся узел М. В него приходят тоже три стрелки. Стрелка из узла Ж "приносит" в М тройку. Стрелка из узла К "приносит" в М тоже тройку. Стрелка из узла Л приносит в М восьмёрку. В сумме для М получается: 3+3+8=14.

Ответ: 14

Задача 2 (Через пункт)

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

Решение:

1. Сначала из исходной схемы убираем все пути, которые не проходят через L:

В результате получаем схему:

2. Теперь выполняем классическое решение по поиску путей (см. решение предыдущей задачи):

Ответ: 30

Задача 3 (Через пункты)

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

Решение:

1. Преобразуем граф в соответствии с заданными условиями: "пути, ведущие из города A в город M и проходящих через пункт D или через пункт F, но не через оба этих пункта". Поскольку здесь используется логическое условие: ("через пункт D" ИЛИ "через пункт F") И НЕ("через оба этих пункта"), потребуется, по сути, решать задачу трижды для трёх соответствующих этим элементарным условиям модификаций исходного графа. Через пункт D:

Количество возможных путей вычисляется как обычно. Всего — 75 путей.

2. Через пункт F:

Всего — 70 путей.

3. Через оба пункта D и F:

Всего — 60 путей.

4. Чтобы подсчитать количество путей, соответствующее полному условию: ("через пункт D" ИЛИ "через пункт F") И НЕ("через оба этих пункта"), нужно сложить значение, полученные в пунктах (1) и (2) и вычесть из этой суммы удвоенное значение, полученное в пункте 3:

Удвоенное — поэтому что количество путей через D и F было один раз подсчитано в составе всех путей через D, а затем ещё один раз подсчитано в составе всех путей через F, а нам нужно исключить из рассмотрения оба этих подсчёта. 75 + 70 - 2 ⋅ 60 = 25.

Ответ: 25

Задача 4 (Не проходимый пункт)

На рисунке – схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П. Сколько существует различных путей из пункта А в пункт П, не проходящих через пункт Е?

Решение:

1. Зачеркнём те дороги, которые поведут наши пути через пункт E:

2. Далее, применим классический метод по поиску путей, который использовали сразу же в первой задаче:

Ответ: 27

Задача 5 (Наибольшая длина пути)

На рисунке - схема дорог, связывающих города А, Б, В, Г, Е, Ж, К, Л, М. По каждой дороге можно двигаться в одном направлении, указанном стрелкой. Какая наибольшая длина пути из А в М?

Решение:

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

Число, которое получится возле конечной точки и будет ответом. В этой задачке получилось 7.

Ответ: 7

Задача 6 (Демоверсия ОГЭ 2025)

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

Решение:

При решении задачи применяем классическую технику по поиску путей из задачи 1.

Ответ: 10