[原创]在图论大会上演讲的字幕

雷明85639720

[watermark]
在图论大会上演讲的字幕
雷  明
（二○一二年七月十七日下午）
第五届全国组合数学与图论大会于二○一二年七月十六日至十八日在洛阳师范学院如开，我与十七日下午4点45分至5点作了题为《任意图顶点着色色数的确定》的学术论文报告，正好不超过大会规定的十五分钟的时间。现把我的演讲稿的字幕整理于后。原文我用的字号是加粗了的黑体一号字，投影到幕布上时有碗口那么大，特别清晰，以便大家看得清。我的讲稿原件是将一幕一幕的文字拉开了很大的距离，以保证投影到屏幕上时，上下文是不会出现在屏幕布上的，这样会产生更好的效果。实中践也证明了这样的效果是很好的。
幕一
雷  明：
金堆城钼业公司（陕西华县）教育处处长，退体高级工程师，67岁
（按：这一幕我没有去读，而是说了以下的话。“我先说几个事：第一，首先我感谢学会邵理事长和大会筹备组给了我很大的面子，让我一个非数学界的人站在这里和大家进行学术交流，我感到非常的荣幸，也很高兴：第二，请大家不要翻看会议手册。不知是什么原因，会大会会务组唯独就把我一个人的论文摘要忘记打印到会议手册上去，我感到很遗憾。不过这不要紧，免得边听边看，看了听不见，影响听的效果。只要各位认真的听，效果会更会好；第三，我看了一下，在座的各位可能都没有我的年令大，尽管是这样，但大家都是我的老师，希望大家听了以后，多提宝贵意见。）
幕二
论文题目：任意图顶点着色色数的确定
（按：我在读了论文题目后说：会务组这里又把我的论文题目弄错了。）
幕三
图：由顶点与某些顶点间的连线（边）所构成的集合就是图。
    （按：为了与后面的几个概念的关键相呼应，我在读完这一版后加了一句：“两个有边相连的顶点叫相邻顶点。”）
幕四
图顶点着色：给图的顶点着以不同的颜色，关键是相邻顶点不能着同一颜色。图中所用的最少颜色数叫图顶点着色的色数，用γ表示。
幕五
顶独立集划分：把图的顶点划分到不同的集合内，关键是相邻顶点不能划分在同一个独立集内。所划分出的最少的独立集数叫最小顶独立集数，用β表示。
（按：我补充说了一句：“请注意，我这里的‘顶独立集数’的概念不同于图论中已有的‘顶独立数’的概念。”）
幕六
同化运算：把图中不相邻的顶点，凝结为一个顶点的过程叫同化，关键是相邻顶点不能同化为一个顶点。图顶点同化的最终结果是一个完全图，叫完全同态。其中顶点数最少的完全同态叫最小完全同态。最小完全同态的顶点数用α表示。
（按：在这里我说明了“同化”一词的来历：“‘同化’一词来自于聂祖安翻译的《图论的例和反例》一书，在那里同化就是指不相邻顶点凝结为一点的过程。”）
幕七
从以上三个概念可以看出：
图顶点着色色数γ
＝最小顶独立集数β
＝最小完全同态Kα的顶点数α
幕八
由于图中的最大团各顶点是互相相邻的，不可能进行同化，所以最小完全同态的顶点数α一定不会小于图的密度ω（图的密度就是图中最大团Kω的顶点数），所以又有
γ＝β＝α≥ω
（按：在这里我对图的密度进行了说明：“我这里的图和密度也是来原于聂祖安所翻译的《图论的例和反例》一书，那里说的图的密度就是指图中最大团的顶点数。”）
幕九
请看下面两图的同化。
（图见DOS文件中）

（按：在这里我先对两图进行了说明：“这是两个非具体的图。图中的虚线椭园表示图的某一个最大团Kω，上面有一条道路Pn。Pn中各顶点均与最大团Kω中相同的ω－2个顶点相邻，Pn中各顶点均不可再向这些顶点去同化，所以最大团中的这ω－2个顶点及其与Pn道路中各顶点相邻的边均没有画出来。而Pn道路的两个端点顶点又分别与最大团Kω中除了那ω－2个顶点外的另一个K2团的两个顶点相邻。我们把以上这种道路叫做饱和道路。因为若再在Pn道路与最大团Kω间任增加一条边时，图的密度就会变成ω＋1，或者就会把Pn道路分成两条与以上所说道路具有相同情况的道路，只是道路变短了而已。）
幕十
图1 中当n为奇数时，Pn中总有一个顶点同化不到最大团Kω中去，且Pn中的任何一个顶点都可有相同的机会成为这样的不可同化顶点；否则n为偶数时，Pn中的顶点则可全部同化到最大团Kω中去。
幕十一

图2中当n为偶数时，Pn中也总有一个顶点同化不到最大团Kω中去，且Pn中的任何一个顶点都可有相同的机会成为这样的不可同化顶点；否则n为奇数时，Pn中的顶点也可全部同化到最大团Kω中去。
幕十二
    道路的分类：
道路：1、普通道路
2、饱和道路：道路与最大团间再增加任一条边时图的密度就会发生变化。
饱和道路：
1、可同化道路
2、不可同化道路：道路中总有一个顶点同化不到最大团中去。
幕十三
可以证明，当不可同化道路是回路（圈）时，同样也有与以上两图的两种情况下相同的结论。
幕十四
如果有S条不可同化道路，且构成了联时,就有S个顶点同化不到最大团中去，这S个顶点因其本来就是相邻的也不可再同化在一起，所以有α＝ω＋S。
幕十五
若道路间没有构成联时，各道路间总有互不相邻的顶点，把这样的顶点作为不可同化顶点，最后再将其同化成一个顶点，实际仍然只有一个顶点没有同化到最大团中去，相当于只有一条不可同化道路的情况。
幕十六
由于联的密度是构成联的各图密度的和，（按：我多说明了一句：“由于各条道路的密度都是2”）,所以又有2S≤ω,即S≤ω/2，因为S必须是整数，所以还要向下取整，即又有
      S≤＜ω/2＞
因此有图的最小完全同态的顶点数的界是：
ω≤α≤＜1.5ω＞
幕十七
因此又有
ω≤γ＝β＝α≤＜1.5ω＞

所以说任意图的色数的界是
ω≤γ≤＜1.5ω＞

    （按：这里我应该再补充一句：“看来图的色数只与图的密度有关，而与图的顶点数是无关的。”）
由于平面图的密度都不大于4，所以这就使得对于密度来说的无穷问题就变成了一个有穷的问题了。
幕十八
把平面图的密度从1 到4 一个个的代入到以上的任意图色数的界中得：平面图的色数都不会大于4，即
            γ平面图≤4
幕十九
这里要说明的是，色数大于4 、密度是4 的图已不再是平面图了，所以就有γ平面图≤4，画一下图就能说明这一事实。
（按：我在这里补充说：“画一个K4图，在其外再画一条饱和道路，就可以看出图中已出现了交叉边；也可以用平面图的边数e≤3v－6进行推导检验，的确它的边数是大于3v－6的。）
这就证明了四色猜测是正确的。
幕二十
奇圈中对于每一个K2团都有一条不可同化道路，所以奇圈的密度虽是2,但奇圈的色数却是3；同样的，奇轮中对于每一个K3团都有一条不可同化道路，所以奇轮的密度虽是3,但奇轮的色数却是4。
幕二十一
有了任意图顶点着色色数的界，研究图的线色数、全色数及图的任何图值函数的色数就方便多了。
幕二十二
比如线图的密度等于原图中的最大度Δ，所以图的线色数的界就是
        Δ≤γ线≤＜1.5Δ＞
1964年V•G•Vizing给出的线色数的界是Δ≤γ线≤Δ＋1，我们这里要比Vizing的准确。
幕二十三
又比如全图的密度等于原图中的最大度加1,所以图的全色数的界就是
Δ＋1≤γ全≤＜1.5（Δ＋1）＞
1965年Behzad提出的全色数的猜想是γ线≤Δ＋2，我们这里也要比Behzad的准确。
（按：我在这里加了以下的话：“这里我要多说一点。上午我在C分会场听了一个报告，是关于全着色的问题的，由于我不懂英语，所以我也不知道最后道底得到了什么结论。但我能听出他介绍了多个验证Δ＋1≤γ线≤Δ＋2的进展。在什么情况下Δ等于几时，Δ＋1≤γ线≤Δ＋2是成立的，正确的。我就不明白，为什么要无休止的去对Δ进行验证呢，Δ可以早任意大的值，什么时间能验证完呢，什么是时间Behzad提出的全色数的猜想才能被证明是正确还是不正确呢。我们已给知道线色数就是线图顶点着色的色数，线图的密度就是原图的最大度，全色数就是全图顶点着色的色数，那么为什么不只去认真的研究图顶点着色的色数与图的密度的关系呢，为什么不去研究一般的图，而要一个个的研究特殊的、具体的图呢。请大家考滤这一意见。）
    谢谢。
    （注：我报告时，除了字号大以外，我还有以下三个特点：1、声大，不只让自已见得见，而主要是要听众听得见；2、我不是背向听众，而是面向听众，与大伙在聊天；3、我不是在念稿，而是在演讲。我的字大，声宏，与听众面对面，有声有色，有动作，有表情，能吸引听众，所以我所看到的听众的表情是不一样的，他们是在认真的听我的演讲，他们的认真听讲也激起了我更加要讲好。报告束在返回驻地的路上，有某大水的某教授赶了上来，送给我一张名片，表示会后愿意给我介绍专家看我的论文，给我以极大的支持。我至少感到今天的报告还是有收获的。）
雷  明
二○一二年七月二十日整理

任在深

啊！
   人如其名呀！
   雷鸣---------------------声音大，洪亮！

            预祝心想事成！