Условие:
На рисунке - схема дорог, которые связывают города А, Б, В, Г, Д, Е, Ж и Н. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько путей ведут из города А в город Н и при этом не проходят через город В?
Решение:
1. Условие
Нужно найти количество путей из А в Н, которые не проходят через В.
Города: А, Б, В, Г, Д, Е, Ж, Н.
Стрелки задают направление движения.
2. Подход
Можно найти общее количество путей из А в Н, затем вычесть количество путей из А в Н, проходящих через В.
Но удобнее сразу строить подсчёт путей, запрещая заходить в В.
3. Предполагаемая структура графа (по типичным задачам ЕГЭ):
- А → Б, Г
- Б → В, Д
- В → Е, Ж
- Г → В, Д
- Д → Е, Н
- Е → Ж
- Ж → Н
- Н — конечный.
Но в условии сказано, что какие-то блоки могут оказаться лишними...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Что нужно знать по теме:
Что нужно знать по теме
Алгоритм решения
Топ 3 ошибок
Что спросит препод
Похожие задачи