魅力无限的图论(Ⅰ)

许 进

(北京大学 信息科学技术学院， 北京 100871)

1 图论过去、现在和未来

图的概念引入主要来自两个方面：①1736年大数学家Euler[1]解决格尼斯堡七桥问题而提出图的概念；②1840年电路专家Kirchhoff[2]研究电路时，为了研究电路中电流和电压的特性,独创性地引入图的概念，揭示了电路中的一些基本性质，提出了著名的基尔霍夫第一定律和基尔霍夫第二定律.

从1736年到1936年，整整两个世纪，图论的发展是非常缓慢的.1936年，法国数学家Berge才写出第一本图论的专著.就在1936年，年仅24岁的超天才图灵创立了图灵机[3].1945年，冯·诺依曼根据图灵机原理建立了可编程的计算机结构体系.1946年，在美国宾夕法尼亚大学诞生了人类第一台电子计算机.由于冯·诺依曼电子计算机模型是基于0-1二进制的，它的理论体系是离散数学，而图论在离散数学中的地位几乎是主导性的，这就极大地激发了人们对图论研究的兴趣.于是，伴随着电子计算机的发展，图论这门古老而年轻的学科得到了飞速的发展.从1945年至今，仅仅七十余年，无论从理论研究，还是在现实生活中的应用，都得到了惊人的发展.现在，可以毫不夸张地讲，图论几乎已经应用于人类目前创造的所有领域.2016年，一种从底层全并行的计算机模型，称为“探针机”被提出来[4].该模型发现了图灵机的局限性，即本质上与中国珠算等价.探针机的框架充分利用图论理论构建.相信未来，人类的计算机体系结构将会以探针机模型构建.

2 图论魅力无限

首先，图论在理论方面存在层出不穷又难的出奇的难题需要去解决，其中有些问题的难度可能不亚于诸如哥德巴赫猜想、孪生数猜想、费马尔猜想及P≠NP猜想等.

其次，图论自身优势特点与时代发展相契合.图论自身直观、简单、明了的优势特点，在解决问题时能给人以独特、奇妙的魅力感受.由于四色猜想的促进和电子计算机科学快速发展的强烈激发，图论在当今离散数学与组合数学中占据了主导地位，现已在理论上形成了含盖树论、图的度序列理论、连通图论、代数图论、图的计数理论、着色理论、平面图理论及其应用、Ramsey数理论、图的可遍历性理论、算法图论及应用图论的强大理论体系[5-7].加之互联网的促进，人类发展到了产生大量形形色色数据的“大数据时代”和“社交网络时代”，而要处理这些海量数据，图论因其在模型构建和算法设计上的独特优势势必担当主角.

最后，图论具有许多数学分支无法比拟的、广阔无垠的应用天地.可以毫不夸张地讲，图论几乎可以应用于人类目前创造的所有领域.经过近几十年的发展，图论业已广泛应用于诸如生命科学、计算机科学、电子线路、信息科学、模式识别、网络安全、心理学、社会科学，甚至中文等领域.

图论的魅力在于它本身的结构之美，解决问题的速度之快，以及应用的范围之广.在可预见的将来，图论将在下述八个领域大放异彩.

2.1 生命科学领域

在生命科学领域，很多重要问题的研究都涉及到生物复杂网络，如生物神经网络[8]、控制生物性状的基因网络[9]、植物次生代谢网络[10]、蛋白质相互作用网络[11]、蛋白质结构预测问题[12]等.生物神经网络通常指生物的大脑神经元、细胞、触点等组成的网络；在基因网络中，结点是转录因子或基因，边表示转录因子和基因之间的调控关系；代谢网络中结点代表的是代谢底物或者产物，而边代表底物或产物之间的代谢反映；蛋白质相互作用网络中，结点代表蛋白质个体，边代表两个蛋白质之间的相互作用关系.因此，这些问题可利用图论的方法进行研究.Koessler等[13]利用图论方法，对从主结构确定RNA二级结构的问题进行研究，提出了RNA二级结构的预测模型.Bermúdez等[14]利用图论方法刻画大肠杆菌的tRNA结构，将tRNA表示为图，其中顶点对应核苷酸，边对应磷酸二酯和氢键之间的键.Ren等[15]利用图论方法，建立脑功能的网络结构模型，研究了针灸调节脑网络重组的效果. Stavrakas等[16]利用图论方法建立蛋白质结构网络，通过宽度优先遍历算法识别最短路径，分析了蛋白质相互作用网络，给出了生物学解释.

2.2 社交网络领域

社交网络又称为社会网络，是一种基于网络的社交组织形式，指社会行动者及他们之间关系的集合.若将社交网络中的基本要素，也就是每个人看成一个节点，节点之间的连线看成是人与人之间的联系，那么用一个复杂的图就可以对社交网络进行描述，G=(V,E)，其中V表示节点的集合，E表示节点关联(边)的集合.因此，社交网络中的一些重要问题，如结构特征[17-18]、社区发现[19-20]、影响力最大化[21-22]等问题，都可以利用图论的方法进行研究.

1998年，Watts等[17]发现许多网络中都存在小世界现象.网络的小世界特性包含两个重要的属性，即网络平均路径长度和平均聚集系数.Mislove等[23]对YouTube、Flickr、Live Journal等知名在线社交网络进行了小世界现象的验证，得到这些不同种类的在线社交网络均有小世界现象.

Barabasi等[18]于1999 年首先发现了复杂网络的无标度特性，并揭示出无标度性是许多复杂网络具有的性质.社区发现问题都是NP-难问题[19]，Palla等[20]提出了团渗透的方法解决社区发现问题，并定义在k团特征图中有k-1个节点相同的k团具有连接关系.特征图中的每个连通分支就被定义为一个社区.由于k团之间会有重叠节点，因此，这种方法可以自然地发现重叠社区.

影响最大化问题最早是由Domingos等[21]引入到社交网络中的.他们将影响最大化问题抽象成一个算法问题.Kempe 等[22]针对所提出的级联模型和阈值模型，给出了一种贪心近似算法，并证明了该算法的贪心近似比至少为1-1/e. Estevez等[24]提出了集合覆盖贪心算法.Chen等[25]从两个方面提高了影响力最大化的效率问题，即首先提出一种改进的贪心算法，该算法将图中没有传播成功的边去掉，得到新的图，然后在新图上依照贪心策略依次选择初始节点.

2.3 网络安全领域

社会信息化程度的加深使人们对网络的依赖程度加强，网络安全日益受到重视并得到广泛的研究.其中，图论作为研究网络安全的重要工具，被用于研究各种可行的方法以对网络系统安全进行建模、分析和评估，并取得了许多的研究成果.

2.3.1 攻击树

Schneier[26]提出的攻击树是一种描述渗透式攻击对系统安全造成威胁的模型，能比较直观地反映攻击者实施攻击的步骤.在攻击树模型中，用树型结构来表示系统面临的攻击，其中根节点代表被攻击的目标，叶子节点表示达成攻击目标的方法，可以在很大程度上帮助我们判断系统存在的威胁和决定应对攻击的方法.

2.3.2 攻击图

网络中总是存在一定的安全漏洞，同时这些漏洞之间可能存在一定的关联关系，即当一个漏洞被成功利用后，可能为另一漏洞的利用创造有利条件.结合网络拓扑、目标漏洞、主机弱点等信息，找到所有能够到达目标的攻击路径，并以图的形式表现，即攻击图[27].

攻击图能够挖掘出潜在的攻击序列，可对网络系统的安全性做出更为全面的分析，及时发现和消除计算机网络系统中存在的安全隐患，减少恶意攻击.与攻击树相比，攻击图对网络攻击过程的描述能力更强，但该方法因其高复杂度，存在组合爆炸问题，无法直接对大规模网络使用.

2.3.3 脆弱性分析

对一个网络的拓扑结构而言，总有一个或多个节点占有极为重要的位置，如果破坏掉它们，这个网络在诸如结构、稳定性上将受到很大的影响.因此，分析关键节点或脆弱点有着重要的现实意义.

最为简单直接的做法就是使用节点的度指标，来衡量关键节点的重要程度.笔者提出了核与核度理论[28]，用于刻画网络中一组节点的重要性, 通过删除一些节点及其相连的边后, 以网络中出现的连通分支个数来衡量核度.王建伟等[29]认为连接节点的边越重要, 则节点越重要，并将其视为分析网络中节点与连边重要性的一个基本公理.同时，还有基于随机游走思想设计的算法，如PageRank和LeaderRank，也可以用于网络脆弱性分析.

此外，还有一些基于图论的网络安全分析方法，如类似于攻击树的故障树[30]具有可靠性分析的功能，被大量应用在航空航天和核工业等产业领域.总之，图论因其具有高效性和较好的可读性，被广泛应用于网络安全领域当中.

2.4 社会科学领域

人类社会有种种现象，涉及经济、政治、心理、历史等很多学科，社会科学便是用科学的方法来研究人类社会这些现象.在科学研究的发展进程中，图论为社会科学的研究提供了新的方法和手段.例如在经济金融领域，Tabak等[31]研究了巴西股票市场网络的拓扑结构，使用关联矩阵为不同板块的股票构建了最小生成树，采用复杂网络的动态方法度量了不同板块的相对重要指数，并给出了股票市场网络中最重要的板块.如何分析越来越庞大的金融数据集是现在众多应用需要面对的挑战.2012年，Lautier等[32]针对金融市场的高维数据提出了一种可以应用于多种领域的图论分析方法，同时阐述了该方法应用于金融衍生市场系统风险分析情景的优势.针对金融领域的犯罪场景，Jedrzejek 等[33]使用图挖掘方法进行检测，对犯罪行为人的行为及逆行有效推理.在心理学领域，Crosier等[34]回顾了社交网络的演化基础和网络构成中的心理因素.在考古学领域，Brughmans[35]追溯了考古学家中最有影响力的学术传统以及网络模型和技术的起源，揭示了图论方法在考古学中的潜力.

2.5 系统科学领域

图论在系统科学领域也有诸多应用.在研究系统中非常重要的要素，即系统的核和核度理论时，用图作为系统中要素和关系的映射以及应用图论进行分析与研究是一种相当重要的方法[28].譬如控制系统等很多复杂的系统都可以简化地表示为一个图.作为分析大型工程问题的有力工具，图论可以帮助我们简化复杂系统的拓扑连接关系.图论中的许多研究成果也可以作为分析系统结构、寻求系统优化算法的重要理论依据和研究方法[36]，图论在复杂系统中的系统设计、故障诊断恢复、状态分析、损费分摊等方面均有广泛而重要的应用[37].Prabhakaran等[38]利用图论的方法，通过建立复合材料性能与结构之间的联系，给出了一种对复合产品系统进行完整分析的自上而下的方法.Schné等[39]利用图论方法，对分散化控制器结构进行优化设计，提出一种基于最接近加权最大匹配的图论算法，改进了分散化控制器的效率.Hamzeh等[40]利用图论方法，对电力系统网络的优化配置问题进行了研究.

2.6 交通信号研究

近年来随着城市人口密度的增长，车流量的增加，交通拥堵成为各大城市需要重点解决的难题.解决交通拥堵一方面在于合理的城市道路规划，另一方面则在于优化交通信号从而发挥其合理的交通指挥和疏导作用[41].因为交通信号在处理过程中存在着错综复杂的连接关系，因而图论知识在其中起到了不可或缺的作用.

在处理交通信号灯问题时，可以引入图论中“图染色”的概念[42].将城市路口交通信号灯最优相位个数归结为其交通流模型图的圆色数.在计算过程中，根据特殊n岔路口交通流状况，由车流的冲突关系给出交通流模型图并求出它们的圆色数，即为给出对应交通信号灯的最优相位个数，从而确定不同状态下的交通信号.

此外，城市轨道交通线路之间的连接关系同样可以利用图论的形式来展现.在设计城市轨道交通信号设备布置模型时，可采用图论拓扑结构策略[43].用图的形式描述信号设备，为城市轨道交通信号设备布置设计合理的矢量图形数据拓扑结构，从而实现信息数据的组织.在解决地铁信号设备布置问题的算法中，需要从某个信号设备出发，系统遍历所有的信号设备，在这个过程中，需要用到图论知识中图的遍历. Yang等[44]利用图论方法，提出一种基于点对点网络的车辆网络模型，提高了网络通信能力以及网络系统的稳定性.

2.7 中文研究

图论在中文研究领域，诸如在文本研究、古汉语音韵学研究等领域，都有着极为广泛的应用，对探索语言网络的结构特征规律和功能演化规律有着十分重要的意义.

2006年，通过应用基于模糊图论的最大树法，提出了一种中文文本模糊聚类算法ATCMT[45].ATCMT首先对文本建立模糊相似矩阵，然后构造模糊图及其最大模糊支撑树，最后进行模糊聚类分析.2009年，一种基于图结构的中文文本表示模型被提出[46].它将文本特征项表示成图结构节点，将特征项之间的共现关系表示为图结构的边，从而将文本映射为图结构，有效地解决了文本表示中词语间语义信息缺失问题.2012年，结合图论中的理论，一种基于语义图结构的中文文本分类方法RCSGC被提出[47].除了对文本研究有着极为重要的作用，图论在古汉语音韵学研究中也有一定的实用价值.2011年，一种基于图论方法的度量古汉语词音相似度方法被提出[48]，为传统音韵学长期以来建立的定性研究提供了一些定量的参考和检验.

2.8 模式识别研究

模式识别指对表征事物或现象各种形式的信息进行处理和分析，从而达到对事物或现象进行描述、辨认、分类和解释的目的.在自然界中，大量模式都可以用图的形式进行表示.随着数据存储、传输、计算能力的增强，人们开始有能力从图结构数据中提取有用的信息.以图理论对问题和数据进行建模，利用经典图论算法求解或与其他新兴技术相融合正越来越成为模式识别研究中的热门领域.比如在计算机视觉方向，利用图论建模图像中的拓扑关系，提高图像识别和分割的准确率及可信度[49-50]；在计算化学方向，以图结构对化合物分子结构进行建模，以寻找特定的分子亚结构和模式，为新型化合物制备及药物研发提供理论指导[51]；在脑科学方向，利用图论方法，对功能核磁共振成像数据进行建模，在分析各神经单元的依赖关系和因果性相互作用，建立大脑连接模式，理解大脑架构等方面发挥了重要作用[52].此外，图论与其他理论和工具的融合也催生了一系列富有前景的新方法，如概率图模型[53]、图神经网络[54]等.