Известная задача о графах.

Логические задачи

Модераторы: Азарапетыч, Администрация

Ответить
aliev-ruslan
Читатель
Читатель
Сообщения: 1
Зарегистрирован: 04 мар 2012, 21:20
Пол: Мужской

Известная задача о графах.

Сообщение aliev-ruslan »

Думаю, многие знают о проблеме четырёх красок - задаче, заключающейся в следующем:
Есть карта (плоский граф) и 4 карандаша. Как раскрасить все сектора карты так, чтобы сектора, покрашенные в один и тот же цвет, не имели общего ребра...
Эта задача была доказана в 1970-х с помощью компьютера и в 2000-х обычным методом. Однако эти методы очень сложны. Намного проще доказать эту же задачу, если использовать 5 карандашей.
Итак, докажите, что любую карту (плоский граф) можно раскрасить 5 карандашами так, чтобы сектора (грани), покрашенные одним и тем же цветом, не имели общего ребра. Можно воспользоваться теоремой Эйлера (не знаю, будет ли она употребляться в задаче, так как сам решения не знаю :D ).
P.S. Прошу кого-нибудь решить ;-) Очень нужно по школе.

Ответить

Вернуться в «Задачки»