💻

ОГЭ информатика: Число путей в графе

Информатика, 9 класс · ОГЭ информатика, уровень КИМ

📚 Программа 9 класса · модуль «Практика: ОГЭ информатика, уровень КИМ» — тренажёр 6 из 6. За освоение тренажёра — +15 ★.

Задание 1 из 10+0 ★

Загрузка…

🖨 Распечатать / PDF

Правило и как решать

Число путей в графе: задание ОГЭ по информатике без компьютера.

Подсказка: Выполни шаги вручную; промежуточные результаты записывай. Ответ — целое число.

Примеры с разбором

Пример 1

Между населёнными пунктами построены односторонние дороги: А→Б, А→В, Б→В, А→Г, Б→Г, В→Г, Б→Д, Г→Д, Б→Е, Г→Е, Д→Е, Б→Ж, В→Ж, Е→Ж. Сколько существует различных путей из пункта А в пункт Ж?

Ответ: 13

Решение: Число путей в вершину = сумма чисел путей в предшествующие вершины.

Пример 2

Между населёнными пунктами построены односторонние дороги: А→Б, А→В, Б→В, А→Г, Б→Г, В→Г, А→Д, Г→Д, Г→Е, Д→Е, А→Ж, Г→Ж, Д→Ж, Е→Ж. Сколько существует различных путей из пункта А в пункт Ж?

Ответ: 19

Решение: Число путей в вершину = сумма чисел путей в предшествующие вершины.

Пример 3

Между населёнными пунктами построены односторонние дороги: А→Б, А→В, Б→В, Б→Г, В→Г, А→Д, В→Д, Г→Д, Г→Е, Д→Е, А→Ж, Г→Ж, Д→Ж, Е→Ж. Сколько существует различных путей из пункта А в пункт Ж?

Ответ: 19

Решение: Число путей в вершину = сумма чисел путей в предшествующие вершины.

Другие тренажёры: Информатика, 9 класс