4CT

[Circiter]

Здравствуйте, предлагаю вашему вниманию небольшую попытку простого (основанного на школьной математике), не использующего компьютер, и чрезвычайно компактного (если со всеми рюшечками, то печатная страница) "доказательства" известной теоремы о четырех красках (ныне уже доказанной жутким способом). Надеюсь услышать какие-нибудь отзывы, критику, и т.д. Слишком серьезно не воспринимайте, но на ошибки укажите, если кому не лень конечно. :)

Если что, ссылка на дядю Мишу (т.е., на меня) обязательна. :)

Формулировка (на всякий случай). Вершины планарного графа можно раскрасить всего четырьмя красками так, чтобы смежные вершины имели различные цвета.

Поводом к написанию этого сообщения послужило обсуждение в соседней, созданной участником iig, теме Проблема 4-краски простой подход (советую предварительно ознакомиться с ней). Сразу предупрежу, что на самом деле никакого строго доказательства у меня нет, а есть лишь аппелирующие к интуиции наброски и размытые рассуждения, которыми я, собственно, и хотел поделиться в этой теме... Поэтому, если у кого-то имеется "аллергия" на попытки нематематиков что-то доказывать, то дальше лучше не читать... :) Остальным же придется переварить все нижеследующее.

Итак, пусть имеется граф $\Gamma$, при этом множество $\mathcal{V}(\Gamma)$ содержит вершины графа, а множество $\mathcal{E}(\Gamma)\subseteq\mathcal{V}(\Gamma)\times\mathcal{V}(\Gamma)$ -- его ребра. Существенно, что граф неориентирован, другими словами, если $(u,\ v)\in\mathcal{E}(\Gamma)$ для некоторых $u,\ v\in\mathcal{V}(\Gamma)$, то и $(v,\ u)\in\mathcal{E}(\Gamma)$.

Необходимо доказать/показать/убедить, что для любого планарного $\Gamma$ существует правильно раскрашивающее отображение $\varphi\colon\mathcal{V}(\Gamma)\to[1;\ 4]\subset\mathbb{N}$ при котором выполняется $\forall\ u,\ v\in\mathcal{V}(\Gamma)\ \left[u\neq v\land(u,\ v)\in\mathcal{E}(\Gamma)\Rightarrow\varphi(u)\neq\varphi(v)\right]$.

Далее будет показано, что требуемая правильная 4-раскраска может быть легко осуществлена почти для любого (в смысле отсутствия у меня контрпримеров) планарного графа (а может быть и для всех планарных графов, это зависит от правильности моих рассуждений).

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

Определение 1. Стягивание ребра есть отождествление соединенных им вершин (с необходимым перенаправлением инцидентных им ребер).

Введем функцию $\mathcal{R}_\Gamma(v)=\{e\in\mathcal{E}(\Gamma)\ |\ e=(v,\ u)\lor e=(u,\ v),\ u\in\mathcal{V}(\Gamma)\}$ возвращающую набор инцидентных ребер для любой вершины $v\in\mathcal{V}(\Gamma)$.

Определение 2. Склейкой двух несмежных вершин называется отождествление этих вершин, то есть стягивание фиктивного ребра, добавленного между ними. Более формально, для графа $\Gamma$ склейкой вершин $u,\ v\in\mathcal{V}(\Gamma):\ u\neq v\land(u,\ v)\notin\mathcal{E}(\Gamma)$ обзовем преобразование $\psi_{u,\ v}\colon\Gamma\mapsto\Gamma'$, конструирующее множества вершин и ребер нового графа $\Gamma'$ по формулам

$$\begin{align}\mathcal{E}(\Gamma') & = \mathcal{E}(\Gamma)\cup\left[\bigcup_{(a,\ u)\in \mathcal{R}_\Gamma(u)}\Big\{(a,\ v),\ (v,\ a)\Big\}\right]\setminus\mathcal{R}_\Gamma(u),\\ \mathcal{V}(\Gamma') & = \mathcal{V}(\Gamma)\setminus\{u\}.\end{align}$$

N.B., Для планарного $\Gamma$ и несмежных $u$, $v$, если $\Gamma'=\psi_{u,\ v}(\Gamma)$, то верно $\forall a\in\mathcal{V}(\Gamma')\ a\in\mathcal{V}(\Gamma)$; это соглашение пригодится в дальнейшем.

Лемма 1. Если в планарном графе содержится более четырех вершин, то среди них найдется хотя-бы одна пара несмежных.

Набросок доказательства. Если несмежных вершин в графе нет, значит граф полный. Однако известно, что максимальный полный планарный граф есть $K_4$, i.e., полный граф с большим количеством вершин заведомо непланарен. Методом от противного, доказано (хотя и так было очевидно). $\blacksquare$

Определение 3. Склейка называется правильной если для планарного $\Gamma$ и некоторых двух его несмежных вершин $u$ и $v$ результирующий граф $\psi_{u,\ v}(\Gamma)$ -- планарен. Сами же такие вершины называются правильно склеиваемыми.

Лемма 2. В произвольном планарном 5-вершиннике найдется пара правильно склеиваемых вершин.

Набросок доказательства. Можно просто выполнить непосредственную проверку всех планарных пятивершинных графов. :) Но, в-принципе, можно попробовать привести такой довод. Лемма 1 говорит нам, что в пятивершинном графе найдется пара несмежных вершин. Их склейка даст 4-вершинник. Поэтому вопрос ставится так: а всякий ли 4-вершинник планарен? Ответ на него, кажется, положителен, что немедленно влечет за собой правильность склейки. $\blacksquare$

Гипотеза 1 (усиление леммы 2). Если $\Gamma$ планарен и $|\mathcal{V}(\Gamma)|>4$, то в $\Gamma$ существует пара правильно склеиваемых вершин.

Набросок доказательства. Здесь уместна индуктивная схема, которую я намечу, пошагово описав простой алгоритм.

Алгоритм 1.

1. Заведем список удаленных вершин $\mathcal{D}\subset\mathcal{V}(\Gamma)$ и проинициализируем его: $\mathcal{D}\gets\varnothing$.
2. Введем временную копию графа $\mathcal{G}\gets\Gamma$. N.B.: здесь и далее, под присваиванием графов понимается присваивание вершин и ребер, т.е., $\mathcal{G}_1\gets\mathcal{G}_2$ означает $\mathcal{V}(\mathcal{G}_1)\gets\mathcal{V}(\mathcal{G}_2),\ \mathcal{E}(\mathcal{G}_1)\gets\mathcal{E}(\mathcal{G}_2)$.
3. Если $|\mathcal{V}(\mathcal{G})|=5$, то с применением леммы 2 алгоритм завершается.
4. Найдем $u,\ v\in\mathcal{V}(\mathcal{G}):\ u\neq v\land(u,\ v)\notin\mathcal{E}(\mathcal{G})$, что всегда возможно в силу леммы 1.
5. Восстановим ранее удаленные вершины и ребра: $\mathcal{G}\gets\Gamma$.
6. Произведем склейку вершин $u$ и $v$: $\mathcal{G}'\gets\psi_{u,\ v}(\Gamma)$.
7. Если $\mathcal{G}'$ планарен, то завершаем алгоритм.
8. Добавим вершину $u$ в список удаленных вершин: $\mathcal{D}\gets\mathcal{D}\cup\{u\}$.
9. Удалим из $\mathcal{G}$ вершины $\mathcal{D}$ вместе с инцидентными им ребрами:
   $$\begin{align}\mathcal{E}(\mathcal{G}') & \gets\mathcal{E}(\mathcal{G})\setminus\bigcup_{a\in\mathcal{D}}R_\mathcal{G}(a),\\ \mathcal{V}(\mathcal{G}') & \gets\mathcal{V}(\mathcal{G})\setminus\mathcal{D}.\end{align}$$
   
   Очевидно, что $\mathcal{G}'$ -- планарен.
10. Присвоим $\mathcal{G}\gets\mathcal{G}'$ и вернемся к шагу 3.

По-сути, выше был приведен алгоритм поиска правильно склеиваемых вершин в планарном графе. Видно, что алгоритм всегда завершается успешно (на каждой итерации мы удаляем одну вершину, что приводит нас в конечном счете к уже исследованному 5-вершиннику). $\blacksquare$

Определение 4. Протоколом сжатия графа $\Gamma$ назовем последовательность $\mathcal{L}_0,\ \mathcal{L}_1,\ \ldots$ из четверок $\mathcal{L}_i\in\mathcal{V}(\Gamma)\times\mathcal{V}(\Gamma)\times\wp(\mathcal{E}(\Gamma))\times\wp(\mathcal{E}(\Gamma))$, где $\wp(\cdot)$ - просто булеан.

Определение 5. Сжатием графа $\Gamma$ называется применение к нему алгоритма сжатия (см. ниже).

Пусть дан планарный граф $\Gamma$ и $|\mathcal{V}(\Gamma)|>4$.

Алгоритм 2 (алгоритм сжатия).

1. Создадим временный граф $\mathcal{G}\gets\Gamma$.
2. Введем счетчик $\mathbb{Z_+}\ni n\gets 0$.
3. Если $|\mathcal{V}(\mathcal{G})|=4$, то завершаем алгоритм.
4. Гипотеза 1 гарантирует, что в $\mathcal{G}$ существует пара правильно склеиваемых вершин. Пусть ими будут вершины $u,\ v\in\mathcal{V}(\mathcal{G})$.
5. Занесем в протокол выбранные вершины и их окружение (инцидентные ребра): $\mathcal{L}_n\gets(u,\ v,\ \mathcal{R}_\mathcal{G}(u),\ \mathcal{R}_\mathcal{G}(v))$.
6. Склеим выбранные вершины: $\mathcal{G}'\gets\psi_{u,\ v}(\mathcal{G})$. Важно заметить, что по определению склейки теперь $u\notin\mathcal{V}(\mathcal{G}')$, но $v\in\mathcal{V}(\mathcal{G}')$.
7. Инкрементируем $n\gets n+1$, присваиваем $\mathcal{G}\gets\mathcal{G}'$ и переходим к шагу 3.

Очевидно, что алгоритм всегда завершается. При этом $n$ содержит количество записей в протоколе $\mathcal{L}_i$, а $|\mathcal{V}(\mathcal{G})|=4$. Ни протокол, ни результирующий граф не выбрасываем, ещё пригодятся. :)

Введем раскрашивающий "вектор" с компонентами $\varrho_x$ индексируемыми вершинами графа $\Gamma$ (того самого, который планарен и содержит более четырех вершин), т.е. $\varrho_x\in[1;\ 4]\subset\mathbb{N},\ x\in\mathcal{V}(\Gamma)$. Фактически, $\varrho_x$ является функцией $\mathcal{V}(\Gamma)\to[1;\ 4]$, но строится динамически с помощью раскрашивающего алгоритма (см. ниже).

Мы используем старый граф $\Gamma$, который использовался в алгоритме 2. Кроме того, как уже было сказано ранее, используем результаты работы этого алгоритма, а именно 4-вершинник $\mathcal{G}$ (N.B., он может быть как полным, так и неполным), число $n$ (длину протокола) и сам протокол $\mathcal{L}_i$.

Алгоритм 3 (раскрашивающий алгоритм).

1. Произведем правильную раскраску графа $\mathcal{G}$ с помощью вектора $\varrho_x$. Теперь верно $\forall a\in\mathcal{V}(\mathcal{G})\ \varrho_a\in[1;\ 4]$ и $\forall a,\ b\in\mathcal{V}(\mathcal{G})\ \big[a\neq b\land(a,\ b)\in\mathcal{E}(\mathcal{G})\Rightarrow\varrho_a\neq\varrho_b\big]$.
2. Если $n=0$, то завершаем работу алгоритма.
3. Декремент $n\gets n-1$.
4. Прочитаем последнюю запись протокола: $(u,\ v,\ U,\ V)\gets\mathcal{L}_n$, здесь $u$, $v$ -- вершины из $\Gamma$, а $U$, $V$ -- наборы инцидентных им ребер. Заметим, что $v$ по определению склейки уже принадлежит $\mathcal{V}(\mathcal{G})$.
5. Восстановим структуру графа, пользуясь текущей записью протокола. Для этого сначала добавим в граф ранее удаленную вершину $u$: $\mathcal{V}(\mathcal{G})\gets\mathcal{V}(\mathcal{G})\cup\{u\}$.
6. Затем удалим ребра, инцидентные вершине $v$: $\mathcal{E}(\mathcal{G})\gets\mathcal{E}(\mathcal{G})\setminus\mathcal{R}_\mathcal{G}(v)$.
7. Наконец, восстановим старые ребра вершин $u$ и $v$:
   $$\mathcal{E}(\mathcal{G})\gets\mathcal{E}(\mathcal{G})\cup U\cup V.$$
8. Логика алгоритма 2 гарантирует, что $(u,\ v)\notin\mathcal{E}(\mathcal{G})$, а так как вершина $v$ уже раскрашена (см. шаг 4 настоящего алгоритма), то мы можем раскрасить $u$ в тот же цвет: $\varrho_u\gets\varrho_v$.
9. Переход к шагу 2.

Гипотеза 2. Раскраска $\varrho_x$ -- правильная.

Набросок доказательства. Проанализируем алгоритм. Он всегда завершается, граф $\mathcal{G}$ совпадает с изначальным графом $\Gamma$. Также легко видеть, что абсолютно все вершины оказываются раскрашенными. Действительно, начальный 4-вершинник полностью раскрашен (см. шаг 1), а алгоритм добавляет к нему в дальнейшем все недостающие вершины (см. шаг 5) и каждой приписывает цвет (см. шаг 8).

Кстати о шаге 8. Этот шаг очень прост, но его последствия туманны и здесь безусловно требуются пояснения. Проблема вот в чем. Конечно, алгоритм 2 обеспечивает несмежность рассматриваемых на этом шаге вершин ($u$ и $v$), поэтому им вполне законно приписывается одинаковый цвет. Но опасность кроется в шаге 7. Именно, на шаге 7 алгоритма 3 мы вслепую снабжаем новую (восстановленную) вершину $u$ ранее имевшимися у неё ребрами рискуя вызвать конфликт цветов (вместе с тем заметим, что операции с ребрами, инцидентными вершине $v$, выполняются без нехороших последствий, ибо ограничиваются лишь удалением некоторых ребер без добавления новых).

Разгадка может быть такой. Изначально, т.е., на шаге 1, граф раскрашен правильно и нам достаточно показать, что правильность раскраски поддерживается в любой момент работы алгоритма. Предположим, что на произвольной итерации, до выполнения опасного шага 8, раскраска является правильной. Исходя из этого предположения мы можем сделать заключение об отсутствии конфликтов цветов между вершиной $v$ и всеми смежными с нею вершинами. Теперь необходимо уяснить, что по определению склейки вершин $u$ и $v$, операция ей обратная (т.е., операция восстановление вершины по записям протокола), по-сути, всего-лишь перенаправляет некоторые ребра, ранее инцидентные вершине $v$, на вершину $u$, которая до этого вовсе не имела ребер (см. шаг 5). А коль скоро эти перенаправляемые ребра не нарушали правильности раскраски будучи инцидентными с вершиной $v$, то и после присоединения к $u$, имеющей тот же цвет, что и $v$, они тоже не будут нарушать раскраски.

В последнем абзаце вроде-бы можно усмотреть доказательство по индукции, там вам и база и шаг... Но это очень мутный момент и требует дальнейшей проработки...

В остальном же, всё вроде-бы в порядке. $\blacksquare$

Для пущего понимания всего вышеизложенного рекомендую вооружиться клочками бумаги и четырьмя разноцветными хреньками с целью проследить ход моих мыслей на каком-нибудь простом практическом примере (применив алгоритмы 2 и 3). :) Также можно и программульку написать, хотя она, предположительно, будет весьма тормознутой для больших политических карт (сложно спрятаться от экспоненциальной асимптотики)...

Резюме.

Собственно, как и обещал, озвучиваю основную идею. Если на карте какие-то страны находятся достаточно далеко друг от друга, другими словами, не являются соседними государствами, то они потенциально могут иметь один и тот же цвет. Если такие страны удастся объединить в союз (и в этом моя идея перекликается с идеей iig'а), то можно будет продолжить раскраску полученной карты, содержащей государств на одно меньше. Повторяя этот процесс мы должны неминуемо прийти к карте, на которой изображены попарно-соседние страны, на раскраске которых уже сэкономить невозможно. Если бы удалось доказать, что любая карта в результате такого процесса сводится к карте, содержащей не более четырех стран, то это могло бы быть одновременно и доказательством 4CT, так как правильно раскрасив такую предельную карту, мы можем вновь преобразовать её к изначальной, сохранив при этом правильность раскраски (ранее объединившиеся союзники ссорятся и снова становятся независимыми странами, но цвета свои продолжают помнить). Основная муть заключается именно в вопросе о возможности безболезненного распада союзов...

Что имеем в итоге? Есть парочка алгоритмов, раскрашивающих произвольную полит. карту. Совокупность доводов, приведенных в доказательство отдельных неясных моментов, позволяет надеяться на правильность такой раскраски, то есть надеяться на то, что соседи имеют различные цвета и всего в палитре их не более четырех... \framebox[1.1\width]{qed}

Как говорится, спасибо за внимание! :) Главный вопрос-просьба у меня такой: найдите фатальную ошибку (я её, кажется, уже нашел, но не выкидывать же писанину). :)

[Xaositect]

Circiter в сообщении #321713 писал(а):

Гипотеза 1 (усиление леммы 2). Если $\Gamma$ планарен и $|\mathcal{V}(\Gamma)|>4$, то в $\Gamma$ существует пара правильно склеиваемых вершин.

Набросок доказательства. Здесь уместна индуктивная схема, которую я намечу, пошагово описав простой алгоритм.

Алгоритм 1.

1. Заведем список удаленных вершин $\mathcal{D}\subset\mathcal{V}(\Gamma)$ и проинициализируем его: $\mathcal{D}\gets\varnothing$.
2. Введем временную копию графа $\mathcal{G}\gets\Gamma$. N.B.: здесь и далее, под присваиванием графов понимается присваивание вершин и ребер, т.е., $\mathcal{G}_1\gets\mathcal{G}_2$ означает $\mathcal{V}(\mathcal{G}_1)\gets\mathcal{V}(\mathcal{G}_2),\ \mathcal{E}(\mathcal{G}_1)\gets\mathcal{E}(\mathcal{G}_2)$.
3. Если $|\mathcal{V}(\mathcal{G})|=5$, то с применением леммы 2 алгоритм завершается.
4. Найдем $u,\ v\in\mathcal{V}(\mathcal{G}):\ u\neq v\land(u,\ v)\notin\mathcal{E}(\mathcal{G})$, что всегда возможно в силу леммы 1.
5. Восстановим ранее удаленные вершины и ребра: $\mathcal{G}\gets\Gamma$.
6. Произведем склейку вершин $u$ и $v$: $\mathcal{G}'\gets\psi_{u,\ v}(\Gamma)$.
7. Если $\mathcal{G}'$ планарен, то завершаем алгоритм.
8. Добавим вершину $u$ в список удаленных вершин: $\mathcal{D}\gets\mathcal{D}\cup\{u\}$.
9. Удалим из $\mathcal{G}$ вершины $\mathcal{D}$ вместе с инцидентными им ребрами:
   $$\begin{align}\mathcal{E}(\mathcal{G}') & \gets\mathcal{E}(\mathcal{G})\setminus\bigcup_{a\in\mathcal{D}}R_\mathcal{G}(a),\\ \mathcal{V}(\mathcal{G}') & \gets\mathcal{V}(\mathcal{G})\setminus\mathcal{D}.\end{align}$$
   
   Очевидно, что $\mathcal{G}'$ -- планарен.
10. Присвоим $\mathcal{G}\gets\mathcal{G}'$ и вернемся к шагу 3.

По-сути, выше был приведен алгоритм поиска правильно склеиваемых вершин в планарном графе. Видно, что алгоритм всегда завершается успешно (на каждой итерации мы удаляем одну вершину, что приводит нас в конечном счете к уже исследованному 5-вершиннику). $\blacksquare$

Не доказано, что если мы пришли на третий шаг с последнего и объединили две вершины в пятивершиннике, то после восстановления удаленных вершин и ребер граф не может стать непланарным

[Circiter]

2Xaositect

Цитата:

Не доказано, что если мы пришли на третий шаг с последнего и объединили две вершины в пятивершиннике, то после восстановления удаленных вершин и ребер граф не может стать непланарным

Кажется, я вас не понял. Если на шаге 3 мы видим 5-вершинник, то на этом алгоритм (доказательство) завершается. То есть в 5-вершиннике мы ничего уже не склеиваем и не восстанавливаем, так как его свойства уже описаны леммой 2.

Заметьте, восстановление вершин и ребер (шаг 5 алгоритма 1) не может нарушить планарности, так как представляет собой всего-лишь откат до начального планарного графа.

Возможно вы имели ввиду, что при использовании алгоритма 3 восстановление структуры графа по протоколу может нарушить планарность... Но это не так, ведь восстановление в алгоритме 3 суть отмена склейки, т.е., обратная операция. Но склейка производится только для планарных графов и является правильной (см. алгоритм 2), поэтому восстановление по соответствующей записи протокола гарантированно даст планарный граф.

Если же вы говорили об особенном положении 5-вершинников в моем доказательстве, то тут опять мне ваше замечание непонятно. Склейку я произвожу только для планарных графов (хотя она, сама по себе, имеет смысл для любых графов). Лемма 2 говорит, что для планарного 5-вершинника возможна правильная склейка. То есть до склейки граф планарен и после восстановления по протоколу он планарен, просто потому, что восстановление с использованием протокола и склейка -- взаимо-обратные операции.

Объясните пожалуйста суть ваших замечаний доходчивее. Спасибо.

-- Пт май 21, 2010 19:40:59 --

Кстати, операции удаления в алгоритме 1 нужны только для того, чтобы можно было пользоваться леммой 1 для продолжения поиска, именно поэтому там предусмотрен столь значительный откат на шаге 5.

[Xaositect]

Допустим, мы удалили из графа $\Gamma$ несколько вершин, получии пятивершинник $\mathcal{G}$. Вы говорите, что в этом случае все доказано, потому что в пятивершиннике вершины склеить можно. Однако не доказано, что склеивание тех же вершин в исходном графе также сохраняет планарность - возможно, непланарные куски появятся в другой части графа.

К примеру, в графе
$\xymatrix{a\ar@{-}[d]\ar@/_50pt/@{-}[dr] & b\ar@{-}[d]\ar@{-}[dl]\ar@{-}[dr]\ar@{-}[l] & \\d & e\ar@{-}[l]\ar@{-}[r] & f}$можно склеить вершины $d$ и $f$, а если добавить к нему одну вершину с ребрами:
$\xymatrix{a\ar@{-}[d]\ar@/_50pt/@{-}[dr]\ar@/^/@{-}[rr] & b\ar@{-}[d]\ar@{-}[dl]\ar@{-}[dr]\ar@{-}[l]\ar@{-}[r] & c\ar@{-}[d]\ar@/^50pt/@{-}[dl]\\d & e\ar@{-}[l]\ar@{-}[r] & f}$, то при склеивании $d$ и $f$ получается $K_5$.

Допустим, сначала мы выбрали для склеивания несмежные вершины

[Circiter]

2Xaositect

Цитата:

Однако не доказано, что склеивание тех же вершин в исходном графе также сохраняет планарность

Да, ваше замечание справедливо. Я действительно пока не знаю как доказать содержащееся в том алгоритме неявное и неочевидное утверждение. Буду кумекать; идея ремонта имеется, но она требует интенсивного допиливания. :)

Приведенных же вами иллюстраций я опять не понял. :) Оба графа прекрасно раскрашиваются моими алгоритмами (2 и 3). Подчеркну, что сохранения правильности склейки при произвольном добавлении вершин и ребер требовать бессмысленно. То есть свобода в добавлении вершин и ребер сильно ограничена и это обстоятельство, думаю, как-нибудь можно будет использовать...

P.S.: Получается, нужно подклеить ещё одну лемму.

Лемма (в контексте доказательства гипотезы 1). Если на шаге 3 алгоритма 1 получен 5-вершинник $\mathcal{G}$, то его правильно склеиваемые вершины $u, v\in\mathcal{V}(\mathcal{G})$, существующие в нем согласно леммы 2, являются правильно склеиваемыми и в изначальном $\Gamma$.

Главное, суметь её доказать или подобрать контрпример... Но это позже... Теперь я вас правильно понял?

[Xaositect]

Circiter в сообщении #322508 писал(а):

Приведенных же вами иллюстраций я опять не понял. :) Оба графа прекрасно раскрашиваются моими алгоритмами (2 и 3).

Да, это не контрпример для гипотезы(она, вполне возможно, верна :) и не для алгоритма(в нем я уже меньше уверен), а просто пример для иллюстрации того, что упомянутое мной недоказанное утверждение действительно важно.

Circiter в сообщении #322508 писал(а):

Главное, суметь её доказать или подобрать контрпример... Но это позже... Теперь я вас правильно понял?

Да.

[Circiter]

Ещё немного мыслей по поводу доказательства дополнительной леммы (см. моё предыдущее сообщение). Такое доказательство могло бы проводиться по-индукции, на каждом шаге которой следовало бы доказать, что если в некотором планарном графе $\mathcal{G}$ есть пара несмежных, но не склеиваемых правильно вершин $u$ и $v$, то после удаления $u$ (с инцидентными ребрами) и осуществимой согласно предположению индукции правильной склейки существующих в оставшемся графе некоторых вершин $p$ и $q$ с последующим восстановлением ранее удаленной $u$ (а также с восстановлением и перенаправлением соответсвующих ребер), результирующий граф (равный графу, полученному из $\mathcal{G}$ правильной склейкой $p$ с $q$) должен оказаться планарным.

Другими словами, если $\mathcal{G}$ -- 6-вершинник, то мы находим несмежные, но не являющиеся правильно склеиваемыми вершины в нем, удаляем одну из них. Затем находим пару правильно склеиваемых вершин в получившемся 5-вершиннике (пользуемся леммой 2). Теперь делаем отмену всех действий и пытаемся показать, что эти правильно склеиваемые вершины из 5-вершинника правильно склеиваемы в 6-вершиннике. То есть, по-сути, мы находим пару склеиваемых вершин в 6-вершинном графе. Проанализировав переход между 5-ти и 6-вершинником, анализируем переход между 6-вершинником и 7-вершинником, 7-ми и 8-вершинником, et cetera. Приходим в конечном счете к самому начальному графу $\Gamma$.

Несмотря на периодически прикладываемые мной к решению этой задачки усилия, она мне так ни капельки и не поддалась. :) Лишь представилась вполне очевидной справедливость описанного индуктивного перехода для, увы слишком тривиального, случая несмежности вершин $u$ и $p$. Ну что же, хотя бы это попробую продемонстрировать.

В основе моей идеи лежит использование стереографических проекций сферических укладок графов. Итак, пусть у нас есть некоторый планарный граф. Допустим, он таков, что мы выбрали две несмежные вершины $u$ и $v$, но правильная склейка этих вершин невозможна. Натянем (правильно уложим) граф на глобус (кстати, изначально, 4CT вроде-бы формулировалась именно в терминах ракраски политической карты на глобусе, а не на плоскости) и спроецируем его на плоскость прямо из вершины $u$ (предварительно можно заменить эту вершину маленькой окружностью и проецирование производить из её центра); образом вершины $u$ при этом будем считать окружность, начерченную вокруг получившейся плоской укладки. Разумеется, эта особая вершина-окружность соединена ребрами с некоторыми другими вершинами. Можно воспринимать такое проецирование как прокол сферы в центре микроскопической окружности на месте вершины $u$ с последующей деформацией (гомеоморфизмом) этой проколотой сферы в обычный круг на плоскости.

Теперь следуя алгоритмам удалим эту особую вершину и в оставшейся части графа отыщем существующую по предположению индукции пару правильно склеиваемых вершин $p$ и $q$. Раз уж они правильно склеиваемы, то мы немедленно произведем такую склейку, а именно, удалим $p$ и перенаправим все её ребра на вершину $q$ не нарушая планарности графа. Заметьте, что самые "внешние" вершины, которые ранее были соединены с особой вершиной $u$, при этом остаются неподвижными (ну или по крайней мере остаются с внешней стороны графа). Остальные, возможно, могут немного быть смещены, чтобы сохранить правильность плоской укладку при перенаправлении ребер, однако сути это не меняет -- эта часть графа остается плоской.

Если после всего этого мы восстановим ранее удаленную особую вершину $u$, то, очевидно, плоская правильная укладка конструкции будет сохранена. Действительно, коль скоро $u$ не была смежна с $p$ (а мы сейчас рассматриваем именно такой специальный случай), то и никакие ребра особой вершины не будут никуда перенаправляться и останутся все на своих местах, т.е., останутся соединенными с "внешними" вершинами, которые, как мы помним, никуда не перемещались и оставались с внешней стороны графа.

Вместе с тем очевидно, что полученный граф изоморфен результату склейки вершин $p$ и $q$ в исходном графе. Таким образом, считаю специальный случай доказанным.

Сложнее дела обстоят с доказательством в условиях смежности $u$ и $p$ (беда здесь в том, что особая вершина будет соединена не только с внешними вершинами, которые всегда "на виду", но и одним ребрышком будет погружаться в мутную мякоть оставшейся части графа, тем самым непредсказуемо влияя на планарность при всех последующих трансформациях наших построений). Здесь я пока опираюсь только на чистую интуицию, а свою уверенность могу продемонстрировать на простейшем конкретном примере. Ещё я, пожалуй, без потери общности (если о ней сейчас вообще можно говорить) буду считать, что $v=q$, да и вообще, лучше переобозначу вершины во избежание недоразумений. :)

В качестве примера давайте рассмотрим такой простенький граф:

$$\xymatrix{ *+=[o]++[F]{x} \ar@{-}[rr]\ar@{-}@/^4pc/[rrrd]\ar@{-}[dd] & & *+=[o]++[F]{2} \ar@{-}[dr] & \\ & *+=[o]++[F]{z} \ar@{-}[dl]\ar@{-}[dr]\ar@{-}[ru] & & *+=[o]++[F]{y} \\ *+=[o]++[F]{1} \ar@{-}@/^2pc/[uurr]\ar@{-}[rr]\ar@{-}@/_4pc/[rrru] & & *+=[o]++[F]{3} \ar@{-}[uu]\ar@{-}[ur] & }$$

Рис. 1.

Здесь вершины $x$ и $z$ несмежны, но правильно не склеиваются (склейка дает $K_5$). Если удалить $x$, правильно склеить $y$ с $z$ и восстановить $x$, то получится граф, который получился бы в результате склейки $y$ с $z$ прямо в исходном графе. Но мне необходимо разработать более универсальный метод для демонстрации этого свойства; именно в условиях смежности $x$ и $y$, чего не хватало мне ранее.

Так, исходный граф имеется. Теперь я применю ранее описанный прием со стереографическими проекциями, но в немного усовершенствованной форме. Заметим, что соответствующее преобразование укладки, если его рассматривать in situ прямо на плоскости, суть замена определенной вершины малой окружностью с последующим растягиванием этой окружности до достаточно больших размеров и одновременным перемещением всех вершин для сохранения плоской правильной укладки и достижения "внешнего" расположения вершин, ранее смежных с выбранной особой вершиной. Идея в том, что можно попробовать применить такое преобразование сразу к нескольким вершинам. Да, пересечения линий при этом, вообще говоря, не избежать, но такие пересечения особых вершин-окружностей и их ребер можно считать в некотором смысле "условными", зная, что комбинаторная структура такого нагромождения по-прежнему ничто иное как планарный граф (да и, строго говоря, именно ребра-то по прежнему и не пересекаются; так что все в порядке).

Если растягиванию подвергнуть вершины $x$ и $z$, сделав вершину-окружность $x$ большей чем $z$, то должно получиться что-то вроде этого:

$$\shorthandoff{

Рис. 2.

Прямоугольниками выделены важные участки графа, в которых на рисунке присутсвуют ранее упомянутые условные пересечения. Важно при последующих трансформациях сохранять эти участки совершенно неизменными, что будет хоть как-то гарантировать планарность.

Все дальнейшие действия будем производить именно с таким представлением графа. Вот например, надо нам удалить вершину $x$. Возьмем, да и удалим (на самом деле она и её ребра все-равно будут видны, но будут прорисовываться пунктирными линиями):

$$\shorthandoff{

Рис. 3.

Здесь двойной стрелкой показано направление склейки вершины $y$ с $z$. Если эту склейку осуществить (напомню, что по предположению индукции такая склейка окажется правильной), то должно получиться следующее (обратите внимание на выделенный прямоугольником результат пренаправления ребра, ранее соединявшего $x$ и $y$):

$$\shorthandoff{

Рис. 4.

Теперь мы можем восстановить удаленную вершину $x$, просто заменив пунктирные линии сплошными:

$$\shorthandoff{

Рис. 5.

Сравним рисунок 5 с рисунком 2. Легко видеть, что выделенные большими прямоугольниками участки не изменились. Ещё один (выделенный прямоугольником поменьше) участок с "шунтирующим" ребром безусловно уложен правильно. Если прорисовать вершину $x$ именно в виде "точечной" вершины, а не в виде большой окружности, то получится и вовсе с очевидностью плоский граф:

$$\shorthandoff{

Рис. 6.

Понятно, что эту технику можно применять вообще к любым подходящим графам и везде мы будем приходить к результату, похожему на представленный рисунком 5. Несомненно, все это не может рассматриваться как удовлетворительное доказательство дополнительной леммы. Фактически, написанное -- это просто попытка извлечь из моего подсознания корни той сильной интуитивной уверенности в справедливости этой самой дополнительной леммы (ну и повод для обкатки некоторых свежедобавленных на этот форум опций пакета \Xy-pic); и я могу лишь надеяться, что кому-нибудь удастся поспособствовать формализации этой интуиции или её опровержению. Такова ситуация на данный момент, может быть в ближайшем будущем ещё что-нибудь придумаю. :)

P.S.:
Кстати, хотя это и не существенно, но формулировку леммы 2 можно обновить (с небольшим усилением). А именно:

Лемма 2 (версия 2). Любые две несмежные вершины произвольного планарного 5-вершинника правильно склеиваемы.

Доказательство при этом остается прежним.

Более того, её можно ещё немножко улучшить:

Лемма 2 (версия 3). Любые две несмежные вершины произвольного планарного 5-вершинника правильно склеиваемы простым удалением одной из этих вершин вместе с инцидентными ей ребрами.

На этот раз доказательства у меня нет, ну кроме прямой проверки всех планарных 5-вершинников... :)

[Circiter]

Чтобы было, что комментировать, попробую описать мою схему доказательства 4CT как можно более кратко.

• Доказательство получилось конструктивным, хотя это и не означает, что его можно использовать как основу для реальных раскрашивающих алгоритмов. Проблема здесь конечно же в низкой эффективности (производительности).
• На первом проходе производится редукция графа, суть которой заключается в итеративном поиске и склеивании подходящих вершин. Процесс останавливается только тогда, когда от изначального графа останется всего четыре вершины. Редукция недеструктивна, так как её побочным продуктом является история (протокол) вносимых изменений, по которой можно последовательно восстановить исходный граф.
• На втором проходе производится восстановление графа на основе сохраненной истории его преобразований. Так как при первом проходе склеивались только несмежные вершины, то при восстановлении графа с использованием протокола этот факт используется для раскраски ранее склеенных вершин в одинаковый цвет. В результате получается, что для раскраски всего изначального (большого) графа требуется цветов не больше чем для раскраски его редуцированной четырехвершинной версии, для раскраски которой, очевидно, четырех красок вполне достаточно.

Кто как думает, есть ли в предложенной схеме смысл и не заблуждаюсь ли я слишком сильно?

Интересно было бы также поговорить о возможных путях обобщения такого доказательства. Например, что если при редукции, на каждой итерации требовать сохранения не планарности, а какого-то другого свойства графа, скажем, правильной (без пересечения ребер) укладываемости графа на сферу с фиксированным количеством ручек? Вообще, что науке известно о связи рода (или эйлеровой характеристики) с хроматическим числом графа?

Не менее интересен вопрос о раскрашиваемости бесконечных графов. К примеру, мы ведь можем говорить о планарности бесконечного графа, возможна ли тогда какая-либо "топологическая классификация" и непланарных бесконечных графов? То есть, имеет ли смысл эйлерова характеристики для таких графов и может ли существовать обобщенная цветовая редукция (аналогичная описанной для планарного случая), позволяющая установить мощность минимального разбиения вершин бесконечного графа на независимые классы (внутри которых все вершины попарно несмежны)?

Надеюсь на ваши ответы... Ссылочки на современные работы очень даже приветствуются. Огроменное спасибо.