В 13-ом задании Вам необходимо подсчитать количество путей, ведущих из одной вершины в другую. Для этого Вам достаточно освоить один простой способ, описанный ниже.
Пример задания
Рассмотрим задание из демоверсии ЕГЭ 2023:
Что нам напоминает это задание? Правильно: рассмотренное ранее первое задание ЕГЭ по информатике. Здесь тоже имеется граф-схема, изображающая города буквами, а дороги - линиями. Единственное нововведение в схеме в том, что теперь мы можем перемещаться по дороге только в одном направлении, указанном стрелкой.
Способ подсчёта дорог
Для иллюстрации способа возьмём пример попроще. Пусть нужно найти количество дорог от пункта "А" до пункта "М" на схеме ниже:
Способ подсчёта дорог достаточно прост. Для начала нужно поставить единицу возле города, от которого мы начинаем движение. Далее по очереди рассматриваются города: если мы знаем числа всех городов, входящих в рассматриваемый пункт, то мы просто суммируем эти числа и результат записываем у рассматриваемого города. Если же числа ещё известны не у всех пунктов, входящих в рассматриваемый город,то мы откладываем этот город на потом.
Начинаем считать дороги. По условию задачи мы должны начать с города "А" - запишем возле этого города единицу. Далее мы рассматриваем соседей города "А". Для того, чтобы вычислить новое число дорог, нам потребуется знать числа дорог городов, входящих в рассматриваемый. Таким образом, сначала вычисляем количество дорог для "Б" и "Д", потом для "Г", после для "В" и т.д.
Проиллюстрируем алгоритм:
Обязательные и избегаемые города
Но что делать, если подсчитываемые пути обязаны проходить через какой-либо город? Тогда до начала подсчёта путей мы должны исключить часть дорог.
Пусть все наши пути из "А" в "М" должны проходить через город "Ж". Если рассмотреть схему, можно увидеть, что дороги "Е-И" и "З-И" нужно исключить, ведь они позволяют избежать город "Ж". После исключения дорог можно уже применить рассмотренный выше способ и подсчитать оставшиеся дороги.
Аналогичная ситуация и с теми городами, в которых мы не должны побывать - исключаем из схемы все входящие и исходящие дороги избегаемого города. После исключения просто считаем оставшиеся пути. Пусть по условиям задания мы ещё не должны попадать в "Е". Тогда:
Заключение
Тринадцатое задание основано на последовательном подсчёте путей от начальной точки до последующих. Аналогичное задание есть в ОГЭ по информатике - тем, кто сдавал ОГЭ, будет немножко проще :)
