Mail.ruПочта0Мой Мир0ОдноклассникиВКонтактеИгры0ЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Помогите пожалуйста решить

Zoloto Бобинь Ученик (112), на голосовании 5 месяцев назад
В компьютерной игре главный герой перемещается по государству, состоящему из нескольких островов. Острова соединены мостами так, что из каждого можно добраться до любого другого. Герой обошёл все острова в поисках карты, пройдя по каждому мосту ровно один раз. Но на острове Туманном он побывал целых 14 раз. Сколько мостов ведёт с острова Туманного, если герой не с него начал и не на нём закончил свой поход?
Голосование за лучший ответ
Шалунишка Шалунишечкин Профи (607) 6 месяцев назад
Он пришёл в волшебное королевство к слаймам и его поставили раком
MacyУченик (108) 1 месяц назад
Ах ты шалунишка
Macy Ученик (108) Мария Монкевич, Бль, только потом заметила ник чела
mexahuk6 Просветленный (20518) 6 месяцев назад
Для решения задачи используем теорию графов. Острова можно представить как вершины, а мосты — как ребра.

Определение степени вершин: Степень вершины — это количество рёбер (мостов), соединяющих её с другими вершинами (островами). Если герой побывал на острове Туманном 14 раз, это означает, что он прошёл по всем мостам, ведущим к этому острову, 14 раз.

Чётная и нечётная степень: В графах, если путь проходит по каждому ребру ровно один раз, то все вершины, кроме двух, должны иметь чётную степень. Вершины с нечётной степенью представляют собой стартовую и конечную точки пути.

Степень острова Туманного: Поскольку герой не начинал и не заканчивал свой путь на острове Туманном, этот остров должен иметь чётную степень. При этом каждый раз, когда он приходит на этот остров, увеличивается степень этой вершины на 1. Герой 14 раз посещал этот остров, значит, он «вошёл» 14 раз и, соответственно, «вышел» 14 раз, что подтверждает, что степень этого острова равна 14.

Таким образом, с острова Туманного ведет 7 мостов.
Похожие вопросы