极大平面图中待着色顶点的按需换位着色法》

晋源泉

《极大平面图中待着色顶点的按需换位着色法》

一、极大平面图中点着色发生的颜色冲突构形：
1、在极大平面图中对所有顶点进行着色时，根据四色猜测最多４种颜色就可完成。但是，由于其有解和无解都不是一个唯一的。着色过程中往往是除某顶点或面外的顶点或面都有了正确的着色，对这个某顶点或面需要着上４种颜色之一而又无法完成的情况经常发生，这种情况就叫颜色冲突或困局，其极大平面图叫颜色冲突构形。
2、极大平面图中所有顶点都可正确的用4种颜色着色的图叫可4—点着色的极大平面图。所有顶点都没有进行着色的极大平面图叫裸图。
3、我们把构形中有颜色冲突的某顶点叫作待着色顶点，用V（Ｖ１、Ｖ２）表示；其周围的顶点叫作围栏顶点，分别用A、B、C、D表示其已经着上颜色的顶点。颜色冲突构形中Ｖ、Ｖ１、Ｖ２的围栏顶点组成的环叫构形内环，构形内环及内部区叫冲突区。Ｖ、Ｖ１、Ｖ２可着上４色之一的所在区叫非冲突区，简称区。颜色冲突构形中最外围的顶点组成的环叫构形外环。内环、外环、及其之间的环，都是指以V为圆心的线和顶点构成的环。
二、在可4-点着色极大平面图中的区的种类：
在极大平面图中，所有顶点已经用A、B、C、D　４种颜色可4-点着色时， 按排列组合有A、B、C、D　４类２４种区。即：V已着上其四色之一时，另三色、二色构成其围栏。
三、极大平面图中各类区的数量分配律：
在极大平面图中，所有顶点对A、B、C、D　４类区的数量按整数平均进行分配，差值大小等于０、1、2的其一。
四、极大平面图中冲突区的种类：
１、在5度颜色冲突区中，围栏顶点已经按顺时针排列的顺序用尽了A、B、C、D、B四种颜色， V无法着上其4色之一。两个Ｂ顶点是构形的同色顶点、Ａ是构形中两个同色顶点之间的一个顶点，C、D是构形中两个同色顶点之间的二个顶点。此处只列举了5度颜色冲突区的其中一种类型。但这一种类型即可代表A、B、C、D  4种颜色组成的5度颜色冲突区为A、B、C、D　４类２４种。
２、在4度颜色冲突区中，围栏顶点已经按顺时针排列的顺序用尽了A、B、C、D  4种颜色，并且没有同色顶点，V无法直接着上其4种颜色之一。这一种类型即可代表A、B、C、D四种颜色组成的４度颜色冲突区为A、B、C、D　４类２４种。
四、冲突区对极大平面图的可４－点着色的影响：
（一）极大平面图着色中冲突区发生的原因：平面图可4—点着色时，所有顶点的周围顶点所着的颜色的数量有n等于3、n等于2、有n等于3和有的n等于2，顶点之间属一种平衡状态，每一种颜色着多少个顶点都是有定数的法则……各类区的数量分配律。当顶点之间的平衡状态被破坏时，每一种颜色着多少个顶点的定数就乱套，顶点之间就要发生颜色冲突。所以，颜色冲突的解就是恢复顶点之间的平衡状态，使冲突区向区的转换。
（二）极大平面图着色中冲突区向区的转换方法：
冲突区向区的转换方法有好多种，至于那种方法比较好？这就得由学习、使用、研究等人员的情况而自己决定了。
这里介绍一种冲突区向区的转换方法……《待着色顶点的按需换位着色法》。或者叫一种颜色冲突的处理技术。
颜色冲突区中的待着色顶点V按其在所在区的需要，通过数次和其已经正确着色的各次冲突区围栏中的顶点交换位置，V在新位置得到正确的着色，恢复了所有顶点之间的平衡状态而使冲突区转换为区。
1、在构形内环上C、D顶点可以换位：
如果构形内环上C、D顶点交换位置后，C、D顶点在新位置和其他顶点不发生颜色冲突。在构形内环上作如下操作：V和两个B换位后，Ｖ分别变为V1、V２。V1、V2分别再按自己的新困局之需与其新内环上的只着了一种颜色的单个顶点换位着色，直至构形有解。
２、在构形内环上C、D顶点不可以换位。但是，C、D中有一个低度顶点。
如果构形内环上C、D顶点交换位置后，C、D顶点在新位置和其他顶点发生了颜色冲突。但是，C、D中有一个低度顶点。
在构形内环上作如下操作：V和C（D）低度顶点换位，Ｖ再和其相邻的B换位。Ｖ再按新困局之需与其新内环上的只着了一种颜色的单个顶点换位着色，直至构形有解。
３、在构形内环上C、D顶点不可以换位。C、D是等度顶点，而且，C、D又不是构形内外环的公共顶点。
如果构形内环上C、D顶点交换位置后，C、D顶点在新位置和其他顶点发生了颜色冲突。虽然C、D是等度顶点，但是，C、D不是构形内外环的公共顶点。
在构形内环上作如下操作： V和C（D）换位。V再按新困局之需与其新内环上的只着了一种颜色的单个顶点换位着色，直至构形有解。
４、在构形内环上C、D顶点不可以换位。C、D是等度顶点，而且，C、D是构形内外环的公共顶点。
构形内环上C、D顶点如果交换位置后，C、D顶点在新位置和其他顶点发生了颜色冲突。虽然C、D是等度顶点，但是，C、D是构形内外环的公共顶点。
在构形内环上作如下操作：V和A换位。V再按新困局之需与其
５、在4度颜色冲突构形中，围栏顶点已经按顺时针排列的顺序用尽了A、B、C、D四种颜色，并且没有同色顶点，V无法直接着上其四种颜色之一。
在构形内环上作如下操作：V和A、B、C、D之一换位。V再按新困局之需与其新内环上的只着了一种颜色的单个顶点换位着色，直至构形有解。
6、 直至构形有解的换位着色次数：小于等于3+内外环之间的环数。