精选
大数学家欧拉（Leornhard Euler）成功解决哥尼斯堡七桥问题标志着图论的诞生，距今已有两个多世纪。经历了这两个多世纪的发展，图论逐渐简化为以点和边为研究对象的一门学科，以其直观、简明的特点在学术研究和科技发展中发挥了不可替代的作用：DNA序列可以通过欧拉回路进行分析，运筹学、计算机科学和编码理论中的很多问题可以化为汉密尔顿回路，大规模集成电路的划分和布局问题可以利用点集划分、二次分配和最小斯坦纳树解决。就连随处可及、包罗大千世界万物众生的互联网也不过是一张庞大的信息传输图而已。
|
图1 汉密尔顿图
这里我们要介绍另一种特殊的图，它不像大名鼎鼎的欧拉图、汉密尔顿图那样众所周知，而且其实际应用尚不多见，但却在基础理论研究中占有一席之地，它就是弦图。
我们将经过有限多个点且不相交的闭路称为环，将连接环中不相邻的两个点的边称为弦。如果无向图中任意长度大于3的环中都至少有一条弦，那么该图就称为弦图。由于弦会将环分割成为若干个三角形，所以弦图也称为三角图。
|
图2 环（蓝色的闭路）、弦（红色的边）和琵琶（右）
图2给出了一个最简单的弦图，图中红色的边就是一条弦。弦图形象而又富有艺术感，会让人联想到琴弦。是否有人还会由此想到《琵琶行》中的诗句“转轴拨弦三两声，未成曲调先有情”呢？
在弦图谱成的乐章中，完美消除序列是最动听的音符。如果弦图G的顶点排列v1, v2,…,vn满足：对任意的i，{vi+1 ,…, vn}中与vi相连的点都构成完全图，那么称顶点序列v1, v2,…,vn为图G的完美消除序列。可以证明，一个图为弦图当且仅当它有一个完美消除序列。
|
图3 完美消除序列
以图3为例，我们来判断弦图中顶点序列1,2,3,4,5,6是否为该弦图的完美消除序列。为此首先观察顶点1：顶点2和3与其相连，并且顶点1,2,3构成了一个完全图。再观察顶点2：顶点3和4是与2相连且编号比2大的点，并且顶点2,3,4构成了一个完全图。由此类推，可以发现如图所示的顶点序列1,2,3,4,5,6就是该弦图的一个完美消除序列。
完美消除序列可以看作是与弦图等价的概念。事实上，弦图在理论研究中的应用大多用到完美消除序列，这就使得弦图完美消除序列的计算变得格外重要。目前已有很多计算完美消除序列的算法，例如单纯点朴素算法、字典序广度优先算法和最大势算法（即MCS算法，其时间复杂度最小，且容易理解）。用MCS算法计算给定弦图G的完美消除序列的过程如下：按照从n到1的顺序给图G的n个顶点编号（标号为i的点出现在完美消除序列的第i个位置），label[i]表示与第i个点相连的已经标号的点个数，每次选择label最大的未标号的点进行标号，直到图G的所有顶点均有标号，由此即可得到图G的一个完美消除序列。
我们用下述例子演示由MCS算法计算弦图G的完美消除序列过程。
|
图4 (1) 初始状态 (2) 第一步编号 (3) 第二步编号 (4) 终止状态
在图4中，[]内的数字表示顶点的label。在初始状态，全部6个顶点的label为0，如图4(1)。开始处理时，先任意选取一个顶点从n=6开始标号，这里选取图左上角的顶点标号为6（如图4(2)）；接着，与6号顶点相连的其它顶点的label相应改变；然后，再选取label最大的顶点按照顺序继续编号。在有多个最大的label时，可以任取其中之一进行编号，编号结果如图4(3)所示。如此类推，直至所有顶点均有编号，如图4(4)。这时顶点1,2,3,4,5,6就是弦图G的一个完美消除序列。
许多研究问题都能通过弦图的完美消除序列得到极大简化。其中之一是困扰了数学家一个多世纪的四色定理：平面或球面上的任何地图都能够只用四种颜色来完成着色，使得任意两个相邻国家的颜色都不相同。该定理的猜想最早于1852年由古德里（Francis Guthrie）提出，但直到1976年它的证明才由阿佩尔（Kenneth Appel）和哈肯（Wolfgang Haken）给出，该证明含有运行了1200多个小时的计算机验证。从四色定理出发，我们考虑另一个有关的问题——点着色问题。
点着色问题是指，用最少的颜色为无向图的顶点着色，使得所有顶点均着有颜色且相邻顶点的颜色不同。回溯算法、分支定界法、Welsh Powell法、布尔代数法、模拟退火算法等等都可以用来解决点着色问题。对一般图进行点着色，上述算法的时间复杂度都很高，其中回溯算法的时间复杂度为指数阶的。然而，若对弦图进行点着色，则有非常有效的着色方法：先计算出弦图的完美消除序列，再按照完美消除序列从后往前依次给顶点着色，着色时尽可能使用已经用过的颜色。利用这种方法对弦图进行点着色，其时间复杂度关于点数n是线性的。
例如图3中的六边形，我们可以通过图中给出的完美消除序列对其进行点着色：首先对顶点6着色，然后将顶点5着成与6不同的颜色，接下来再将顶点4着成与5,6都不同的颜色，由此继续很容易完成点着色的过程。所得结果如图5所示，由此可见用三种颜色就可以完成该图的点着色。利用完美消除序列对弦图进行点着色，不仅着色方法会得到简化，而且着色的时间复杂度也会降低。
|
图5 弦图的着色结果
弦图还可用于预测高斯消去法中矩阵的非零元结构。John R. Gilbert在他1986年的文章中指出，当输入矩阵具有弦图结构时，对该矩阵进行高斯消去法后得到的矩阵的关联图将是原弦图的子图。进一步地，Diego Cifuentes和Pablo A. Parrilo首次指出了多项式组的弦图结构与三角列之间的内外联系，并指出王东明所提出的若干三角分解算法对处理具有弦图结构的多项式组效率更高。受此启发，牟晨琪和笔者证明了将自上而下形式的三角分解算法用于具有弦图结构的多项式组时，计算所得的三角列的关联图都是该弦图的子图。
例如，图6为多项式组
F={ x2 + x1 + 2,(x2 + 2)x3 + x1, (x3 + x2)x4 + x3 – 1, x4 + x2 }
的关联图（这里变元序规定为x1< x2< x3< x4），该图为弦图。利用王东明提出的自上而下的三角分解算法对F进行三角分解，得到的三角列为
T1 =[ -x13+x12+14x1+16,x2+x1+2,(x2+2)x3+x1,(x3+x2)x4+x3-1 ],
T2 =[ x1+1, x2+1, x3-1, x4+x2 ],
T3 =[ x1, x2+2,(x2-1) x3+ x22+1,(x3+ x2) x4+ x3-1 ],
它们对应的关联图分别如图7中(a)、(b)、(c)所示。由图可知，输出三角列的关联图均为原弦图的子图。
|
图6 多项式组F的关联图
|
图7 三角列T1，T2，T3的关联图
在此基础上，牟晨琪与笔者提出了基于弦图的完美消除序列对稀疏多项式组进行三角分解的快速算法。该算法在调用自上而下形式的三角分解算法对稀疏多项式组进行分解时，其效率显著提升。
此外，弦图在信息论、控制论和运筹学等领域中已有若干应用，然而对弦图的研究还处于起始阶段。弦图是否可以用于其它领域，揭示更多算法的内蕴特性，仍是有待探究的问题。这些问题的研究和解决是否会让弦图更玄更炫，演奏出“大珠小珠落玉盘”的动人乐曲？我们拭目以待。
那数弦与琴弦有什么内在联系呢？数弦之理在于去繁从简、化曲为直，琴弦之美妙在于震颤有声、声声悦耳，弓弦之神奇在于收放有力、力力向的。弦能射出巨矢长箭，能弹出高山流水，能演绎出勾股方圆。琴声出于弦，数形亦然，声形合一，数琴同源！
（本文经王东明教授审阅）
（白阳）
来源：阿狗数学AlgoMath
转载本文请联系原作者获取授权，同时请注明本文来自王东明科学网博客。
链接地址：https://wap.sciencenet.cn/blog-1362128-1111919.html?mobile=1
收藏
