ЕГЭ-2015 задание 15.

Поиск количества путей в графе

Теория

Если в город S можно приехать только из городов X, Y, и Z, то число различных путей из города A в город S равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть

NS = NX + NY + NZ ,

где NM обозначает число путей из вершины A в некоторую вершину M

Число путей конечно, если в графе нет циклов - замкнутых путей

Задача

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

Поиск путей в графе

Решение

Будем обозначать через NX количество различных путей из города А в город X. Для города А есть только один маршрут – никуда не двигаться, поэтому NA = 1. Для любого города X количество маршрутов NX можно вычислить как

NX = NY + … + NZ

где сумма взята по всем вершинам, из которых есть прямой путь в вершину X; например, 

NЛ = NД + NИ + NЖ + NК

Составим таблицу, в которой около каждого города будем записывать количество прямых путей в этот город. Начнем считать количество путей с начала маршрута – с города А: 

В пункты Б и В ведут единственные дороги из А. В пункт В можно попасть из пунктов А, Б, и Г, т.е. NВ = NА + NБ + NГ = 3.

А Б В Г Д Е Ж И К Л
1 1 3 1            

В пункт Е можно попасть только из Г, количество путей равно количеству путей в пункт Г. В пункт Ж ведут прямые пути из пунктов Е и В, т.е. NЖ = NВ + NЕ = 4. В пункт Д ведут прямые пути из пунктов Б и В, т.е. NД = NВ + NБ = 4.

А Б В Г Д Е Ж И К Л
1 1 3 1 4 1 4      

В пункт И можно попасть только из Д, количество путей равно количеству путей в пункт Д = 4. В пункт К ведет путь только из пункта Е, т.е. NК = NЕ = 1. В пункт Л ведут прямые пути из пунктов Д, И, Ж и К, т.е. NЛ = NД + NИ + NЖ + NК = 13.

А Б В Г Д Е Ж И К Л
1 1 3 1 4 1 4 4 1 13

Ответ

13

Яндекс.Метрика