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

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

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

Демонстрационный вариант Единый государственный экзамен ЕГЭ 2017 г. – задание №15

Решение:

Определяем количество путей из города А в город В:
— напрямую из А в В,
— через Б (АБВ),
— через Г , (Из А в Г можно попасть напрямую(АГ) и через Д (АДГ), получается, из города А в город В через Г можно попасть 2мя способами – (АГВ) и (АДГВ).
итого: 4

Теперь будем определять пути из пункта В в пункт М.

В пункт Е ведут 4 маршрута из В.

В пункт Ж ведут 8 маршрутов: 4 маршрута из В, 4 маршрута из Е.

В пункт И ведут 12 маршрутов: 4 маршрута из Е, 8 маршрутов из Ж.

В пункт К ведут 12 маршрутов из И.
В пункт Л ведут 12 маршрутов из И.

В город М ведут 36 маршрутов: 12 маршрутов из И, 12 маршрутов из К, 12 маршрутов из Л.

Ответ: 36

Демонстрационный вариант Единый государственный экзамен ЕГЭ 2016 г. – задание №15

Решение:

Примечание: на рисунке зеленым цветом в кружочке отмечено количество маршрутов в каждый пункт. А синие цифры обозначены для более легкого сложения и нахождения конечного результата.

Начинаем считать пути из пункта А=1.

Из пункта А идут пути в пункты Б,В,Г,Д → рисуем из пункта А синим единицы к четырем путям. Определяем, что в пункты Б и Д проложен единственный маршрут из пункта А , слудует, что у этих двух пунктов количество= 1.

В пункт Г мартруты исходят из пунктов А и Д, которые равны единице, следует что количество мартрутов в пункте Г = 1+1.

В пункт В мартруты исходят из пунктов А,Б,Г. Складываем значения количеств маршрутов каждого пункта →1+1+2=4.

Ответ: 56

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

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

Решение:

Ответ: 18

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

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

Решение:

Ответ: 15

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

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

Решение:

Ответ: 7

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

Решение:

Ответ: 33

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

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

Решение:

Ответ: 9

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

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

Решение:

Ответ: 30

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

Решение:

Ответ: 42