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

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

Посмотреть пояснение и ответ
Чтобы найти количество путей в графе, нужно складывать значения всех вершин, из которых ведут стрелки в текущую. Начинаем с единицы в пункте А и двигаемся по направлению стрелок. К = В + Д + Е = 2 + 3 + 3 = 8
Ответ: 8

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

Посмотреть пояснение и ответ
Чтобы найти количество путей в графе, нужно складывать значения всех вершин, из которых ведут стрелки в текущую. Начинаем с единицы в пункте А и двигаемся по направлению стрелок. К = Г + Ж + Е = 4 + 5 + 3 = 12
Ответ: 12

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

Посмотреть пояснение и ответ
Чтобы найти количество путей в графе, нужно складывать значения всех вершин, из которых ведут стрелки в текущую. Начинаем с единицы в пункте А и двигаемся по направлению стрелок. Л = И + З + Ж + К = 3 + 10 + 1 + 1 = 15
Ответ: 15

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

Посмотреть пояснение и ответ
Чтобы найти количество путей в графе, нужно складывать значения всех вершин, из которых ведут стрелки в текущую. Начинаем с единицы в пункте А и двигаемся по направлению стрелок. G = E + C + F = 3 + 1 + 2 = 6
Ответ: 6

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

Посмотреть пояснение и ответ
Чтобы найти количество путей в графе, нужно складывать значения всех вершин, из которых ведут стрелки в текущую. Начинаем с единицы в пункте А и двигаемся по направлению стрелок. К = Д + Г + Е = 4 + 1 + 1 = 6
Ответ: 6