如何求平面图的最小完全同态

雷明85639720

如何求平面图的最小完全同态
雷  明
（二○一六一六年四月十六日）

1、图的色数等于其最小完全同态的顶点数（哈拉里），平面图的色数也就等于其最小完全同态的顶点数。求平面图的最小完全同态，必须用图的“同化”运算方法。所谓同化，就是把图中不相邻的顶点凝结在一起，使其成为一个顶点。这在有些图论书中也叫“收缩”，但收缩在图论中有两种，不相邻的顶点可以收缩在一起，相邻的顶点也可以收缩在一起。我为了与相邻顶点的收缩相区别，所以我这里专用了同化一词。其实同化一词在聂祖安翻译的《图论的例和反例》一书中早就已经出现过。
2、有些平面图的最小完全同态与其最大团是相同的，如道路，树图，偶圈和偶轮，它们的最大团分别是K2和K3，而最小完全同态仍是K2和K3；也有些平面图的最小完全同态与其最大团是不同的，如寄圈和寄轮，最大团是分别是K2和K3，而最小完全同态却是K3和K4，最小完全同态的顶点数比最大团的顶点数多；但却没有最小完全同态的顶点数比最大团顶点数少的情况。
3、同一个图可能有不同的完全同态，如道路可以同化成K2，也可以同化成K3，他们都是道路的完全同态，但顶点数却不相同，把顶点数最少的一个叫最小完全同态。最小完全同态的每一个顶点都是由原图中不相邻的若干个顶点同化而来的，这些顶点着相同的颜色完全是能够符合着色要求的。所以说，图的最小完全同态的顶点数就是图的色数。
4、与图中某一个最大团KV中的顶点相邻的顶点最多只可能与最大团中的v－1个顶点相邻，否则图中的最大团就不是KV而是KV＋1了，所以最大团KV中总至少还有一个顶点可以让这个与其相邻的顶点同化上去。图中不与最大团相邻的顶点，当然也一定都是可以同化到最大团中去的。
5、图中与最大团不相邻的顶点，到最大团间一定有各种不同的道路存在。由于道路可以同化成K2，也可以同化成K3，所以一定在同化时要注意：不能把与最大团中某顶点间的道路是寄长的顶点向最大团中去同化，因为这样，有可能会增大最小完全同态的顶点数；而要把与最大团中某顶点间的道路是偶长的顶点向最大团中去同化。
6、一个图最终同化的结果，可能最小完全同态的顶点数会与其最大团的顶点数相同，也可能不同。这在同化之前就可根据图的结构特点确定下来。最大团是K4的图，最小完全同态的顶点数只能是4，而不会更大；最大团是K3的图，最小完全同态的顶点数是：当图中含有寄轮时是4，否则仍然是3；最大团是K2的图，最小完全同态的顶点数是：当图中含有寄圈时是3，否则仍然是2；当然了只有一个顶点的K1图，其最小完全同态只能是它自身了。
7、至于具体对某个平面图着色时，也倒不一定要求出其最小完全同态，只要判断出其色数（即最小完全同态的顶点数）是多少，就可以直接给图着色。在遇到某个顶点其周围顶点都着上颜色时，能给其直接着上颜色更好，不能直接通着上颜色时，可以使用坎泊的颜色交换技术，交换几次就可以空出颜色给其着上。
   
                         雷  明
二○一六年四月十六日于长安

注：此文已于二○一六年四月十日在《中国博士网》上发表过，网址是：

雷明85639720

，，，，，，，，

雷明85639720

........

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，