На рисунке изображена схема дорог между пунктами А, Б, В, Г, Д, Е, Ж, З, И, К. Сколько существует путей из пункта А в пункт К, если необходимо посетить пункт Г?

Алгоритм решения задачи о подсчете путей с обязательным посещением узла

1. Дано

• Граф: Схема дорог между пунктами (вершинами) А, Б, В, Г, Д, Е, Ж, З, И, К.
• Начальный пункт: А.
• Конечный пункт: К.
• Обязательный пункт: Г.

2. Найти

• Общее количество путей из А в К, проходящих через Г.

3. Решение

Задача сводится к нахождению произведения числа путей из начальной точки в обязательную и числа путей из обязательной точки в конечную.

Пусть $N(X \rightarrow Y)$ — это количество различных путей из пункта $X$ в пункт $Y$.

Поскольку путь должен идти из...