Главная › Информатика › №9 · Пути в графе

ОГЭ информатика, задание 9: №9 · Пути в графе

Есть дороги между городами А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении: А→Б, А→В, Б→В, Б→Г, Б→Д, В→Г, В→Д, Г→Д, Д→Е, Д→Ж, Е→З, Ж→З, Ж→И, З→И, И→К.

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

Показать ответ и разбор
Ответ: 6

Идём по городам по порядку и в каждом записываем число путей = сумма чисел у городов, из которых в него ведут дороги. Через Е: (пути А→Е) × (пути Е→К). У города К получается 6.

Лайфхак. так считается быстрее и надёжнее, чем выписывать все пути.
Потренируйся в боте. Такие задания с разбором, статистика по темам и работа над ошибками: бесплатно в Telegram.
Решить это задание в боте @infkostbot

Ещё задания по теме