1.2.1 图论及其发展史

图论作为一门学科和数学领域的一个重要分支，通常认为它奠基的标志性事件之一是1736年数学家欧拉在圣彼得堡科学院发表了论文《哥尼斯堡七桥问题》（见图1-10），欧拉用证伪的方式证明了“困扰”当地居民很久的一个数学问题—能否从哥尼斯堡城中的任意地方出发，经过且只经过七座桥中的每座桥一次，再回到原点？这个问题的证明过程与证伪结果在图论中被称作欧拉环路（Eulerian Circuit），欧拉环路可看作欧拉路径的一种特例（如果路径的起点和终点相同，欧拉路径就是欧拉环路）。

在中小学奥林匹克数学竞赛中常见的“一笔画”问题，实质上就是欧拉环路是否存在的问题。但是在欧拉的时代，他对于现实问题的数学抽象是极具开创性的：哥尼斯堡的七座桥坐落在城市的4块陆地上，每座桥跨越了当地的一条叫作普列戈利亚（Pregolya）的河流，并连接两块陆地。欧拉把陆地抽象为顶点，桥抽象为边，并证明从任意顶点出发，如果要经过每条边一次并回到原点，连接每个顶点的边的数量一定是偶数。图1-10b的图模型告诉我们，没有任何一个顶点符合连接偶数条边的限定要求，因此不可能存在欧拉环路。

而图论奠基的另一标志性事件（在影响力与知名度上远不如欧拉的七桥问题）是对骑士巡逻（Knight 's Tour）问题的解决。在比欧拉更早的、与牛顿同时期的莱布尼茨（1646—1716）时代，莱布尼茨与欧拉先后研究过骑士巡逻问题，但都没有提出确定的解决方案。该问题直到19世纪上半叶被一个叫作马踏棋盘的算法成功破解，后世也将该算法称为Warnsdorf算法，以纪念它的发明人—德国数学家冯·沃恩斯多夫（H.C.von Warnsdorf）。

骑士巡逻问题经常出现在计算机专业本科生的编程作业中。尽管骑士巡逻问题被认为是NP复杂（NP-Hard、NP-Complete）问题，它本身是哈密尔顿路径（Hamilton Path）的一个典型例子，但在实际的编程实现中，如果使用启发式学习等策略，是很有可能以线性的（而非指数性的）复杂度来找到答案的，沃恩斯多夫的论文中描述的就是这样一种启发式策略（这里我们也可以笼统地称之为一种图算法）。骑士巡逻问题也可以通过神经元网络的方式解决，不过此方式到20世纪90年代才得以实现。

欧拉解决七桥问题之后整整100年，图论领域并没有特别显著的进展（图论或图的正式命名在19世纪末才出现，英国数学家西尔维斯特（J. J. Sylvester）于1878年在《自然》杂志上首次明确提出了图的概念—一张图由多个顶点与边组成）。但是，一些重要的概念和现象被逐步揭示。

❑ 1847年，德国数学家利斯汀（Johann B. Listing）明确了拓扑（Topology）的概念，明确了拓扑学研究的范畴包含连通性、紧致性、维度等。一般认为，欧拉的七桥问题是拓扑学解决实际问题的最早应用案例。

❑ 19世纪中叶，通过手工计算证明了五色地图问题。地图染色问题贯穿了15世纪末到20世纪初的大航海到地理大发现时期，而四色地图的证明则等到20世纪70年代借助计算机的算力才得以初步完成。

❑ 19世纪下半叶到20世纪初，对于具有特殊空间拓扑结构的物体的研究有所发展，如莫比乌斯环（Mobius Strip）、克莱因瓶（Klein Bottle）、三叶结（Trefoil Knot）等，如图1-11所示。

❑ 1936年，第一部图论教科书由匈牙利数学家康尼格（Dénes Kőnig，1884—1944）发表，这也是图论作为数学的一个重要分支的起始，而这距离欧拉解决七桥问题已经过去了整整200年。

图论领域的另一个重要里程碑是20世纪50年代末到60年代对于随机图（Random Graph）理论的研究，其中最知名的是ER随机图（Erdős-Rényi Random Graph，如图1-12所示。注意它与ER模型图的区别，前者的ER是两个学者的姓氏组合，而后者指的是实体-关系，即Entity-Relationship）—任意图模型都可以被称作随机图。今天，我们通常把随机图作为研究复杂网络的基础，例如统计物理学中的渗流理论（Percolation Theory）就与随机图高度相关，机器学习中的随机森林（Random Forest）或随机决策森林（Random Decision Forest）可看作随机图的子集—毕竟在拓扑结构中，树被看作一种简化的、无环的图。

20世纪50年代，伴随着初代计算机技术的发展，开始涌现出了一些典型的早期图算法，例如，著名的Dijkstra算法解决的是一种典型的带权重的单源最短路径问题。目前已知的图算法超过120种（如果加上每种算法的变种，可能会超过200种），其中最早被应用的或许是深度优先搜索（Depth First Search）算法，它最早在19世纪被法国数学家特莱谋（Trémaux）应用于解决迷宫演算问题。但是不难想象，人类在远古时代就一定已经在使用某种图算法来走出迷宫，例如常见的沿左遍历或沿右遍历算法。实际上，所有的寻路问题（Pathfinding）都被视为面向迷宫问题时如何寻求最短路径解的问题。此外，与深度优先算法齐名的广度优先搜索（Breadth First Search）算法的出现要晚得多，一般认为是在二战时期由德国科学家发明的，但论文的发布则晚于20世纪70年代。

20世纪80年代至90年代，随着社会心理学、社交网络研究的发展，开始出现了早期的图计算框架，也逐步奠定了互联网的理论基础。其中有两点值得注意：

1）社交网络研究中一般都采用简单图（Simple Graph）、同构图（Homogeneous Graph）模式，即实体代表人（用户），实体间的关联关系通常只有一种类型的边，表达关注或朋友关系。这与近年来随着金融科技（Fintech）对于图技术的应用而产生的复杂多边图（Multi-graph）—如两个账户实体间存在多笔转账交易关系—有很大的区别。事实上，有识之士已经意识到，图计算的需求需要通过多边图才能得到更好的满足，国际标准化组织LDBC（Linked Data Benchmark Council，关联数据评测委员会）已经着手制定金融评测标准（Financial Benchmark, FB）来取代和补充先前的社交网络评测标准（Social Network Benchmark, SNB）。

2）早期的图计算深度较浅，例如在互联网搜索引擎技术中最核心的网页排序算法（PageRank），它在迭代过程中的计算深度不大于2，意味着在系统架构层面是可以通过优化BSP（Bulky Synchronous Processing）系统实现大规模分布式架构的，如谷歌的Pregel图计算系统（Pregel源自德文，是欧拉解决的七桥问题所横跨的那条河的名字）。因此，就算我们说图算法奠定了WWW搜索引擎技术的基础，也一点都不过分。

20世纪90年代至今，图计算的应用场景在更多领域得以发展，例如服务业、运输业、航空业中的人力资源科学统筹规划，大型项目中的资源动态分配等。特别是金融服务业，以美国金融巨头为例，黑石的阿拉丁系统、高盛银行的SecDB和美国银行等纷纷基于图数据库、图计算引擎来奠定其核心金融产品的算力霸权。

金融行业对于新的技术有天然的敏感性，而金融业务本身伴随着对各类风险敞口、收益率与综合汇报率的量化计算，风险传导路径的传导分析，流动性与各项资产负债指标的预测分析及压测模拟，这些计算与分析天然地更适合用图计算的方式高效实现，而传统的关系型数据库、数据仓库、数据湖的架构难以实现对海量数据的实时、高阶、灵活、白盒化的分析/计算/模拟等操作。

图查询语言国际标准GQL预计于2024年面世，这是数据库领域自1983年发布SQL标准以来的唯一一个新的国际标准。在大数据与NoSQL类型数据库（如列数据库、宽表数据库、文档数据库、时序数据库）发展的近20年中，并没有形成任何新的国际标准，唯有图数据库会形成新的国际标准，这意味着全球专业人士已经达成了一个共识—SQL以及RDBMS（关系型数据模型与数据库）在过去的几十年中被广为诟病的问题有望得到彻底解决，而本书中涉及的图算法大多与解决这些问题息息相关。我们在这里罗列一下SQL/RDBMS的一些典型缺陷：

❑ 缺乏递归能力。这是由ER数据模型与SQL的内在建模和查询逻辑特性所造成的。

❑ 缺乏高维数据建模能力。ER模型本身表达的是高维（网络）模型，但是在二维表的限制下，数据之间的关联性被打散，进而无法高保真地还原真实世界的关系模型。

❑ 数据治理复杂。事实上，因为数据间的关联性被打散、打乱，当有大量表存在时，数据血缘分析变得异常困难。

❑ 效率低下。特别是在处理多表关联、深度下钻、海量数据干扰等问题时，大量T+1甚至T+N的SQL存储进程存在本身就说明了数据处理的效率低下。

❑ SQL代码复杂度高。特别是在进行复杂逻辑处理时，SQL代码的编写、测试极为复杂甚至黑盒化，容易造成效率低下等问题。