Логотип GDZ.RU Решение есть!
VK Войти с VK ID

Вопрос:

Д/з. Задача 1. Перенесите граф в тетрадь, запишите все возможные пути из А в К.

Фотография

Ответ ассистента

Чтобы найти количество всех возможных путей из A в K, переберем их по порядку, двигаясь по стрелкам: 1. А-Б-Д-К 2. А-Б-Д-Е-К 3. А-Б-Д-Е-В-К 4. А-Б-Е-К 5. А-Б-Е-В-К 6. А-Г-Е-К 7. А-Г-Е-В-К 8. А-Г-Е-Д-К 9. А-Г-Е-Д-Е-К (в условии не указано, что посещение вершин повторять нельзя, но если это обычный граф, мы идем по направлению стрелок) 10. А-Г-В-К Давайте посчитаем аккуратнее, используя метод динамического программирования (количество путей в вершину равно сумме путей из предыдущих вершин): - A = 1 - Б = 1 (А -> Б) - Г = 1 (А -> Г) - Е = Б + Г = 1 + 1 = 2 - Д = Б + Е = 1 + 2 = 3 - В = Г + Е = 1 + 2 = 3 - К = Д + Е + В = 3 + 2 + 3 = 8 Проверим перебором: - Через Б (всего 4 пути): - A-Б-Д-К - A-Б-Д-Е-К (путь Д-Е-К) - A-Б-Е-К - A-Б-Е-В-К - Через Г (всего 4 пути): - A-Г-Е-К - A-Г-Е-В-К - A-Г-Е-Д-К - A-Г-В-К Итого: 8 путей. **Ответ: 8**
Задать вопрос История вопросов

Другие решения

Что ещё задавали пользователи

Д/з. Задача 1. Перенесите граф в тетрадь, запишите все возможные пути из А в К.
Иконка cookie — уведомление о согласии

Продолжая работу, ты принимаешь cookie и Политику