Количество путей. Задание №13

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

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

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

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

Задача №5
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д…М.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М и проходящих через участок дороги, который связывает город Д и И напрямую?

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

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

Проходят
через Г, но
не проходят
через К

Проходят
через К, но
не проходят
через Г

Ответ: 24 (15 +9)
Через Г- 15
Через К- 9

Длина самого длинного пути.

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

Решение.
Решаем почти так же, как и в задачах на вычисление количества путей, но при определении индекса очередной вершины X
вместо суммы индексов предыдущих вершин (как это было в задачах на количество путей)
берём наибольшее из значений индексов предыдущих вершин + 1
Вершина А – 0 ( нет предыдущих вершин)
Вершина Б – 1 – предыдущая вершина А
→ max(0) + 1 = 1
Вершина Г – 1 – предыдущая вершина А
→ max(0) + 1 = 1
Вершина В – предыдущие вершины А, Б, Г, т.е. max (0,1,2) + 1 =3
Вершина Д – предыдущие вершины А и Г, т.е. max (0,1) + 1 =2

Вершины Е и К сможем
рассмотреть только
после вершин И и З
Вершина З – предыдущие вершины Г и Д, т.е. max (1,2) + 1 = 3
Вершина И– предыдущие вершины Д и З, т.е. max (1,3) + 1 = 4

Вершина К – предыдущие вершины З и И, т.е. max (3, 4) + 1 = 5
Вершина Е – предыдущие вершины Б и К, т.е. max (1, 5) + 1 = 6