дан многоугольник с 201 вершиной. требуется покрасить каждую из них в какой-нибудь цвет таким образом, чтобы несоединённые одной стороной вершины были разных цветов. каким…
Дан многоугольник с 201 вершиной. требуется покрасить каждую из них в какой-нибудь цвет таким образом, чтобы несоединённые одной стороной вершины были разных цветов. каким наименьшим количеством цветов можно это сделать?
Для решения задачи о раскраске многоугольника с 201 вершиной необходимо использовать понятие о «раскраске графа». В этом случае каждая вершина многоугольника представляет собой узел графа, а стороны – ребра.
Основное условие раскраски заключается в том, что несоседние вершины должны быть разного цвета. В данном случае можно использовать теорему о 2-цветной раскраске, но с учетом того, что у нас не просто цикл, а многоугольник с нечетным количеством сторон.
Поскольку многоугольник с 201 вершиной – это нечетный цикл, он требует не менее 3 цветов для правильной раскраски. Это происходит потому, что в нечетном цикле, если бы мы использовали только 2 цвета, то в одной из частей нам пришлось бы повторить цвет на соседних вершинах.
Следовательно, для раскраски многоугольника с 201 вершиной при условии, что несоседние вершины должны иметь разные цвета, необходимо использовать как минимум 3 цвета.
