Задача Задача №2256929
А
А
В магическом замке миллион комнат. Некоторые комнаты соединены лестницей или порталом. Каждый портал соединяет две комнаты. Каждая лестница соединяет две комнаты. В каждой комнате есть ровно одна лестница и ровно один портал. Докажите, что эти комнаты можно раскрасить в два цвета так, чтобы ни из какой комнаты нельзя было попасть в комнату того же цвета, не посетив других.
Ваша задача связана с раскрашиванием графа, где комнаты представляют собой вершины, а лестницы и порталы — рёбра. Поскольку в каждой комнате есть ровно одна лестница и ровно один портал, это приводит к интересной структуре.
Структура графа:
- Комнаты можно рассматривать как вершины графа.
- Лестницы и порталы создают рёбра, соединяющие эти вершины.
- Важно отметить, что каждую вершину (комнату) соединяет ровно одно ребро лестницы и ровно одно ребро портала.
Циклы в графе:
- Каждый цикл, образуемый лестницами или порталами, будет четной длины, поскольку каждая комната соединена двумя рёбрами (лестницей и порталом).
- Поскольку в каждой комнате соединены ровно одна лестница и один портал, при движении по этому графу вы будете перемещаться чередуя типы соединений.
Раскрашивание:
- Чтобы раскрасить граф в два цвета (например, красный и синий), мы можем использовать жадный алгоритм, начиная с произвольной комнаты и раскрашивая её в один цвет.
- Затем, двигаясь по лестнице, мы раскрасим соседнюю комнату в другой цвет, и так далее.
Обоснование:
- Если в процессе раскрашивания вы никогда не сможете вернуться в комнату того же цвета (поскольку при каждом перемещении по лестнице или порталу цвет будет меняться), значит, вы достигли своей цели.
- Таким образом, любой цикл, которого мы можем достичь, будет иметь чередующиеся цвета.
С учетом всех этих аспектов, можно сделать вывод, что комнаты можно эффективно раскрасить в два цвета, так что ни одна комната не будет соединена с другой того же цвета без промежуточного перехода.
Таким образом, задача доказана: комнаты можно раскрасить в два цвета, соблюдая условия задачи.
