ОГЭ №9

 

Добрый день, сегодня попробуем разобраться с заданием №9 ОГЭ по информатике. Для этого нужно знать базовую информацию по теме “графы”. Граф — структура данных, благодаря которой видно взаимосвязи между объектами (в данном случае между населёнными пунктами). В данной задаче используется ориентированный граф.

Ориентированный граф — это такой граф, который имеет лишь одно направление движения (по стрелке), идти в обратном направлении нельзя.

Попробуем разобрать несколько задач с разным условием

Существует несколько видов решения. Первый вариант решения - переписать все возможные пути из города А в город П, которые обязательно проходят через город Е. И потом посчитать количество данных путей. Данный способ занимает большое количество времени, долго расписывать и имеет большой шанс ошибиться. Второй вариант решения - подписывать сумму (веса) предыдущих путей. Этим способом и будем решать данный тип задания.

Задача №1

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

 

Схема дорог (граф)

Решение

Для начала отметим через какой населённый пункт нужно ОБЯЗАТЕЛЬНО пройти и через какие населённый пункты нам идти не нужно (т.к. они не проходят через нужный населённый пункт)

 

Отметили обязательное прохождение через город Е

Далее будем наносить веса для каждого населенного пункта.

 

Подписали веса

Вес с входящих городов складывается (в город Е).

 

Продолжаем подписывать веса

Вес с городов сохраняется, даже если в дальнейшем он расходится по другим населённым пунктам (из города Ж в К,Н). Далее поочерёдно суммируем веса. Сначала в город “М”, а потом в город “Л”.

 

Продолжаем подписывать веса

После этого останется лишь просуммировать веса для города “П” и получить ответ.

 

Суммируем окончательный ответ

Достаточно быстро получили правильный ответ — 21 (количество путей из города А в город П через населённый пункт Е). Если выписывали все возможные пути, то это заняло бы больше времени и, возможно, допустили ошибку.

Задача №2

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

 

Схема дорог (граф)

Решение

Для начала опять же отметим, через какие города мы не должны проходить и зачеркнём их. Поскольку нам НЕЛЬЗЯ проходить через город “В”, то зачеркнём все пути ведущие из него (можно ещё и зачеркнуть, которые ведут в него).

 

Отмечаем через какие дороги НЕЛЬЗЯ проходить

Далее немного пропишем веса у населённых пунктов.

 

Подписываем веса

Осталось просуммировать окончательный вес в городе “К” и записать ответ.

 

Суммируем окончательный ответ

Достаточно просто и легко получили наш ответ — 5