Задача на раскраску областей, полученных окружностями

[xmaister]

Конечное множество окружностей делит плоскость на области. Показать, что мы можем раскрасить плоскость в два цвета так, чтобы никакие две смежные области (с общей дугой ненулевой длины входящих в состав границы каждой области) не имели одинаковый цвет.

(попытка решения)

Возможно напишу глупость, но по другому не знаю как
Пусть $C_i$- круг $i=1,2,\ldots ,n$. Обозначим $X=\bigcup\limits_{i}^{n}C_i$
Закрасим $\overline{X}$ в цвет $A$. Обозначим пересечение нечётного количества кругов как $Y$, чётного как $Z$, если $Y\neq\varnothing$, то красим его в цвет $B$, если $Z\neq\varnothing$, то красим в цвет $A$. Если такая раскраска справедлива, то я не пойму, как строго доказать, что она справедлива :(

[мат-ламер]

Вместо окружности рассмотрим круги, которые им соответствуют. Берём любую точку. Если количество накрывающих его кругов чётно - красим эту точку в один цвет. Если нечётно - в другой.

-- Пн авг 08, 2011 21:43:47 --

xmaister. Посмотрел попытку Вашего решения. Тоже рассматривается чётность количества кругов. Но ничего понять не могу.

[xmaister]

мат-ламер
Так я вроде тоже самое написал. Мне непонятно, как доказать, что пересечение чётного количества кругов будет смежно только с пересечением нечётного количества. Или это очевижно

[ИСН]

Ну дак они это, кагбе, отличаются на один - на тот, по дуге которого они смежные.

[мат-ламер]

Насчёт пересечения чётного числа кругов я ничего не писал.

Цитата:

Так я вроде тоже самое написал

А вроде и не совсем. Однако, Вашего решения я просто не понял.

[xmaister]

мат-ламер
Я пересечение чётного числа кругов красил в цвет $A$, нечётного в цвет $B$ и оставшуюся часть плоскости в цвет $A$. А исходя из того, что сказал ИСН, можно сказать, что такая раскраска будет верной.

[Circiter]

xmaister писал(а):

Показать, что мы можем раскрасить плоскость в два цвета так, чтобы никакие две смежные области (с общей дугой ненулевой длины входящих в состав границы каждой области) не имели одинаковый цвет.

Можно попробовать по-аналогии с пофасеточной 2-раскраской графа с вершинами четной степени. Идея в том, что система окружностей на плоскости имеет по четному числу линий, выходящих из каждой точки пересечения. Вроде-бы, через каждую вершину можно пустить простой цикл, т.е. несамопересекающуюся последовательность дуг, соединяющих точки пересечения окружностей. Находим и удаляем такой цикл. Потом рекурсивно раскрашиваем оставшуюся систему в два цвета и восстанавливаем цикл. Наконец, просто инвертируем цвета внутри цикла. Готово! Случай "окружность в окружности" тривиален.