На рисунке показана схема дорог, связывающие города A, B, C, D, E, F, G, H, I. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город I, которые НЕ ПРОХОДЯТ через город D?

Пути обязательно не должны проходить через пункт D. Отсечем его от схемы:

Построим развёрнутый граф по данной схеме.

Шаг 1. Из пункта А пути ведут в пункты B и C:

Шаг 2. Из пункта B — один путь в E (путь в D не учитываем), из пункта C два пути — в E и в F:

Шаг 3. Из пункта E ведут три пути — в G, I, и F. Пункт Е на графе встречается два раза, но распишем его только один раз:

Примечание: конечные пункты в графе для удобства обведены, чтобы в конце можно было легко их посчитать.

Шаг 4. Как мы видим, из пункта Е в пункт I ведут четыре пути, из пункта F в пункт I — один путь. Мы можем не расписывать заново для оставшихся пунктов E и F, а просто подписать количество:

Шаг 5. Подсчитаем общее количество. 4+4+1=9

Ответ: 9