Часть 1. Задание 9.

Вариант ОГЭ-2023. Демо. 

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К.

По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город В?

Решение.

Для нахождения правильного ответа, необходимо несколько видоизменить предложенный граф, удалив из него ребра, которые не участвуют в создании пути, проходящего через узел В. Это ребра БД и АГ.

Следующий шаг: Определим «вес» каждого узла графа, под которым понимаем количество проходящих через этот узел дорог.

Начнем с узла А. С него начинается движение, следовательно ставим на ребрах АБ и АВ по 1 (смотри рисунок). Через узел Б проходит всего один путь (в принципе, узел Б в этой схеме перестал быть узлом). Через узел В проходит два пути: АВ и АБВ. Таким образом вес вершины В становится равным 2 (что означает, через узел В проходят две дороги).

Через вершину Д  проходит 2 дороги (следовательно, вес вершины Д - 2). И так далее… В итоге мы получим следующий граф:

Построение и перестройка графа позволяет наглядно решить задачи такого класса. По завершении работы над графом мы получаем ответ.
В нашем случае ответом будет число 10.

Задачи для самостоятельного решения

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

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

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

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