На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город О, проходящих через город В?
Заметим, что количество путей из города А в город О, проходящих через город В равно произведению количества путей из города А в город В на количество путей из города В в город О. Разобъём заданный граф на два: один из которых будет содержать только города и соответствующие дороги, ведущие из А в В, а другой — только города и соответствующие дороги из В в О.
Построим таблицу, соответствующую каждой из полученных схем. В первую строку таблицы запишем наименование всех вершин в следующем порядке.
Для первой схемы сначала запишем вершину В. Затем те вершины, из которых в В ведёт прямой путь и из которых в вершину В можно попасть только через уже просмотренные вершины. Получим:
| В | Б | Г | А |
Вторую строку таблицы заполним числами, соответствующими количеству исходящих путей Px (B) из просматриваемой вершины x в B. Если из вершины x выходит несколько путей, например, в вершины x1, x2, и x3, то количество путей, ведущих из этой вершины в К, будет равно сумме путей, ведущих из x1, x2, и x3 в К.
То есть Px (B) = Px1 (B) + Px2 (B) + Px3 (B). Получим:
| В | Б | Г | А |
| 1 | 1 | 1 | 3 |
Количество путей из А в В равно 3.
Для определения количества путей из города В в О аналогично построим таблицу, соответствующую второй схеме.
| О | Н | М | З | И | Л | К | Д | Ж | Е | В |
| 1 | 1 | 1 | 3 | 3 | 3 | 6 | 9 | 9 | 18 | 36 |
Количество путей из В в О равно 36.
Следовательно, количество путей из города А в город О, проходящих через город В, равно 3 · 36 = 108.
Ответ: 108