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

 

Решение.

Начнем считать количество путей с конца маршрута – с города Л. NX — количество различных путей из города А в город X, N — общее число путей.

 

В «Л» можно приехать из И, Е, Ж или К, поэтому N = NЛ = NИ + N Е + N Ж + N К (*)

 

Аналогично:

 

NИ = NД + N Е = 3 + 4 = 7;

NЕ = NД + NВ = 3 + 1 = 4;

NЖ = NВ + NГ = 1 + 2 = 3;

NК = NЖ = 3.

 

Добавим еще вершины:

 

NД = NБ + NВ = 2 + 1 = 3;

NБ = N А + NВ = 1 + 1 = 2;

NВ = NА = 1;

NГ = NА + NВ = 1 + 1 = 2.

 

Подставим в формулу (*):

 

N = NЛ = 7 + 4 + 3 + 3 = 17.

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

Сколько существует различных путей из города А в город М, проходящих через город Ж?

Решение.

Количество путей до города К равно количеству путей добраться в любой из тех городов, из которых есть дорога в K.

При этом если путь должен не проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город наоборот обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения найдём последовательно количество путей до каждого из городов:

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 4

Е = Б + В = 5

З = Д = 1

Ж = Е + В + Г + Д + З = 5 + 4 + 2 + 1 + 1 = 13

И = Ж = 13 (Е и З не учитываем, поскольку нужно обязательно проходить через Ж)

К = И = 13

Л = И = 13

М = К + Л + И = 39

 
Ответ: 39.

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

Решение.

Количество путей до города К равно количеству путей добраться в любой из тех городов, из которых есть дорога в Х.

При этом если путь должен не проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город наоборот обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения найдём последовательно количество путей до каждого из городов:

А = 1

Б = А = 1

Г = А + Б = 1 + 1 = 2 (т. к. проходить через город нужно Г обязательно)

Д = Г = 2

Ж = Г + Д = 4 (т. к. нельзя проходить через город З)

И = Д = 2

К = Ж + Д + И = 8

 
Ответ: 8.

4. На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н.

Сколько существует различных путей из пункта А в пункт Н, не проходящих через пункт В?

Решение.

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

 

При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

А = 1.

Б = А = 1.

Г = А = 1 (В не учитываем, поскольку путь не должен проходить через город В).

Д = Б = 1 (В не учитываем, поскольку путь не должен проходить через город В).

Е = Г + Д = 2 (В не учитываем, поскольку путь не должен проходить через город В).

Ж = Д = 1.

И = Г + Е = 3.

К = Д + Ж + И = 5.

Л = К + Ж = 6.

М = К = 5.

Н = К + Л + М = 16.

 
Примечание. Необходимо найти количество различных путей из города А в город Н, не проходящих через город В.
 
Ответ: 16.

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

Решение.

Начнем считать количество путей с конца маршрута — с города Л. Пусть NX — количество различных путей из города А в город X, N — общее число путей. В город Л можно приехать из И, Ж или К, поэтому N = NЛ = NИ + NЖ + N К (*)

 

Аналогично:

NИ = NД + NЕ = 3 + 7 = 10;

NЖ = NВ + NГ = 1 + 2 = 3;

NК = NЖ = 3.

 

Добавим еще вершины:

NД = NБ + NВ = 1 + 2 = 3;

NЕ = NД + NВ + NЖ = 3 + 1 + 3 = 7;

NБ = NА + NВ = 1 + 1 = 2;

NВ = NА = 1;

NГ = NА + NВ = 1 + 1 = 2.

 

Подставим в формулу (*): N = NЛ = 10 + 3 + 3 = 16.

 

Ответ: 16.

6. На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н.

Сколько существует различных путей из пункта А в пункт Н, не проходящих через пункт В?

Решение.

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

 

При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

А = 1.

Б = А = 1.

В = А + Б = 2.

Г = А = 1 (В не учитываем, поскольку путь не должен проходить через город В).

Д = Б = 1 (В не учитываем, поскольку путь не должен проходить через город В).

Е = Г + Д = 2 (В не учитываем, поскольку путь не должен проходить через город В).

Ж = Д = 1.

И = Г = 1.

К = Д + Ж + И + Е = 5.

Л = К = 5.

М = К + И = 6.

Н = К + Л + М = 16.

 
Примечание. Необходимо найти количество различных путей из города А в город Н, не проходящих через город В.
 
Ответ: 16.

7. На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П.

Сколько существует различных путей из пункта А в пункт П, проходящих через пункт И?

Решение.

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

 

При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

А = 1.

Б = А = В = 1.

Ж = Б = 1

Г = А + Б + В + Ж = 4

Д = Ж = 1

Е = Д + Г = 5.

И = Г + Е + В = 10.

К = И = 10.

Л = К = 10.

М = Н = Л = 10.

П = Л + Н + М = 30.

 
Примечание. Необходимо найти количество различных путей из города А в город П, проходящих через город И.
 
Ответ: 30.

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

Сколько существует различных путей из города А в город М, проходящих через город Ж, но не проходящих через город К?

Решение.

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

При этом если путь должен не проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город наоборот обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 1 + 1 + 2 = 4

Е = Б + В = 1 + 4 = 5

З = В + Г + Д = 4 + 2 + 1 = 7

Ж = В + Е + З = 4 + 5 + 7 = 16

И = Ж = 16

К = И = 16

Л = И = 16

 

Таким образом, путей, проходящих через город Ж, но не проходящих через город К: М = Л = 16.

 
Ответ: 16.

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

 

Решение.

Начнем считать количество путей с конца маршрута – с города К. NX — количество различных путей из города А в город X, N — общее число путей.

 

В «К» можно приехать из И, Ж, или Е, поэтому N = NК = NИ + NЖ + N Е (1)

 

Аналогично:

 

NИ = NД;

NЖ = NД + NВ + NЕ;

NЕ = NГ.

 

Добавим еще вершины:

 

NД = NБ + NВ;

NВ = NБ + NА + NГ + NЕ;

NГ = NА = 1;

 

NБ = NА = 1.

 

Преобразуем вершины:

 

NИ = NД = 5;

NЖ = NД + NВ + NЕ = 5 + 4 + 1 = 10;

NЕ = NГ = 1.

 

NД = NБ + NВ = 1 + 4 = 5;

NВ = NБ + NА + NГ + NЕ = 1 + 1 + 1 + 1 = 4;

NГ = NА = 1;

NБ = NА = 1.

 

Подставим в формулу (1):

 

N = NК = 5 + 10 + 1 = 16.

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

Сколько существует различных путей из города А в город Т, проходящих через город В?

 

Решение.

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

 

При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

А = 1.

Б = А = 1.

Г = А + Б = 2.

Д = А = 1.

В = Б + Г = 3.

Е = Г + Д = 3.

Ж = В = 3. (Е и Г не учитываем, поскольку в этих вершинах не проходим через В).

К = Ж = 3.

Н = Ж = 3.

М = Ж + Н = 6.

Л = К + Ж + М = 12.

П = К + Л + М = 21.

Р = П = 21.

С = П = 21.

Т = Р + С = 42.

 
Примечание. Необходимо найти количество различных путей из города А в город Т, проходящих через город В.
 
Ответ: 42.

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


 

Сколько существует различных путей из пункта А в пункт П, не проходящих через пункт Д?

Решение.

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

 

А = 1.

Б = А = 1.

В = А = 1.

Г = А + Б + В = 3.

Е = Г = 3.

И = Г + Е = 6.

Ж = 0 (Д не учитываем, поскольку путь не должен проходить через город Д).

К = И + Е = 9.

Л = Ж + Е + К = 0 + 3 + 9 = 12 (Д не учитываем, поскольку путь не должен проходить через город Д).

Н = Л = 12.

М = Л = 12.

П = Н + Л + М = 12 + 12 + 12 = 36.

 
Ответ: 36.

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

 

Решение.

Начнем считать количество путей с конца маршрута — с города Л. Пусть NX — количество различных путей из города А в город X, N — общее число путей. В город Л можно приехать из И, Д, Ж или K, поэтому N = NЛ = NИ + NД+NЖ + NК. (*)

 

Аналогично:

NИ = NД = 4;

NД = NБ + NВ = 1 + 3 = 4;

NЖ = NВ + NЕ = 3 + 1 = 4;

NК = NЕ = 1.

 

Добавим еще вершины:

NБ = NA = 1;

NВ = NБ + NА + NГ = 1 + 1 + 1 = 3;

NЕ = NГ = 1;

NГ = NA = 1.

 

Подставим в формулу (*): N = NM = 4 + 4 + 4 + 1 = 13.

 
Ответ: 13.

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

Сколько существует различных путей из города А в город М, проходящих через город Л, но не проходящих через город Е?

Решение.

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

При этом если путь должен не проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город наоборот обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 1 + 1 + 2 = 4

Е = Б + В = 1 + 4 = 5

З = В + Г + Д = 4 + 2 + 1 = 7

Ж = В + З = 4 + 7 = 11

И = Ж + З = 11 + 7 = 18

К = И = 18

Л = И = 18

М = Л = 18

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

Сколько существует различных путей из города А в город Т, проходящих через город М?

 

Решение.

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

 

При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

А = 1.

Б = А = 1.

Г = А + Б = 2.

Д = А = 1.

В = Б + Г = 3.

Е = Г + Д = 3.

Ж = В + Г + Е = 8.

К = Ж + В = 11.

Н = Д + Ж = 9.

М = Ж + Н = 17.

Л = М = 17. (Ж и К не учитываем, поскольку путь должен проходить через М)

П = Л + М = 34 (К не учитываем, поскольку путь должен проходить через М).

Р = П = 34.

С = П = 34.

Т = Р + С = 68.

 
Примечание. Необходимо найти количество различных путей из города А в город Т, проходящих через город М.
 
Ответ: 68.

15. На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н.

Сколько существует различных путей из пункта А в пункт Н, не проходящих через пункт В?

 

Решение.

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

 

При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

А = 1.

Б = А = 1.

Г = А = 1.

Д = Б = 1.

Е = Д = 1 (В не учитываем, поскольку путь не должен проходить через город В).

Ж = Д = 1.

И = Г + Е = 2.

К = Ж + Е + И + Д = 5.

Л = К = М = 5.

Н = Л + М + К = 15.

 
Примечание. Необходимо найти количество различных путей из города А в город Н, не проходящих через город В.
 
Ответ: 15.

16. На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город Т?

 

Решение.

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

 

А = 1

Б = А = 1

В = А + Б = 2

Д = А = 1

Г = А + Д = 2

Е = А + Б + В + Г + Д = 1 + 1 + 2 + 2 + 1 = 7

К = Б + Е = 7 + 1 = 8

Л = Е + К = 7 + 8 = 15

М = Л + К = 8 + 15 = 23

Н = К + М + Л = 8 + 23 + 15 = 46

П = Н = 46

Р = Н = 46

Т = П + Р = 46 + 46 = 92

 
Ответ: 92.

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

Сколько существует различных путей из города А в город М, проходящих через город В?

Решение.

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

При этом если путь должен не проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город наоборот обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 4

Е = В = 4

Ж = В + Е = 4 + 4 = 8

З = 0 (поскольку в З не ведёт ни одна дорога из В)

И = Е + Ж = 4 + 8 = 12

К = Л = И =12

М = К + И + Л = 36

 
Примечание. Необходимо найти количество различных путей из города А в город М, проходящих через город В.
 
Ответ: 36.

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

 

Решение.

Начнем считать количество путей с конца маршрута – с города Л. NX — количество различных путей из города А в город X, N — общее число путей.

 

В «Л» можно приехать из И, Д, Е, Ж или К, поэтому N = NЛ = NИ + N Д + N Е + N Ж + N К (*)

 

Аналогично:

 

NИ = NД = 7;

NД = NБ + NВ + N Е = 1 + 3 + 3 = 7;

NЕ = N В = 3;

NЖ = NЕ + NВ + N Г = 3 + 3 + 1 = 7;

NК = NЖ = 7.

 

Добавим еще вершины:

 

NБ = NА = 1;

NВ = NБ + NА + N Г = 1 + 1 + 1 = 3;

NГ = N А = 1.

 

Подставим в формулу (*):

 

N = NЛ = 7 + 7 + 3 + 7 + 7 = 31.

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

Сколько существует различных путей из города А в город М, проходящих через город Л?

 

Решение.

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

 

При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

А = 1.

Б = А = 1.

Д = А = 1.

Г = А + Д = 2.

В = Б + Г + А = 4.

Е = В + Б = 5.

З = Д = 1.

Ж = В + Г + Е + Д + З = 13.

И = Ж + Е + З = 19.

Л = И = 19.

К = И = 19.

М = Л = 19 (К и И не учитываем, поскольку путь должен проходить через Л).

 
Примечание. Необходимо найти количество различных путей из города А в город М, проходящих через город Л.
 
Ответ: 19.

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

 

Решение.

Начнем считать количество путей с конца маршрута — с города Л. Пусть NX — количество различных путей из города А в город X, N — общее число путей. В город Л можно приехать из И, Е или К, поэтому N = NЛ = NИ + NЕ + NК. (*)

 

Аналогично:

NИ = NВ + NЕ = 3 + 7 = 10;

NЕ = NВ + NГ + NЖ = 3 + 2 + 2 = 7;

NК = NЕ = 7;

NВ = NБ + NГ = 1 + 2 = 3;

NГ = NА + NБ = 1 + 1 = 2;

NД = NА = 1;

NЖ = NА + NД = 1 + 1 =2;

NБ = 1.

 

Подставим в формулу (*): N = NЛ = 10 + 7 + 7 = 24.

 
Ответ: 24.

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


 

Сколько существует различных путей из пункта А в пункт П, не проходящих через пункт Е?

Решение.

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

 

А = 1.

Б = А = 1.

В = А = 1.

Г = А + Б + В = 3.

Д = Г = 3.

И = Г = 3 (Е не учитываем, поскольку путь не должен проходить через город Е).

Ж = Д = 3.

К = И = 3 (Е не учитываем, поскольку путь не должен проходить через город Е).

Л = Д + Ж + К = 3 + 3 + 3 = 9 (Е не учитываем, поскольку путь не должен проходить через город Е).

Н = Л = 9.

М = Л = 9.

П = Н + Л + М = 9 + 9 + 9 = 27.

 
Ответ: 27.

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

Сколько существует различных путей из города А в город Т, проходящих через город Н?

Решение.

Количество путей до города Т равно сумме путей в каждый из тех городов, из которых есть дорога в T. С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов, кроме тех, которые не проходят через город Л:

А = 1

Б = А = 1

Д = А = 1

Г = А + Б = 1 + 1 = 2

В = Б + Г = 1 + 2 = 3

Е = Г + Д = 2 + 1 = 3

Ж = В + Г + Е = 3 + 2 + 3 = 8

Н = Ж = 8

М = Н = 8 (так как ищем пути проходящие через город Н)

Л = М = 8

П = Л + М = 16

Р = П = 16

С = П = 16

Т = 16 + 16 = 32

 
Ответ: 32.

23. На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н.

Сколько существует различных путей из пункта А в пункт Н, не проходящих через пункт Е?

 

Решение.

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

 

При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

А = 1.

Б = А = 1.

В = А + Б = 2.

Г = А + В = 3.

Д = Б + В = 3.

И = В + Г = 5 (Е не учитываем, поскольку путь не должен проходить через город Е).

Ж = Д = 3.

К = Ж + И + Д = 11.

Л = К = М = 11.

Н = Л + М + К = 33.

 
Примечание. Необходимо найти количество различных путей из города А в город Н, не проходящих через город Е.
 
Ответ: 33.

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

Решение.

Начнем считать количество путей с конца маршрута – с города И. NX — количество различных путей из города А в город X, N — общее число путей.

 

В «И» можно приехать из Д, Ж, или З, поэтому N = NИ = NД + NЖ + N З (1)

 

Аналогично:

 

NД = NБ;

NЖ = NБ + NВ + NЕ;

NЗ = NЖ + NЕ.

 

Добавим еще вершины:

 

NБ = NА = 1;

NВ = NА + NГ = 1 + 1 = 2;

NЕ = NВ + NГ = 2 + 1 = 3;

 

NГ = NА = 1.

 

Преобразуем первые вершины с учетом значений вторых:

 

NД = NБ = 1;

NЖ = NБ + NВ + NЕ = 1 + 2 + 3 = 6;

NЗ = NЖ + NЕ = 6 + 3 = 9.

Подставим в формулу (1):

 

N = NК = 1 + 6 + 9 = 16.

25. На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, К, Л, М.

Сколько существует различных путей, ведущих из города А в город М, проходящих через город В?

Решение.

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

 

При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

А = 1.

Б = А = 1.

Д = А = 1.

Г = А + Д = 2.

В = А + Б + Г = 4.

Е = В = 4 (Б не учитываем, поскольку путь должен проходить через город В).

З = В = 4. (Г и Д не учитываем, поскольку путь должен проходить через город В)

Ж = В + Е + З = 12.

И = Е + Ж + З = 20.

К = И = 20.

Л = И = 20.

М = К + И + Л = 60.

 
Примечание. Необходимо найти количество различных путей из города А в город М, проходящих через город В.
 
Ответ: 60.

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

Решение.

Посчитаем количество способов попасть в каждую вершину:

 

A = 1

Б = Д = А = 1

B = А + Б = 2

Г = А + Д = 2

Е = Б + В + Г + Д = 1 + 2 + 2 + 1 = 6

К = Е = 6

Л = Е + К = 6 + 6 = 12

М = Л + К = 12 + 6 = 18

Н = К + М + Л = 6 + 18 + 12 = 36

П = Н = Р = 36

Т = Н + П + Р = 36 + 36 + 36 = 108.

 
Ответ: 108.

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

Сколько существует различных путей из города А в город Н, проходящих через город Д?

 

Решение.

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

 

При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

А = 1.

Б = А = 1.

В = А + Б = 2.

Г = А + В = 3.

Д = В + Б = 3.

Е = Д = 3 (В и Г не учитываем, поскольку путь должен проходить через город Д).

Ж = Д + Е = 6.

И = Е = 3.

К = Ж + И = 9.

Л = К = М = 9.

Н = Л + М = 18.

 
Примечание. Необходимо найти количество различных путей из города А в город Н, проходящих через город Д.
 
Ответ: 18.

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

Сколько существует различных путей из города А в город М, проходящих через город Л?

Решение.

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

При этом если путь должен не проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город наоборот обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 4

Е = Б + В = 5

З = Д + Г + В = 7

Ж = В + Е + З = 4 + 5 + 7 = 16

И = Е + Ж + З = 5 + 16 + 7 = 28

Л = И = 28

К = И = 28

М = Л = 28 (путь в М через К не учитываем, т. к. надо пройти через Л)

 
Ответ: 28.

29. На рисунке изображена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город M?

Решение.

Начнем считать количество путей с конца маршрута – с города М. NX — количество различных путей из города А в город X, N — общее число путей.

 

В «М» можно приехать из G, H, F, K или L, поэтому N = NМ = NG + NH + NF + N К + N L (1)

 

Аналогично:

 

NG = NB;

NH = NB + NC + NF;

NF = NC + NА + ND;

NК = NF + ND;

NL = NE + ND.

 

Добавим еще вершины:

 

NB = NA + NC;

NC = NA = 1;

ND = NA= 1;

NE = NА + ND = 2.

 

Преобразуем вершины:

 

NB = NA + NC = 2;

NC = NA = 1;

ND = NA= 1;

NE = NА + ND = 2.

 

NG = NB = 2;

NH = NB + NC + NF= 2 + 1 + 3 = 6;

NF = NC + NА + ND = 1 + 1 + 1 = 3;

NК = NF + ND = 3 + 1 = 4;

NL = NE + ND = 2 + 1 = 3.

 

Подставим в формулу (1):

 

N = NМ = 2 + 6 + 3 + 4 + 3 = 18.

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

Сколько существует различных путей из города А в город Т, проходящих через город Б?

 

Решение.

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

 

При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

А = 1.

Б = А = 1.

Г = Б = 1.

В = Б + Г = 2.

Е = Г = 1.

Ж = В + Г + Е = 4.

К = Ж = 4.

Л = Ж + К= 8.

Н = Е + Ж = 5.

М = Л + Ж + Н = 17.

П = К + Л + М = 29.

Р = П + К = 33.

С = П = 29.

Т = Р + С + П = 91.

 
Примечание. Необходимо найти количество различных путей из города А в город Т, проходящих через город Б.
 
Ответ: 91.

Задание №15 ЕГЭ информатика. Поиск путей в графе.