基本图算法的介绍与历史

图论的发展历史

图是一组配对的集合——可以是整数对、人对、城市对、恒星对、国家对、科学论文对、网页对、游戏位置对、递归子问题对，甚至图对本身。最常用的可视化方法是镜像表示；被配对的实体通常称为顶点或节点，而这些配对本身则称为边或弧。但实际上，这些对象和配对可以是任何事物。

图论最早的实例之一是道路网络及其地图。在罗马帝国鼎盛时期，罗马工程师在欧洲、西亚和北非修建了超过40万公里的公共道路网络。旅行者依靠路线图通行，这些路线图要么是简单的列表，要么是以图像形式呈现沿途地标与距离的说明。《普特林格地图》（Tabula Peutingeriana）是一幅13世纪的手卷，描绘了整个“罗马公共驿道系统”，普遍认为它是5世纪版本的中世纪复制品，而该版本又源自公元1世纪由奥古斯都皇帝下令编纂的《图画式行程录》。普特林格地图并非地理精确的地图——历史学家甚至争论它是否算得上一张真正的地图！但它是一种抽象的道路网络表示，类似于现代地铁线路图。每条道路上的城市通过曲线的折点来标识；这些城市的名称以及它们之间的路段长度也标注在图上。因此，这张地图包含了足够信息，可用来找出5世纪罗马帝国任意两座城市之间的最短路径。下图展示的是康拉德·米勒于1872年复原的《普特林格地图》的一个小片段，描绘了从今比尔滕（Veteribus，左上角）经科隆（Agripina）和波恩（Bonnae）到美因茨（Mogontiaco，右上角）的罗马道路，以及通往特里尔（Avg Tresvirorvm，中部）和梅茨（Matricorvm，底部中心）的分支。

图论中最古老的经典应用之一——特别是树结构的应用——是用于表示家谱。复杂的家族谱系已使用数百年，用以解决婚姻、继承和王位继承等法律问题。罗马帝国的民法后来被早期天主教会采纳为教会法，禁止一级堂表亲或更近亲属之间的通婚。到了9世纪初，教会改变了计算标准和距离要求：罗马的“法律计算法”要求最近共同祖先的距离之和至少为四，而新的“教会计算法”则要求两个距离的最大值至少为七。1215年，考虑到实际操作的需要（以及现实中的做法），教会将结婚所需的最小距离放宽至四。

下图展示了来自15世纪匿名著作《论亲缘与姻亲之树》（Johannes Andreae’s Super arboribus consanguinitatis et affinitatis）中的一个复杂婚姻案例。左侧图描述了一个极为复杂的例子：提里乌斯与特伯加结婚并生下儿子盖乌斯，之后提里乌斯去世；特伯加再嫁给洛塔尔，生下一子后去世；最后，洛塔尔与贝莎结婚并生下女儿杰玛。那么，盖乌斯的儿子能否合法地与杰玛的女儿结婚？

图形静力学的发展

17世纪末，法国数学家皮埃尔·瓦里尼翁在前人西蒙·斯蒂文工作的基础上，发展出一种图形方法，用于求解受张力作用的树状绳索网络的平衡位置。瓦里尼翁观察到，当绳索处于平衡状态时，可以绘制一张图，其边段分别平行于各根绳索，长度等于对应绳索上的张力，且网络中任一点交汇的绳索会在图中形成闭合回路。瓦里尼翁的图形静力学方法直到1725年才在他去世两年后才完整发表。这类图现在被称为互易力图或麦克斯韦-克雷莫纳图，以詹姆斯·克拉克·麦克斯韦和朱利奥·克雷莫纳命名，他们在19世纪后期（与卡尔·库尔曼等人一起）建立了互易图的丰富理论体系。

下图展示了来自瓦里尼翁遗作《新力学或静力学》（Nouvelle mécanique, ou statique, dont le projet fut donné en MDCLXXXVII，即1687年提出项目）中的互易力图（虚线部分）。

当然，还有许多其他常见的图的例子：棋盘游戏（可追溯至古代）；凸多面体的顶点与边（由古希腊哲学家正式研究，但远早于此）；星象图案的可视化（早在公元7世纪东亚已有发展）；骑士巡游问题（由阿勒-阿德利、鲁德拉塔、阿勒-苏里等人在9至10世纪描述）；迷宫（以现代形式由乔瓦尼·丰塔纳约在1420年引入）；大地测量三角测量（由吉马·弗里斯尤斯于1533年提出，后被威勒布罗德·斯内尔于1615年用于测算地球周长，并于1799年用于定义“米”的标准）；莱昂哈德·欧拉著名的关于柯尼斯堡七桥问题的部分解法（1735年）；电报及其他通信网络（最早于1753年提出，由罗纳兹、施林、高斯、韦伯等人在19世纪初发展，于19世纪末实现全球部署）；电路系统（由欧姆、麦克斯韦、基尔霍夫等人在19世纪初正式建立）；分子结构式（由奥古斯特·凯库勒于1857年独立提出，阿奇博尔德·库珀于1858年独立提出）；社交网络（由社会学家雅各布·莫诺在1930年代中期首次研究）；数字电子电路（由查尔斯·桑德斯·皮尔士于1886年提出构想，后由克劳德·香农于1937年确立为现代形式）；当然，如果你坚持的话，还包括现代互联网。

图论关键发展的历史

“图”这一术语用于指代抽象数学结构，是由詹姆斯·西尔维斯特于1878年提出的。他根据同事威廉·克利福德的建议，借鉴凯库勒的“化学图”概念，将其用于描述某些代数不变量。而“树”这一术语首次用于表示连通无环图，是由阿瑟·凯莱于1857年提出的，尽管在此之前，古斯塔夫·基尔霍夫和卡尔·冯·施陶特已在十年前就已使用过这一抽象概念。第一本图论专著由安德烈·圣特-拉居于1926年出版；十年后，丹尼·柯尼希出版了第一本系统的图论教科书。