1 of 7

Задание №9

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

Никифоров Николай Сергеевич�МБОУ СОШ №26 г. Сургут

http://online.fizinfo.ru

online.fizinfo@mail.ru

2 of 7

№1 (Демоверсия ФИПИ – 2020)

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

Ответ: 10

Решение:

1

  1. A = 1
  2. Б = А = 1
  3. В = А + Б = 1 + 1 = 2
  4. Г = В = 2
  5. Д = В = 2
  6. Е = В + Д = 2 + 2 = 4
  7. Ж = В + Г = 2 + 2 = 4
  8. К = Д + Е + Ж = 2 + 4 + 4 = 10

1

2

2

2

4

4

10

1

3 of 7

№2 (СтатГрад – октябрь 2019)

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

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

Решение:

1

  1. A = 1
  2. Б = А = 1
  3. В = А + Б = 1 + 1 = 2
  4. Д = А = 1
  5. Г = А + В + Д = 1 + 2 + 1 = 4
  6. Е = Б = 1
  7. Ж = Г + Д = 4 + 1 = 5
  8. И = 0
  9. К = 0
  10. З = Е + В + Г + Ж = 1 + 2 + 4 + 5 = 12
  11. Л = З = 12

Ответ: 12

1

5

4

2

0

1

12

1

0

12

1

4 of 7

№3 (СтатГрад – октябрь 2019)

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

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

Ответ: 14

  1. A = 1
  2. Б = А = 1
  3. В = А + Б = 1 + 1 = 2
  4. Д = 0
  5. Г = В = 2
  6. Е = В = 2
  7. Ж = Г = 2
  8. И = Е = 2
  9. К = Ж = 2
  10. З = Е + В + Г= 2 + 2 + 2 = 6
  11. Л = И + Е + З + Ж + К = 2 + 2 + 6 + 2 + 2 = 14

Решение:

1

2

6

1

2

2

2

2

2

14

0

1

5 of 7

№4 (СтатГрад – ноябрь 2019)

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

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

Ответ: 19

Решение:

1

  1. A = 1
  2. Б = А = 1
  3. В = А + Б = 1 + 1 = 2
  4. Д = А = 1
  5. Г = А + Д = 1 + 1 = 2
  6. Е = Б + В = 1 + 2 = 3
  7. Ж = Д + Г = 1 + 2 = 3
  8. З = Е + В + Г + Ж = 3 + 2 + 2 + 3 = 10
  9. К = Ж = 3
  10. И = Е = 3
  11. Л = И + З + Ж + К = 3 + 10 + 3 + 3 = 19

1

1

1

2

2

3

3

10

3

3

19

6 of 7

№5 (СтатГрад – ноябрь 2019)

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

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

Ответ: 26

Решение:

  1. A = 1
  2. Б = А = 1
  3. В = А + Б = 1 + 1 = 2
  4. Д = А = 1
  5. Г = А + В = 1 + 2 = 3
  6. Е = Б + В = 1 + 2 = 3
  7. Ж = Д + Г = 1 + 3 = 4
  8. З = Е + В + Г + Ж = 3 + 2 + 3 + 4 = 12
  9. К = Ж = 4
  10. И = Е = 3
  11. Л = И + Е + З + Ж + К = 3 + 3 + 12 + 4 + 4 = 26

1

1

1

3

2

3

4

12

3

4

26

7 of 7

№6 (А.Г. Минак, вариант №8)

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

Ответ: 25

  1. A = 1
  2. Б = А = 1
  3. В = А = 1
  4. Г = А + Б + В = 1 + 1 + 1 = 3
  5. Ж = Г + В = 3 + 1 = 4
  6. З = Г = 3
  7. К = В + Ж = 1 + 4 = 5
  8. Е = Ж + К = 4 + 5 = 9
  9. И = Г + К + Е = 3 + 5 + 9 = 17
  10. Л = З + К + И = 3 + 5 + 17 = 25

Решение:

1

5

17

1

3

4

9

3

25

1