[原创]顶独立集、完全同态与四色问题

雷明85639720

[watermark]
          顶独立集、完全同态与四色问题
                    雷  明
             （二○一○年元月六日）
摘  要：从图的顶独立集，完全同态，顶点着色三者的关系出发，证明了四色猜测是正确的。
关键词：四色问题  四色猜测  着色  着色数  平面图  正则图   极大图  完全图  线图  全图  图的密度  图的最大度  划归  顶独立集  顶独立集数  最小顶独立集数  同化  完全同态  最小完全同态  最小完全同态的顶点数  
    1、图的顶独立集、完全同态与顶点着色的关系：
    不相邻的顶点可以划归到同一个顶独立集内，而相邻顶点则不可划归到同一个顶独立集内；不相邻的顶点可以同化为同一顶点，而相邻顶点则不可同化为同一顶点；不相邻的顶点可以着以相同颜色，而相邻顶点则不可着同一颜色。可以看出，图的最小顶独立集数β、最小完全同态的顶点数α与图顶点着色的色数γ是相等的。即有
        γ＝β＝α                                                              （1）
的关系。
    2、图的最小完全同态的顶点数与密度的关系：
    若图的顶点数是v，密度是ω，显然其最小完全同态的顶点数的宽界是
    ω≤α≤v                                    （2）
也可以证明，其窄界是
        ω≤α≤<1.5ω>                           （3）
（注：<  >表示其中的数字向下取整，下同——笔者）
其证明方法见笔者有关用图论方法证明四色猜测的论文。同理也有
        ω≤β≤v                                 （4）
        ω≤β≤<1.5ω>                            （5）
        ω≤γ≤v                                 （6）
        ω≤γ≤<1.5ω>                            （7）
公式（7）就是任意图顶点着色色数与其密度的关系。也是任意图顶点着色色数的界。
    3、平面图顶点着色色数的界：
    平面图的密度ω小于等于4，把ω＝1、2、3、4公别代入到（7）式中去，得到在ω＝1、2、3时的色数γ都小于等于4，而ω＝4时，有4≤γ≤6，色数γ有三种，即4，5，6三种，但也可以证明，当γ＝5或6时，图就不是平面图了，而是一个非平面图。所以有
        γ平面图≤4                                （8）
    4、平面图四色猜测是正确的：
    从公式（8）可以看出，任何平面图顶点着色的色数都是小于等于4的，这就说明了平面图的四色猜测是正确的。也就是说，任何平面图顶点着色时，最多四种颜色就够用了。
   
    5、地图四色猜测也是正确的：
    地图本身就是一个3—正则的平面图，其对偶图则是一个极大的平面图。给地图面上的着色，就相当于给平面图顶点的着色。平面图顶点着色时四种颜色够用了，那么地图着色时四种颜色也一定够用了。地图四色猜测也得到了证明是正确的。
    6、四色猜测还可以这样证明（又一证明方法）：
从公式（1）知道γ＝α，若某个图的色数是γ时，则它的最小完全同态一定是一个顶点数是α＝γ的完全图Kγ（或Kα），那么现在只要能证明平面图的最小完全同态的顶点数α≤4，就能够说明四色猜测是正确的。
    完全图的顶点数v与其边数e的关系是
        e＝v(v－1)/2                               （9）
按照库拉图斯基定理，平面图的边数e最大只可能是
        e＝3v－6                                   （10）
令公式（9）和公式（10）相等，则有
        3v－6＝v(v－1)/2
        6v－12＝v（v－1）
        6v－12＝v2－v
        v2－7 v＋12＝0
解该一元二次方程
        Δ＝（－7）2－4×12＝49－48＝1
        v1＝(－(－7)＋1)/2＝4
        v2＝(－(－7)＋1)/2＝3
两个根均不大于4，说明既是完全图，又是平面图的图的顶点数只有3和4两种，即K3和K4；另外还有完全图K2和K1虽不是极大图，但也是平面图；这四种完全图的顶点数v都是小于等于4的。这也就说明了任何平面图的最小完全同态的顶点数总是小于等于4的。这也就证明了平面图的四色猜测是正确的，同理，也证明了地图的四色猜测也是正确的。
    7、图的线色数和全色数的界：
    有了公式（7），就可以求出任意图的线色数和全色数的界。线图的密度ω线图就是原图最大度Δ，即ω线图＝Δ；全图的密度ω全图比原图的最大度Δ大1，即ω全图＝Δ＋1。把ω线图＝Δ和ω全图＝Δ＋1分别代入公式（7），即可得到图的线色数和全色数的界分别是
        Δ≤γ线≤<1.5 Δ>                          （11）
        Δ＋1≤γ全≤<1.5( Δ＋1)>                  （12）
8、结论：
    四色猜测是正确的。
    从图的最小完全同态与密度之间的关系，可以得到图的线色数和全色数的界的正确表达式。说明了1964年由V&#8226;G&#8226;Vizing给出的线色数的界Δ≤γ线≤Δ＋1和1965由Behzad给出的全色数的界γ全≤Δ＋2是不正确的，至少是不完全的。
                                         雷  明
                                二○一○年元月六日于长安
[/watermark]

想尔

楼主对四色的痴迷，小弟佩服！
不过实在看不懂你讲的内容，可能这是你的简化版，一些具体的概念都没有讲，比如
顶独立集  顶独立集数  最小顶独立集数等，能不能具体一些说说

雷明85639720

想尔：你好。
   你可以看一看有关的图论书，对图论的专业术语了解一下。我也是一个门外汉。顶独立集就是把图中不相邻的顶点划归为同一个集合内，这个集合就是顶独立集，因为该集合内的所有顶点在图中都是不相邻的。我的文章中的最小顶独立集数，是与图论中的最小独立集数是不同的概念。最小顶独立集数是一个图所能划分的最少的独立集的个数；而最小顶独立数则是所有顶独立集中具有最少顶点的独立集中的顶点的个数。这样解释不知你能不能明白。雷明。2010，2，22。