如何在一个极大平面图中构造指定度数的顶点

雷明85639720

如何在一个极大平面图中构造指定度数的顶点
雷  明
（二○二一年七月二十七日）
四色问题由给地图的染色而提出，研究四色问题还得从地图开始着手。地图是一个含有“无顶环”（即“国中之国”）的、无割边的、连通的3—正则平面图，其对偶图则是一个带有悬挂顶点的、极大平面图。给地图的面上的染色就是对其对偶图的顶点着色。极大平面图的四色猜测是正确的了，当然地图的四色猜测也就是正确的了。而对极大平面图经增、减顶点或边而得到的任意平面图的色数，只会减少而不会再增加，所以任意平面图的四色猜测也就是正确的了。我们这篇文章里所要研究的问题，就是如何构造含有指定度数的顶点的极大平面图。
    首先作一个最简单的极大平面图（如图1）K3，分别着A、B、C三色。这是只有三个区域的地图的对偶图。如海地岛的地图。海地岛上有海地和多米尼加两个国家，第三个区域则是海洋。在这个图的基础上，再增加顶点，且要保证图仍然是地图的对偶图——极大图。
1、作一个1—度的顶点：
在图1的这个极大图的某一个顶点（如B点）上增加一个一度的顶点V（如图2），顶点V有三种颜色可着，这里着了A。这个V就是“国中之国”的地图的对偶图。如非洲的莱索托的地图，只与南非一个国家相邻。这里是增加了一个顶点和一条边。
2、作一个2—度的顶点：
在图2的基础上，在某条边（如A—C边）上增加一个顶点，就是一个2—度的顶点V（如图3），顶点V仍有两种颜色可着，这里也着了A。再在顶点A与顶点C之间作两条平行边，这就是“两国夹国”的地图的对偶图。如蒙古国的地图，只与中国和俄罗斯两个国家相邻。这里是增加了一个顶点和两条边。


3、作一个3—度的顶点：
在图3的基础上，再在某一个面（如ABC三角形面）内增加一个顶点V，就是一个3—度的顶点（如图4），顶点V还有一种颜色D可着。这就是“三国环国”的地图的对偶图。如我国的宁夏回族自治州，与陕西省，内蒙古自治州和甘肃省三个省区相邻。这里是增加了一个顶点和三条边。
4、作一个4—度的顶点：
作4—度顶点至少要在由两个以上三角形面构成的极大图（如图5）之内的一条边上进行。在四边形ABCD的对角线AC上增加一个顶点V，就是一个4—度顶点（如图6）。这是“四国环国”的地图的对偶图。如我国的青海省和山西省，都是“四国环国”型的区域。当V的围栏顶点所用颜色数小于4时，V是可以直接着色的；当V的围栏顶点所用颜色数等于4时，坎泊早已解决了其着色的问题，V总是可以着上四种颜色之一的。也是增加了一个顶点和三条边。

5、作一个5—度的顶点：
作5—度顶点同样也至少要在由两个以上三角形面构成的极大图内进行，且是在一个由3个三角形面构成的五边形内进行（如图7）。把五边形内的两条对角线去掉后，便是一个五边形（如图8），再在其中增加一个顶点V，就是一个5—度顶点（如图9）。这是“五国环国”的地图的对偶图。如我国的贵州省和重庆市，都是“五国环国”型的区域。当V的围栏顶点所用颜色数小于4时，V也是可以直接着色的；当V的围栏顶点所用颜色数等于4时，可以用待着色顶点移动法，把待着色顶点V移动到度是小于等于4的顶点上去，再给V直接着色或采用坎泊的颜色交换技术给4—度待着色顶点V着色。这里也是增加了一个顶点和三条边。
6、作一个6—度的顶点：
作6—度顶点同样也至少要在由两个以上三角形面构成的极大图内进行，且是在一个由4个三角形面构成的六边形内进行（如图10）。把六边形内的三条对角线去掉后，便是一个六边形（如图11），再在其中增加一个顶点V，就是一个6—度顶点（如图12）。这是“六国环国”的地图的对偶图。如我国的湖南省、江西省、湖北省、河南省和安徽省等，都是“六国环国”型的区域。当V的围栏顶点所用颜色数小于4时，V也是可以直接着色的；当V的围栏顶点所用颜色数等于4时，也可以用待着色顶点移动法，把待着色顶点V移动到度是小于等于4的顶点上去，再给V直接着色或采用坎泊的颜色交换技术给4—度待着色顶点V着色。也是增加了一个顶点和三条边。

7、作一个n—度顶点：
根据以上的作图，可知当要作一个n—度顶点时，必须是在一个由n－2个三角形面构成的n—边形内去掉了全部的n－3条对角线（边）后才能进行。在n—边形内增加一个顶点V,就是一个n—度顶点。增加的顶点数仍是一个，增加的边数则也是n－（n－3）＝3条。当V的围栏顶点所用颜色数小于4时，当然也V可以直接着色的；当围栏顶点所用的颜色数等于4时，照样V也可以使用待着色顶点移动的方法，移动到度是小于等于4的顶点上去，再给V进行着色。看来，要顺利的完成构造指定度数的顶点，还必须在图中要有几个度是小于等于4的顶点，否则，构造的顶点的度在大于等于5时，还真的是无法着色的。

雷  明
二○二一年七月二十八日于长安

注：此文已于二○二一年七月二十八日在《中国博士网》上发表过，网址是：
http://www.chinaphd.com/cgi-bin/ ... pic=4424&show=0

朱明君

雷明85639720

我谈的是在极大平面图中构造指定度数的顶点。你看看你那些图是不是都是极大图呢？

朱明君

雷明85639720 发表于 2021-7-29 00:28
我谈的是在极大平面图中构造指定度数的顶点。你看看你那些图是不是都是极大图呢？

这是构成地图的最基本原素

雷明85639720

1、你只画几个图，且不是极大图，一句文字也没有，哪一个能知道你是在说什么呢？
2、你只是说“这是构成地图的最基本元素”，那你给其着色就没有什么意义了。所以我说，看不明白你是在说什么？
3、地图是一个“无割边的3—正则平面图”，其对偶图是一个极大图，而你所画的图根本就不是极大图，它能与地图有什么关系呢？
4、朋友，还是好好的把图论再学习一下吧！