Задание 9

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

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

Ответ: ___________________________.

Решение:

Разобьём задачу на две. Найдём количество дорог из пункта А до пункта В и из пункта В до пункта К, затем их перемножим.

Из графа видно, что в пункт В из А можно попасть только двумя путями (напрямую и через пункт Б).

Для второй части (В — К) построим граф:

Из пункта В до пункта К существует 5 путей.

2 * 5 = 10

Ответ: 10