Количество путей в графе
Коротко
Дана схема дорог с направлениями. Число путей до города равно сумме числа путей до всех городов, из которых в него ведёт дорога. Идите от старта к финишу, подписывая числа у вершин.
Главное
| Шаг | Действие |
|---|---|
| 1 | старт = 1 |
| 2 | для каждой вершины сложить входящих |
| 3 | обходить в порядке следования стрелок |
| 4 | ответ — число у финиша |
Типичные ошибки
- Считают вершину до того, как посчитали всех её предков.
- Учитывают дороги против стрелки.
Что дальше
Проверьте себя на заданиях этого типа в тренажёре Upward. Начните с диагностики по предмету: она покажет, какие номера уже получаются, а какие стоит подтянуть, и по её итогам соберётся личный план подготовки.
Как это выглядит в задании 9
Пример 1 из 2
Дороги: А→Б, А→В, Б→В, Б→Г, В→Г, В→Д, Г→Д. Сколько путей из А в Д?
- Разбор
- Б = 1, В = 2, Г = 3, Д = В + Г = 5.
- Ответ
- 5
Пример 2 из 2
Как учитывать обязательный пункт?
- Разбор
- Пути до него × пути от него.
- Ответ
- Умножением
Мини-тест: 5 вопросов
- Вопрос 1 из 5
Число путей в старт?
Показать ответ
Ответ: 1.
Начало.
- Вопрос 2 из 5
Правило?
Показать ответ
Ответ: Сумма по входящим дорогам.
Динамика.
- Вопрос 3 из 5
Через обязательную вершину?
Показать ответ
Ответ: Перемножить.
До и после.
- Вопрос 4 из 5
Избегать вершину?
Показать ответ
Ответ: Считать её как 0.
Удалить.
- Вопрос 5 из 5
Направление?
Показать ответ
Ответ: Только по стрелкам.
Ориентированный граф.
Проверьте всё задание 9, а не одну тему
Диагностика Upward покажет, какие задания ОГЭ по информатике стоит подтянуть в первую очередь.
Уже есть аккаунт? Войти