有關染色問題是否有通解的證明

導語：有關染色問題是否有通解的證明一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

任何整體陸地板塊均可視作由其中任何一國，以每個鄰國作為單位自外擴展而成，依次國家為a1、a2、……an，顏色為1、2、3，4遵循以下原則涂色。

1、一旦一國家邊界被完全包圍，這以后它將不會再有任何新增鄰國，同時它的現有鄰國也已經全部涂色完畢，因此該國不會對接下來的涂色產生任何影響，出于簡化分析的需要將該國視作“消失”。

2、新增國家與原板塊有兩段以上不連續邊界時，這時分段國界空白區域必然會產生的國家，改為優先擴展空白區域國家，至于不連續邊界鄰國則會在后面涂色，即只擴展連續邊界國家。

3、非必要不使用4顏色。

4、先給原有國家涂色后增加新國家只是為分析簡化的需要，真實情況是地圖上一開始就是客觀存在的，預先的涂色是考慮了所有可能情況后多個可選顏色中的一個，但實際地圖只有一種情況，所以允許在發現不符合地圖實際情況后，在保證規則自治的前提下修改原有顏色。

5、一國如同時在板塊邊緣擁有兩段以上不連續的邊界，則客觀上在內部形成與整體板塊隔絕的封閉區域，封閉區域內按照與該國關系劃分為兩種顏色類型：兩種與該國相異顏色，一種相同顏色，其中兩種相異顏色具備對稱性可以隨意輪換，如圖1，其中2和3可以輪換。

在第一次出現顏色4時，整體板塊如下面示意圖，由最外圍國家部分邊界組成的環形結構。

將外圍每一段邊界對應的國家分為兩種：

A、只有一段邊界與外圍重合，此類國家的特點是該段一經被包圍該國便進入“消失”行列（原則1）

B、有兩段或兩段以上邊界與外圍重合，此類國家的特點是在兩段或兩段以上邊界的中間形成封閉區域，內部與該國相異的兩種顏色具備對稱性，可以自由互換（原則5）
下面對各種情況進行分類：

引理1：對于B類國家形式的封閉區域，其內部的其它B類國家由于無法跨越封閉區域，只能在內部形成形狀類似的新的封閉區域，最終形態是以中間一段區域作為分界，兩側相對獨立的波紋狀分布，如圖6，對于處于同一側的所有B類國家而言，由中間向兩側，相鄰B類國家又構成新的封閉區域，以右側為例，由中間向右依次設為T1、T2……Tn，根據原則5與進行如下操作：在保證T1顏色不變的情況下

若Tn,Tn+1同色，則Tn+1保持顏色不變；

若Tn,Tn+1異色，但Tn+1并非第三種顏色；則Tn+1保持顏色不變；

若Tn,Tn+1異色，且Tn+1是第三種顏色，根據原則5，將Tn+1變換為與Tn相異的另一種顏色，同時每次變色后，相應封閉區域內的其它“消失”國家也要進行相應變色。

結論：對于同側形成波紋狀分布的所有B類國家在保證靠中間一側的B類國家顏色不變的前提下，再選擇邊界三種顏色與B相異色的兩種顏色中任一種，即可完成對同側所有B類國家染色，且保持總體使用顏色數仍為3。

即在T1顏色不變下再任選另外兩種顏色中的任一種可保證在整體板塊不使用顏色4的前提下，完成對同側所有B類國家的重新染色。

其中兩種顏色必須包括T1顏色，可知，同側的所有B類國家，可以用兩種顏色即可涂色，引理完畢。

①1.2之間存在3，若3全部為A型，則4與3互換即可，若3有部分B型，則進入下一步。

②1.3之間若不存在2，則2必在右側封閉區域內（為了3確認此情況，根據原則5的對稱性，將2換作1）若右側封閉區域仍有B類國家，則根據引理1，用3.1兩顏色將全部B類國家標記。

這時2有兩種可能：

①2為A型，則2與4互換即可。

②2被1.3兩種顏色替換，這時整個邊界已經沒有2，所以不需要第四種顏色，即這時已不屬于“不得不用4色”的前提。

1.3之間若存在2，且所有2均對應A類國家，那么將③內封閉區域內1.2互換，若右側封閉區域仍有B類國家，則根據引理1，用3、1兩種顏色將全部B類國家染色，這時可以確認封閉區域內無顏色2的B類國家，然后再4與所有2互換，4消失即可得到3色地圖。

1.3之間若存在2，且2有部分或整體為B類，2的B類國家分為左側或右側。

若2左側，側2替代1的位置，繼續討論2、3之間是否存在1的情況重復上述①②步驟。

若2在右側，則2替代3的位置，繼續討論1、2之間是否存在1的情況重復上述①②步驟。

①②得出規律推廣到普遍情況。

①……若P1,Pn之間存在與P1、Pn相異的顏色，且全部為A型設為Pm，將左右側的封閉區域分別用P1,Pn的顏色為所有B型，重新涂色（引理1），保證兩側封閉區域內的Pm顏色均為A型，同時用如下方式將兩端點顏色替換為P1或Pn：若最內圈B類國家與端點同色，則端點顏色即為P1或Pn保持不變。若最內圈B類國家與端點異色，則將端點替換為輪換顏色（原則5）例如若P1與2異色，則將2替換為Pn。再用4與Pm顏色互換。

②……若P1,Pn之間不存在與P1、Pn相異的顏色，則該相異顏色必在兩側封閉區域內，根據引理1再次將兩側所有B型重新涂色（用P1、Pn的顏色），這時Pm如果仍存在那么一定是A型，同時用如下方式將兩端點顏色替換為P1或Pn：若最內圈B類國家與端點同色，則端點顏色即為P1或Pn保持不變。若最內圈B類國家與端點異色，則將端點替換為輪換顏色（原則5）例如若P1與2異色，則將2替換為Pn。用4與Pm，顏色互換即可，反之如果已經不存在Pm，那說明Pm已經被P1或Pn顏色取代，同時用如下方式將兩端點顏色替換為P1或Pn：若最內圈B類國家與端點同色，則端點顏色即為P1或Pn保持不變。若最內圈B類國家與端點異色，則將端點替換為輪換顏色（原則5）例如若P1與2異色，則將2替換為Pn。那么“不得不用4”的前提已經不存在。

若P1、Pn之間存在P1、Pn相異的顏色，且有B型，設為Pm，若Pm位于左側，則Pm、Pn取代之前的P1、Pn，若Pm位于右側，則P1、Pm取代之間的P1、Pn，重復之前的操作，直至出現①或②的情況。

若最后仍未出現①②的情況，則如圖9根據引理1左側所有B型用Pn、Pm的顏色重新染色，右側用Pm、Pn顏色重新顏色，這時P1顏色的B型全部被替代，同時用如下方式將兩端點顏色替換為Pm或Pn：若最內圈B類國家與端點同色，則端點顏色即為Pm或Pn保持不變。若最內圈B類國家與端點異色，則將端點替換為輪換顏色（原則5）例如若Pm與2異色，則將2替換為Pn。將4與P1顏色替代即可。

以上證明是以二段邊界，并且二段邊界分布在端點兩側的情況作為范例代表所有B類國家，至于二段邊界完全在兩端點之內，或者擁有三段以上邊界分布在端點兩側，并且有兩段以上位于兩端點之內的情況，同樣可將位于端點之內的二段之間的封閉區域，視作獨立于整體之外的部分，先當作“消失”待完成了二段邊界的著色，再探討內部即可。如下：

先將3的封閉區域視作“消失”，簡單當3的整體國家，按照上述步驟證明后，再二次對3內部二次染色即可（原則5）

先將3的左側封閉區域視作“消失”，當作3的二段B類國家，按照之前的方法證明后，再一次對陰影區域涂色。

以上證明，若將兩端點換為同色，同理可以得到相同結果。

綜上，一旦板塊最外圈顏色數達到4，永遠都可以通過變換，將板塊最外圈顏色數重新降為3，亦即板塊可以以任何一種方式無限擴展，這對應了已知的和未知的所有地圖。

作者：黨珅