Форум » Поиск путей в графе » Опечатка ли? » Ответить
Опечатка ли?
Arkadii: Всем хорошего дня. ЕГЭ-2022, задание 13, номер 99 (А.Богданов). Между D и B двусторонняя стрелка. Нигде такого нет. Как это решается? Не понимаю, как считать графы в этих точках. Спасибо всем
Ответов - 5
Danov: По каждой стрелке можно ходить только один раз. Поэтому по двухсторонней стрелке мы можем либо вверх пройти, либо вниз. Но туда сюда не можем.
s11kai: (№ 4185) (А. Богданов) На рисунке представлена схема дорог, связывающих города A, B, C, D. По каждой дороге можно двигаться только один раз в направлении стрелки. По дороге из B в D можно двигаться в любую сторону, но лишь один раз. Сколько существует различных путей из города A в город C, проходящих либо через В (но не D), либо через D (но не B), либо через B и D одновременно? Danov пишет: По каждой стрелке можно ходить только один раз. Поэтому по двухсторонней стрелке мы можем либо вверх пройти, либо вниз. Но туда сюда не можем. С учетом сказанного выше, если идти по часовой стрелке и пройти из города Б в Д можно, то при движении против часовой стрелки из Д в Б пойти уже нельзя? Но в таком случае, как получается ответ = 100!? А если двигаться из А в С, не заходя в D или через D (но не В) как получить тот же самый ответ 100? Подскажите, где я ошибаюсь: Спасибо за подсказку!
s11kai: Danov пишет: из А в С через В: 5*5=25 из А в С через D: 5*5=25 этот момент понятен, Danov пишет: из A в С через B и D: 5*5=25 и этот понятен, а вот следующий - ведь мы уже прошли по дороге BD, а по условию, по ней пройти можно только один раз! s11kai пишет: По дороге из B в D можно двигаться в любую сторону, но лишь один раз И кроме того, союз либо, разве не означает, что нужно пройти только из А в С через В, или из A в С через D. Неужели союз либо равнозначен союзу и В таком случае, почему не написать так: s11kai пишет: Сколько существует различных путей из города A в город C, проходящих через В (но не D) и через D (но не B) и через B и D одновременно? Прошу прощения за скудность мысли и спасибо за пояснения
Danov: Опечатки в условии нет. Решается так: из А в С через В: 5*5=25 из А в С через D: 5*5=25 и далее двунаправленная стрелка! из A в С через B и D: 5*5=25 из А в С через D и B: 5*5=25 Всего 4*25=100 Эта задача на понимание комбинаторики. Всего 4 одинаковых фрагмента по 5 путей в каждом. Далее просто перемножаем "каждый с каждым", перебирая разные варианты. И в итоге всё складываем. Успехов!
s11kai: Danov пишет: Эта задача на понимание комбинаторики. Всего 4 одинаковых фрагмента по 5 путей в каждом. Далее просто перемножаем "каждый с каждым", перебирая разные варианты. И в итоге всё складываем. Успехов! Спасибо, Danov!
полная версия страницы