摘要：完美图，指的是用尽可能有限的一组颜色着色的网络图。在给图表着色时，每一个处于相互之间密集联系的“团”内的节点都必须被指定一个独一无二的颜色。而至今为止，关于如何处理方形结构的着色，仍然没有得到解决。
四年前，数学家Maria Chudnovsky 遭遇到一个常见困境：如何给120名参加婚礼的客人安排好座位,在所有客人中有可能存在矛盾，问题的关键在于如何避免将有矛盾的客人安排在同一张桌子前就座。很幸运，这个问题恰巧在她的研究领域内。Maria把客人视作网络中的节点，用线将“不相容”的节点间连接在一起。问题于是转化为：用一系列不同颜色来代表不同餐桌，再将节点分别着色。只要毗邻节点保证不同色，婚宴中便不会出现尴尬事件。
无论是节点还是参加同一场婚礼的客人，他们在数学家眼中都可以看做是位于同一网络中的、相联系的事物。图表的着色是一个被广泛研究的课题，目的就是把这些事物分割成没有矛盾的集合。由于节点内部的复杂联系，大部分网络很难用有限的颜色组合完成着色。网络规模越大，需要的颜色越多。从一个节点到另一节点，不停的变化颜色组合，最终你会陷入一种“交通堵塞”，迫使你选择更多新的颜色。同理，在现实世界中，座位表、时间表和运输路线安排鲜有最优解决方案。自从1960年起，数学家们就已经通过所谓“完美图”(perfect graph)避免了着色难题。普林斯顿大学一位38岁的数学教授Chudnovsky称：“完美图非常适用于着色难题。”
根据其定义，完美图指的是用尽可能有限的一组颜色着色的网络图。在给图表着色时，每一个处于相互之间密集联系的“团”（cliques）内的节点都必须被指定一个独一无二的颜色，所以任何一个网络都至少需要与其规模最大的“团”里的节点同等数量的颜色。在大部分网络中，你需要的颜色甚至比这个更多。但是在完美图表中情况则不同。正如法国图论领域理论家Claude Berge 在1961年所定义的：完美图表所需颜色的数量与其最大“团”的规模大小一致。颜色数量（chromatic number）必须与“团数量”（clique number）完全相等，因为完美图表的每个子集都是通过删除它的一些节点完成的。诸如此类的完美在现实世界鲜有出现，但是它的特殊属性使得完美图比其他非完美图更易于分析和证明定理。
然而在半个世纪之后，关于完美图一个显而易见的问题仍旧无人作答：究竟该如何为完美图着色？普林斯顿大学另外一位图论理论家Paul Seymour认为：“完美图是为着色而生的结构图，不知道如何为其着色是非常恼人的一件事。对于一个数学家，类似问题令人着魔，每一个数学家都渴望解决完美图的着色问题。”
现在， Chudnovsky 和她的合作者在为完美图着色的理论方面取得了显著的进步。Alan Tucker，石溪大学（Stony Brook University）的数学家表示：在过去的几年里，他们已经“啃掉了馅饼的不同部分”，证明了完美图里大型子集的着色理论。今年10月份，Chudnovsky和她的合作者（Irene Lo,Frédéric Maffray, Nicolas Trotignon and Kristina Vušković）一起发布一个完美图的着色理论，该理论中的完美图表不包括由四个节点组合的方形结构（Square）。Gérard Cornuéjols，卡内基梅隆大学（CarnegieMellon University）的数学家表示：“这个理论解决了一些常见的问题。”
希望历史能够重演。15年前，研究人员争相证明完美图的着色定理。在Cornuéjols, Vušković和Michele Conforti于2001年证明了“square-free”完美图的着色定理后，Chudnovsky表示：“下一步便可以推而广之到更普遍的网络结构中”。
在2002年，Chudnovsky同她的博士导师（Seymour）以及另外两个合作者共同证明了“强完美图定理”（strongperfect graph theorem），证实如何完成一个完美图。他们的论证发表在2006年的《the Annals of Mathematics》上，占了150页的篇幅。但强完美图定理提供了一个简单的令人惊奇的完善方案： 就像Berge在54年前猜想的一样，只有一图不包含由5个或更多节点组成的“奇洞”（odd holes）或 “反奇洞” (odd antiholes)时才能被称为完美图。
奇洞是一个闭合的回路，它穿过图表的一部分，经过奇数个节点。（如果把图画在纸上，沿此路径用剪刀剪开，会从纸上剪下一个洞。）在一个“反奇洞”中，形成它的节点与该图其它所有节点都连接在一起，距离它最近的节点除外，最终形成一个星型。让我们看看这些奇点为什么会导致图形不完美：例如“五个节点组成的奇洞”，就像一个五角大厦，它的团数（cliques） 是2，然而只有成对儿的连续节点才能连接在一起。但如果仅用两种颜色给五个节点的奇洞着色，例如蓝色和绿色，很快就会陷入麻烦：第5个节点一边紧邻绿色节点，一边紧邻蓝色节点。我们需要第三种颜色给这个节点着色。（三个节点的奇洞，不像更多节点的奇洞，属于完美图表，因为它们的团数（cliques）是3）
现实世界的图表，如会议时间表，曼哈顿地铁系统或人类神经网络，通常含有奇洞，使得完美图的研究成为重要的智能运用研究。美国利兹大学教授Vušković说：“这种完美图可以帮助你开发尖端科技，从而应用于其他类型的网络结构中。”
然而完美图仍然十分复杂，得到完美图需要考虑其内在网络结构，但是这一过程仍缺乏简洁而有力的论证。Alan Tuck表示：“现有零碎的发现并不能帮助我们得到完整的理论。” 在为缺少square（也称4节点奇洞）的网络设计最佳着色方案的理论中，Chudnovsky等人采用了一种“分布化解”的方案，将网络分为不同部分，分别着色后合并为完整网络。
在为网络着色前，Chudnovsky等人首先将网络结构简化为一种“棱状”（prism）结构，每一组“棱状”结构中包含一对三边相连的三点网络（three-holes）。
其次，通过分析 “棱状”结构如何与剩余网络联系起来，研究者将图分割为左右两部分，并通过部分桥梁（hinge）节点将两部分连接起来。负责连接两部分图的桥梁节点也可能包含方格形（square）结构，但是方格形结构（square）和桥梁（hinge）有太多的着色方案，在现有证明中暂时不考虑这类特殊案例。
假如左右两部分其中一方仍包含“棱状”结构，研究者则会将其继续向下划分，直到不再包含“棱状”结构为止。（此时，方形（square）结构再次会制造障碍，过多的方形结构需要过多分割，导致着色效率下降。）
当左右部分均不再包含“棱状”结构，便可以开始着色过程。研究者证明存在一种高效方案可以同时为左右两部分及其桥梁节点着色。通常，为桥梁节点着色的方案并不能完全契合（译者注：即不一定可以保证相邻桥梁节点颜色不同），于是，着色过程的最后一步即为调整桥梁节点的颜色直到保证其颜色不会与各自毗邻的节点（neighboring nodes）颜色相同为止。
至此为止，关于如何处理方形结构的着色仍然没有得到解决。该领域的研究者就当前研究是否已经实现了完美图着色方案（perfect graph coloring theorem）仍然无法达成共识。在Vušković 看来：“现有不包含方形结构的完美图已经涵盖了最优图的复杂结构，因此也已经很大程度接近了更普遍的网络结构。” Cornuéjols则认为：“离解决所有网络结构的最优着色方案还有相当远的距离。”
五位研究者将在今年12月于法国格勒诺布尔（Grenoble）见面，讨论如何将他们的论证推广到更普遍的网络结构中。
Trotignon 是巴黎高等师范的一名数学及计算机科学家，他表示：“在完美图的着色方案设计上，我们已经推进了一大步，然而还需要投入更多努力。我个人的感觉是这一领域最终一定会得到解决。在解决不包含方形结构的方案出现之前（译者注：即Chudnovsky等人的方案），我并不抱希望。”
有人认为，假设研究者能够成功提出完美图的着色定理，将会标志着一个时代的终结。Cornuéjols认为：“对我而言，这是关于完美图最后一个尚待解答的大疑问。”
原文发布时间为：2015-11-11
本文来自云栖社区合作伙伴“大数据文摘”，了解相关信息可以关注“BigDataDigest”微信公众号
