Разработка задание ОГЭ по теме: "Графы. Поиск путей".

Тема: Графы. Поиск путей.

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

Е

Решение:

Главную идею решения: (число дорог в город N есть сумма дорог, приводящих в города, из которых есть прямой проезд в город N), отразим на самой схеме, показывая на ней ЧИСЛО ДОРОГ, приводящих в каждый город.

1. Последовательность очевидна: начинаем с Б и Г (городов, куда есть по 1-й дороге из А)

1. Посчитаем дороги в В: 1 (из A)+ 1(дороги города Б)+ 1(дороги города В) = 3

1. Аналогично посчитаем дороги в Д, И, Е, Ж:

1. Определяем число дорог в город К, как сумму дорог в города, с которыми он связан: Д, И, Ж, Е.

1. Ответ: 13.

2 Тема: Графы. Поиск путей

Сегодня мы рассмотрим решение задачи 11 ГИА по информатике.

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

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

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

Итак, начнем решение с конца, т. е. с города К. Как мы видим, в город К можно приехать из городов Е, В, Г, Ж. Отобразим это графически

Шаг 1

Далее, на втором шаге определим, откуда можно добраться в города Е, В, Г, Ж. К примеру,

• в город Е можно добраться только из города Б,

• в город В — из городов А и Б,

• в город Г из городов А, В и Д,

• в город Ж из городов Г и Д.

Графически это будет выглядеть таким образом:

Шаг 2

Таким образом, мы будем продолжать до тех пор, пока каждая ветка не приведет к городу А. В итоге получится такая диаграмма — дерево:

Шаг 3

Здесь зеленым цветом я выделил конечные пункты — город А. Осталось только посчитать их количество — это и будет правильный ответ. В нашем случае их 12. Правильный ответ: 12.