Часть 1. Задание 9.
Вариант ОГЭ-2023. Демо.
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город В?
Задача на графы (ориентированные). Ориентированный граф – это такой граф, в котором указано направление перемещения. Перемещаться против стрелок запрещено.
Решение.
Для нахождения правильного ответа, необходимо несколько видоизменить предложенный граф, удалив из него ребра, которые не участвуют в создании пути, проходящего через узел В. Это ребра БД и АГ.
Красным цветом показан вес узла.
Следующий шаг: Определим «вес» каждого узла графа, под которым понимаем количество проходящих через этот узел дорог.
Начнем с узла А. С него начинается движение, следовательно ставим на ребрах АБ и АВ по 1 (смотри рисунок). Через узел Б проходит всего один путь (в принципе, узел Б в этой схеме перестал быть узлом). Через узел В проходит два пути: АВ и АБВ. Таким образом вес вершины В становится равным 2 (что означает, через узел В проходят две дороги).
Через вершину Д проходит 2 дороги (следовательно, вес вершины Д - 2). И так далее… В итоге мы получим следующий граф:
Главное, при определении веса каждого узла - не ошибиться!
Построение и перестройка графа позволяет наглядно решить задачи такого класса. По завершении работы над графом мы получаем ответ.
В нашем случае ответом будет число 10.
Задачи для самостоятельного решения
Задача 1. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город К?
Ответ
10
Задача 2. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Л, проходящих через город В?
Ответ
16
Задача 3. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через город Е?
Ответ
15
Задача 4. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через город Г?
Ответ
16