Insert title here
左侧导航栏
  • 论坛声明:本帖由网友上传,只代表网友个人观点,转帖请注明作者及出处。

原创 简单平面图的色数为4(地图可4色)

  • 要科学
  • 等级:新手上路
  • 经验值:39
  • 积分:
  • 5
  • 14659
  • 2018-09-01 07:13:19

                               简单平面图的色数为4(地图可4色)

                                               (苏州大学  李金良)

   

   摘要:通过证明极大平面图(饱和平面图)的色数为4,进而推广为所有的简单平面图的色数为4

   (本文中的图,均指简单平面图。|V(G)|表示图G的阶,nsN。)

[定理1]:极大平面图(饱和平面图)的色数为4

(极大平面图(饱和平面图),指,顶点全部由边互相平面连满,其中的所有的面全部是三边形。)

[证明]:(归纳法)

   当|V(G)=4时,(如图-1

       

-1

   显然,色数为4

   假设,|V(G)= n 时,色数为4

   现需证明当|V(G)= n +1 时,色数亦为4

由于,n阶的图G ,是极大平面图(饱和平面图),其中所有的面全部是三边形,且4色。(如图-2


                                                                           -2

那么,在该n阶的图G 中,要增加一个顶点,“必然只能”把这个顶点放进任意的一个三边形中,并且只能和这个三边形中的三个顶点分别连接。(如图-3

                                                                     -3

由于,三边形的三个顶点已取且仅能取三种颜色,则,放入其中的新增顶点,自然,可取第4种颜色。

所以,|V(G)= n +1 时,图G的色数为4

[定理1] 得证。

[定理2]:简单平面图的色数为4(地图可4色)。

证明:

因为,任意一个s阶的简单平面图G,只需将图中没有连满的顶点,平面地用增加的边连满,就变成一个s阶的极大平面图(饱和平面图)。

即,将图中不是三边形的面,全部平面地用增加的边连接成三边形的面,所有的面都变成了三边形,即连成了极大平面图(饱和平面图)。

而,据[定理1] 可知,极大平面图(饱和平面图)的色数为4

则,上述s阶图G增加连边形成的s阶极大平面图(饱和平面图)的色数亦为4

那么,再倒过来,将增加的连边去掉,还原到原来的s阶的平面图G

由于,减少连边,并不会增加色数。

所以,减去连边后的原来的s阶平面图G依然色数为4

由此可知,简单平面图的色数为4(地图可4色)。

[定理2] 得证。


点赞


  • 分享到
    谢谢您的阅读, 您是本文第 14659 个阅览者

网友回复

定理1证明补充:

   

  当|V(G)= n +1 时,若增阶的顶点(不是在面上),而是在任意一条连边上,现需证明,图G的色数仍为4

增阶的顶点在边上,(如图-4):

  -4

具体连接,有三种形式(如图-567):

   -5

   -6

   -7

如图-5和如图-6的连接形式,由于新增顶点只和三个顶点连接,所以,新增顶点可以使用第4种颜色,所连接形成的n+1阶图G的色数为4

现在分析如图-7的连接形式:

将如图-7中原来的四个顶点分别标为abcd,因为ac原来是相连的,所以,ac这两个顶点必定颜色不同。

(一)、如果bd颜色相同,则,新增顶点所连的四个顶点总共只有3种颜色,所以,新增顶点可以取第四种颜色,所连接成的n+1阶图G的色数为4

(二)、现在分析bd颜色不同的情形:

1、若ac 之间连接有一条(ac两色交替的)双色路。(注:双色路,指,一条路上,由两种颜色的顶点交替连接。)(如图-8):

   -8

由于ac之间有一条ac两色交替的双色路,这条双色路将bd分开来,使得bd之间无法形成bd这两种颜色交替的双色路。

所以,b点变为d色,不会导致d点连动变为b色。

(说明:如果bd两点之间连有bd两色交替的双色路,则,b点变为d色,为了保持相邻两点异色,d点必须连动变为d色。由于现在没有,所以,b点变为d色后,d点不需要变色。)

这样,bd两点就能取同样的颜色。

abcd四个顶点总共就只有三种颜色了。

于是,新增的定点,只和三种颜色的顶点相连,自然可取第4种颜色。新增顶点后的图G的色数为4

2、若ac 之间没有连接一条(ac两种颜色交替的)双色路。

则,a变成c色,不会导致c点连动变成a色。

这样,a点和c点就能取相同的颜色。

同样,abcd四个顶点又总共只有三种颜色了。

于是,新增的顶点,又只和三种颜色的顶点相连,又自然可取第4种颜色。新增顶点后的图G的色数又为4

综上得知,新增顶点若增加在连边之上,所连成的n+1阶极大平面图(饱和平面图)G的色数也能为4

定理1的证明补充完毕。


(李金良)


    谢谢您的阅读, 您是本文第 14659 个阅览者


    谢谢您的阅读, 您是本文第 14659 个阅览者

更正一个字母:应该是“b”,误打成了“d”:

定理1证明补充中, 下划线上的第二个“d”,应该是“b”:

原句:

(说明:如果bd两点之间连有bd两色交替的双色路,则,b点变为d色,为了保持相邻两点异色,d点必须连动变为d。由于现在没有,所以,b点变为d色后,d点不需要变色。)

改为:

(说明:如果bd两点之间连有bd两色交替的双色路,则,b点变为d色,为了保持相邻两点异色,d点必须连动变为b。由于现在没有,所以,b点变为d色后,d点不需要变色。)

向各位老师、各位网友致歉!


    谢谢您的阅读, 您是本文第 14659 个阅览者

路过,看一看

    谢谢您的阅读, 您是本文第 14659 个阅览者

对这些字母还真有点不太会用。

    谢谢您的阅读, 您是本文第 14659 个阅览者
单张最大不超过1M!