ЕГЭОГЭЕНТ
РУҚА
9

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

ОГЭ · Информатика · Задание 9 · Графы и пути
ПовышеннаяФИПИ7DCCC3Короткий ответ≈ 3 минутыРазбор в 3 шагаОтвет сверен с ключом
Условие

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

Открыть задачу и решить самому
Дальше ответЕсли ещё решаете — начните с подсказок: они ведут к ответу, но не выдают его.
К подсказкам

Решение по шагам

3 шага
1

До городов Б и Г из города А существует по одному пути, а до города В ведут три пути: непосредственно из А, через Б и через Г.

$$N(Б)=1,\quad N(Г)=1,\quad N(В)=1+1+1=3$$
2

До города Д ведут пути из Б и В, а до города Е — пути из Г и В.

$$N(Д)=N(Б)+N(В)=1+3=4,\quad N(Е)=N(Г)+N(В)=1+3=4$$

В город К можно попасть из города Д или из города Е.

$$N(К)=N(Д)+N(Е)=4+4=8$$
Ответ
8
8
так ответ выглядит в бланке

Где здесь ошибаются

Не учитывают пути, проходящие через промежуточный город В.

Считают только непосредственные дороги, а не все возможные маршруты.

Повторно учитывают один и тот же путь.

Закрепить приёмВ теме «Графы и пути» ещё 170 задач — с ответом и таким же разбором.
Тренироваться

Как решать задание 9 ОГЭ, информатика

Разбор этой задачи разложен на 3 шага: видно, откуда берётся каждое число и где теряется балл. Ответ приведён рядом с выкладками, а не вместо них.

Задача из темы «Графы и пути»: в ней 171 задача, и у каждой есть такой же разбор. Регистрация не нужна.

Условие и проверка ответаПравильный ответ к задачеВсе задачи темы «Графы и пути»Все задачи задания 9 ОГЭ по информатикеИнформатика: все задачи и темыПоиск по банку ОГЭКонспект по теме