Задание 15

Теория.

Поиск путей в графе можно упростить, помня одно правило: если есть три города, А, B, С, и города A и C, а также В и С связаны, то количество дорог в город С равно сумме дорог в города А и В.

Пример задания.

Сколько существует дорог из А в М?

Чтобы проще было сосчитать дороги, будем считать сначала те из них, в которые ведет ровно 1 путь. Количество дорог в город будем называть весом вершины.

Так, например, в Б ведет один путь - из А, а вот в В два пути - из А и из Б.

Итак, в город В ведет одна дорога - А, поэтому вес вершины В=1. В Д также только один пути, поэтому вес Д=1:

Зная вес вершин А и Б, найдем вес В=1+1=2, теперь вершина Г: 1+1+2=4:

Вершина Ж:

1+4=5

Вершина Е:

1+2+5=8

Вершина З:

8+5=13

Вершины И :

13

Вершина К:

13+13=26

Вершина Л:

26+13=39

Вершина М:

13+26+39=78

Ответ 78.