Персональный сайт - решение ГИА

Текст задания.

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

Решение:

В данном задание рассматривается ориентированный граф.

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

Давайте по рисункам их рассмотрим:

1 рис. - пути из города А через Б - всего 3.

2 рис. - пути из города А через В - всего 2.

3 рис. - пути из города А через Г - всего 3.

Итого: 3 + 2 + 3 = 8 путей из города А в город К.

вернуться

Сайт учителя Фадеева А.В.

решение ГИА - 11