На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М?
Источник: демоверсия ФИПИ по информатике и ИКТ 2016-го года.
В решении задания есть видеоразбор
Решение:
Обратите внимание, для того, чтобы попасть из А в М, нужно обязательно пройти через пункт И, из которого два пути в М. То есть мы можем найти количество путей из А в И, а потом просто их умножить на 2.
Для решения построим граф.
Шаг 1. Из пункта А пути ведут в пункты Б, В, Г, Д:
Шаг 2. Из пункта Б пути ведут в пункты В и Е:
Шаг 3. Из пункта В пути ведут в Е, Ж, З:
Шаг 4. По схеме видно, что из пункта Е в И ведут два пути (напрямую в И и через Ж в И), из пункта Ж — один путь, из пункта З — два пути. Отметим это на графе:
Шаг 5. По нашему графу видно, что из пункта В в И ведут пять путей, отобразим это на графе:
Шаг 6. Из пункта Г пути ведут в В и З, из В, как мы знаем, пять путей, из З — два пути. Отобразим на графе:
Шаг 7. Из пункта Д пути ведут в Г и З. Из Г, как мы теперь знаем, существует семь путей, из З — два пути:
Остаётся сосчитать. 2+1+2+2+5+5+2+7+2 = 28.
Но мы нашли пути из А в И. В пункт M путей в два раза больше:
