如何在理论上解释「四色定理」?(理性情绪治疗理论名词解释)


首先考虑对一个给定的图 G,对他的点进行染色,使得任意一条边的两个顶点不同色。我们把满足条件的最小的所需颜色数目叫做 chromatic number,记为

同时我们把图 G 中包含的最大完全图子图的点的数目叫做 clique number,记为

。很容易发现,一个 n 个点的完全图由于点两两相邻,至少需要 n 种不同的颜色。于是我们有如下结论:

Simple Observation:

由于我们更关心染色数的上界,到这里我们就会问,有没有

?很遗憾。。

Naive Conjecture:
Answer: False !

我认为百分之 80 的民科的证明就错在这里了:如果一个图不包含

即五个点的完全图为子图,不能得出这个图可以用四种颜色染色。

这里给一个例子:如下图考虑

,该图不包含

,因此

,但是

那么 chromatic number 能不能被 clique number 控制住呢?

Advanced Conjecture:
Answer (by Erdos, 1959): False !

实际上 Erdos 构造了 clique number 固定,但 chromatic number 任意大的图(Erdos-Renyi Graph)。也就是说在四色定理的证明中,试图从图中包含的完全子图的大小来讨论,是行不通的。更一般的,我们把满足

的图(并且所有 induced 子图也满足)叫做 perfect graph。对于这种图我们有更精细的结构:定义如果一个图 G 不包含长度大于 5 的 odd cycle 和它的 complement,我们称这个图 Berge。

Strong Perfect Graph Theorem (Chudnovsky, Robertson, Seymour, Thomas):

现在我们从 structure graph theory 的角度去看四色定理。delete an edge 指对 G 删去给定的边,contract an edge 指的是“商”去给定的边:将这条边的两个点粘合成一个并且保持所有和其他点的相邻关系(如下图)

如果图 H 可以通过对 G deleting 和 contracting 一些边得到,我们就说 H 是 G 的 minor。可以发现 minor 关系是包含子图这个关系的推广:H 是 G 的子图,那么 H 也是 G 的 minor。

Graph Minor Theorem(Robertson, Seymour):

上面深刻的定理同时告诉我们,当图 G 对于给定的图 H minor-free 时,具有清晰的结构。具体定理的叙述太长这里就不说了,目前这个图结构引理的最新证明由 Kawarabayashi, Thomas, Wollen 在 2016 年简化到了 100 页以内。图的结构问题是图论中最困难的问题之一,有了图的结构,我们就可以考虑图上的染色问题了。比如对于一个没有

minor 的图,我们有 Wagner's Theorem,即 G 是由 planar graphs 和

经过 clique sum of order at most 3 得到的(如图),其中

指的是 8 个点的 cycle 再连上对径点。

严格的说上图是 H minor-free 的图,里面的漩涡是 vortices。不过如果忽略漩涡,把洞当作

,还是可以看作是

minor-free 的图示的。

上面讲的 structure 内容看似和四色定理没什么关系。再让我们回到最开始举的

反例上:我们给它的 5 个点编号 1 到 5,如果我们 contract 边 12 和边 34,我们得到了

,也就是说

的 minor。这看起来也解释了

不能被

控制这个看似矛盾的现象:对于一个图 G,如果

是它的 minor,说明图 G 中有 t 个不相交的子集,分别 contract 掉它们我们可以得到

。那么对于那些子集,如果对所有子集我们首尾的点染色相同,那我们相当于在对

染色;否则我们就要求子集的首尾染色不同,相当于多了限制条件。换句话说,就算图 G 连

都不包含,但是如果它有

minor,那么有可能这个图需要至少 t 种不同的颜色。

很自然的,我们可以提出下面图论中最深刻的猜想:

Hadwiger's Conjecture:

配合 planar graph 的经典定理:

Kuratowski's Theorem:

我们可以发现,四色定理实际上是 Hadwiger's Conjecture 的 t=4 时的特殊情况。目前对这个猜想的进展如下:

Trivial

Hadwiger, 1943

By computer, 1976 (即 四色定理)

Robertson, Seymour, Thomas, 1993

Open

注意到 Robertson, Seymour and Thomas 对 t=5 情形的证明没有用电脑,但是用到了四色定理的结论。如果有一天有人可以证明 Hadwiger's Conjecture,绝对是组合数学里面最大的新闻了。目前这个猜想大家都认为是对的,但是我们目前的工具不够深刻。

做为结束,还是回到四色定理。四色定理有没有不依赖计算机的证明?答案是没有,不过目前已经可以通过计算机在 10 秒内证完了。如果得到了四色定理不依赖计算机的证明,对 Hadwiger's Conjecture 绝对是巨大的推进,发个四大不是问题。

线粒体是怎么产生的?(线粒体由什么产生)
上一篇
动物会感到疼痛吗?(动物疼痛表现)
下一篇
本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。

相关推荐

  • 苹果手机各个功能介绍,iphone必须关闭的十个功能

    1、关闭蓝牙。现在已经很少有人用蓝牙传输文件了,而且iPhone与安卓的蓝牙并不兼容,所以,可以在设置中,关闭蓝牙功能。2、关闭通知功能。关于APP推送,无非也就是一些更新提醒,关了也不会有什么影响,还能多省点电。3、关闭自动调节亮度功能。一般来说,可以将屏幕亮度在15%-30%之间,在强光环境中,在进行手动调整就可以了。4、禁止后台刷新。在设置—通用中,关闭后台自动刷新功能,也可以对省电起到一点...

  • 高德打车怎么设置途经地,高德如何添加途经路线

    1、点击高德地图APP界面底部的“导航”按钮,进入导航模式。2、点击右下角的“路线”,进入路线设定页面,根据要求输入起点、终点进行路线规划。3、点击“添加途经点”,弹出添加途经点页面,点击右上角,可以添加或者删除途经点,乘客可以手动输入要添加的途经点。4、当添加完途经点时,点击“确定”按钮,即可添加途经路线。此时地图会显示出这条路线上所有的途经点,以及当前途经点的地点信息。怎么设计高德地图设置要经...

  • 高中必修二物理知识点总结,高一物理必修2重点知识点归纳

    您好,1.运动学-位移、速度、加速度的概念及计算方法-相关运动的分析方法,如相对运动和抛体运动-牛顿运动定律及其应用2.力学-力的概念及种类,如重力、弹力、摩擦力等-牛顿第一、二、三定律及其应用-力的合成与分解-能量、功、动能定理、功率的概念及计算方法-动量、冲量定理及其应用3.热学-温度、热量、热能的概念及计量单位-热传递的方式及其特点,如传导、对流、辐射-热力学第一、二定律及其应用,如热机效率...

  • 线粒体是怎么产生的?(线粒体是怎样产生能量)

    关于线粒体的起源,科学家提出了两种不同的假说——内共生起源和非共生起源。顾名思义,内共生是真核细胞的祖先和它吞噬掉的原始细菌一起共生演化。相较于非共生起源,佐证内共生起源的结果更多一些。但是,在内共生...

  • 有没有可能,氧气是种慢性毒气,通常需要 70-100 年来杀死人类?

    不要贩卖“脱离剂量谈毒性都是耍流氓”的老梗了,让老夫上干货:是的,氧气确实有毒,特定条件下不是慢慢杀人,而且会迅速要命,还曾经差点灭光地球生物!待本文细细道来。1) 生命为什么一定需要氧气?真要这么问...