图计算发展简史（上）

导读：图数据库的技术的根本是图计算与存储技术（事实上所有IT技术在本质上都是计算、存储与网络，因为计算有网络计算、分布式计算，存储有分布式存储、网络存储，因此我们经常省略掉网络而只说计算和存储），而图计算 （图分析）的理论基础是图论。

本文将通过回顾图论相关学科与技术的发展历史以帮助大家更好地了解图技术。

一.图计算溯源

图计算最早可以溯源到250年前，欧拉（Leonhard Euler）被认为是人类历史上最伟大的数学家，他是图论与拓扑学的开创人，生于瑞士巴塞尔（在金融领域中的“巴塞尔协议III”就得名于此地 —这种小知识的延展就是典型的2步关联）。

​

欧拉通过对哥尼斯堡七孔桥（Seven Bridges of Konigssberg）问题的描述而开创了图论学科。

在哥尼斯堡（现俄罗斯的加里宁格勒市，濒临波罗的海，二战之前是德国东部最大的城市，1945年被苏联红军占领，1946年改为今名）的一个公园里，有七座桥将普雷格尔河（Pregel）中两个岛及岛与河岸连接起来。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点呢？

欧拉于1736年研究并证明了此问题，他把问题归结为“一笔画”问题，并证明一笔画的走法是不可能的。

​

如图所示，在图2的b中是把陆地与桥分别抽象为点、边后所形成的一个简单的拓扑图（拓扑网络）。

在这张图中，上面的一笔画问题变成了寻找是否存在一条“欧拉路径（Euler path），即是否存在一条路径可以遍历图中的每一条边仅一次（欧拉环Euler circuit，是欧拉路径的一种特例，它的定义是存在一条路径可以从一个点出发遍历所有路径后回到该点）。

欧拉是如何证伪这个一笔画的问题呢？

按照欧拉路径的定义，只有起点与终点可能存在奇数条边，其它所有途径节点都只可能是偶数条边。显然，图2—b不符合这个特征，所以一笔画无法实现。

如果延展为欧拉环路的问题，那么条件会苛刻到所有顶点都必须是偶数条边。按照充分与必要的条件，没有欧拉路径，就一定不会有欧拉环。

在这个过程中引入了图论（图计算）的一个基础概念——度（degree），即我们提到的每个顶点的相连边的概念，如果是无向图（忽略图中的边的方向），那么每个顶点的相连的边的数量就是它的度。在有向图中，每个顶点的度等于它的入度边的数量+出度边的数量，既out-degree + in-degree之和。

二.图论的早期应用场景

图论的早期应用的一个主要场景是地图渲染（染色），随着15—17世纪大航海时代的到来以及法国大革命(1789-1799)之后民族国家概念的兴起，世界各国都开始绘制更高精度的地图，而绘图中如何用最少的颜色来保证相邻的两个区域（国家、州、省）用不同的颜色区别开来的问题是个经典的图论问题（图3）。

19世纪中叶，数学家们以手工计算的方式证明了“五色地图”的问题，而直到整整一个世纪之后的1976年，才在计算机的算力的帮助下初步证明了“四色地图”(four color map theorem)的可行性。这类证明随着计算机的算力的提升被不断地演进，直至2005年，通过复杂的人机交互理论证明软件的帮助，以通用的方式证明了四色地图的可行性。这也是通过计算机程序的“穷举计算”来辅助证明的第一个主流理论。

​

图3展示了 通过图计算优化后，以四色图取代了五色图。地图上色问题是数学中典型的NP完全（NPC或NP-Complete，Non-deterministic Polynomial-time Complete，即非确定性多项式时间完全）问题，即NP中最难的决定性问题。

通过本文的背景介绍，希望读者能够做好准备，更好地进入图数据库的世界。

​—— 未完待续 ——

图计算发展简史之完整目录：

一.图计算溯源

二.图论的早期应用场景

三.浅谈拓扑

四.从图到随机图理论的研究

五.关系型数据库和非关系型数据库

六.图计算与后关系型数据库时代

本文摘编于《图数据库原理、架构与应用》，经出版方授权发布。（书号：9787111708100）转载请保留文章来源。

◆内容简介：

这是一本能帮助读者快速掌握图数据库的原理、架构、算法、扩展、规划、测评、优化以及实战应用的著作，书中的理论和实践均来自国内领先的图数据库企业Ultipa的科研成果和实践经验，由Ultipa的创始人兼CTO孙宇熙领衔撰写。

该书内容全面、体系完整、循序渐进、深入浅出、图文并茂，兼具理论性、实战性、趣味性。用通俗的语言将抽象的图数据库技术具体化、形象化，将带领读者经历一次非凡的“图数据之旅”。

通过本书，你将掌握以下内容：

·图数据库、图计算的概念与区别；

·图计算、图存储、图查询语言的原理；

·高性能图存储架构、计算架构；

·图数据库查询与分析框架的设计；

·度计算、中心性计算、相似度计算、连通性计算等图算法；

·可扩展的图数据库设计；

·高可用分布式设计；

·图数据库在决策智能、反欺诈、反洗钱、智能推荐、流动性风险管理等多个领域的实战经验；

·图系统的规划、评测与优化。

◆作者简介：

孙宇熙：业界知名的高性能计算与存储系统专家、大数据专家、数据库专家及学者，Ultipa创始人兼CTO。曾任EMC（易安信）亚太研发集团CTO和中国研究院院长、哈尔滨工业大学客座教授、中国电子学会云计算专家委员会委员；持有50多个美国及中国专利；文物鉴赏家、收藏家，哈佛大学美术馆亚洲艺术鉴赏委员会理事；技术作家，著有《云计算与大数据》《软件定义数据中心》《大数据分析》《程序员生存手册》（The 99 Points of Launching High-Tech Business）等多部中英文科技畅销书。

嬴图（Ultipa）团队 一支致力于构建世界上最快、最直观、最易用的下一代实时图数据库的国际化的技术研发与推广团队。自研的核心产品包括高性能图计算与实时图数据库软件，已构建了一整套针对数据资产管理、数据生命周期管理、数据治理指标管理的智能化产品矩阵。团队目前已获得高密度并行图计算、超级节点处理、高性能查询语言及半结构化图数据处理、海量数据导入、装置、设备及存储介质、数据库深度路径搜索、动态图剪枝过滤等30多项技术成果和专利，100%自研并拥有全部底层架构，研发成果已成功服务于多家大型央企、国有企业及世界500强企业。