基础图算法简介与历史

图的历史

图 是成对元素的集合——整数对、人与人之间、城市之间、恒星之间、国家之间、科学论文之间、网页之间、博弈局面之间、递归子问题之间，甚至图与图之间的配对。在可视化图时，最常用的方法是映射表示法：通常将被配对的基本对象称为顶点或节点，而这些配对关系本身则被称为边或弧。但实际上，这些对象和配对可以是任意类型的实体。

图的最早应用之一是道路网络及其地图表示。在罗马帝国鼎盛时期，罗马工程师在整个欧洲、西亚和中亚以及北非地区修建了总长超过40万公里的公共道路网。旅行者在路途中会携带行程记录，这些记录可能是简单的列表，也可能是对沿途地标和距离更为形象化的描绘。《佩廷格地图》（Tabula Peutingeriana）是一份13世纪的手卷，描绘了整个罗马帝国的“公共驿道系统”，普遍认为它是对5世纪修订版的一次中世纪复制，而该5世纪版本又源自奥古斯都·凯撒统治时期委托制作的公元1世纪的“图像行程表”（itinerarium pictum）。佩廷格地图并非地理上精确的地图——历史学家甚至争论它是否真正算得上一张“地图”！——但它是一种对道路网络的高度抽象表达，类似于现代地铁线路图。每条道路上的城市通过代表道路的曲线上的折点来表示；同时地图上还标注了这些城市的名称以及相邻城市之间的路段长度。因此，这张地图包含了足够的信息，可用于找出5世纪罗马帝国任意两座城市之间的最短路线。见下图。

下图是康拉德·米勒（Konrad Miller）于1872年复原的《佩廷格地图》的一小部分，展示了从现代比尔滕（Veteribus，左上角）经科隆（Agripina）、波恩（Bonnae）到美因茨（Mogontiaco，右上角）的罗马道路，并分出通往特里尔（Avg Tresvirorvm，中部）和梅斯（Matricorvm，底部中央）的支线。

图的一个古老经典应用——特别是树结构——体现在家谱的表示中。复杂的家族“树”已被使用数百年，用于解决婚姻、继承权和王位继承等法律问题。罗马帝国的民法后来被早期天主教会采纳为教会法，其中禁止近亲（如堂兄妹或更近亲属）结婚。到了九世纪初，教会改变了所需亲缘距离的计算方式：原先罗马的“法定计算法”（computatio legalis）要求双方到最近共同祖先的距离之和至少为四，而新的“教会计算法”（computatio canonica）则要求两者中较大的距离至少为七。1215年，出于实际考虑（以及现实中的普遍做法），教会将结婚所需的最小亲缘距离放宽至四。下图左侧展示了一个特别复杂的情况：提里乌斯（Tirius）与特博尔嘉（Theburga）结婚并生下儿子盖乌斯（Gaius），之后提里乌斯去世；特博尔嘉改嫁洛塔尔（Lothar），为其生下一子后去世；最后洛塔尔与贝尔莎（Bertha）结婚并育有一女杰玛（Gemma）。那么，盖乌斯的儿子能否合法迎娶杰玛的女儿？

图示静力学的发展

17世纪末，法国数学家皮埃尔·瓦里尼翁（Pierre Varignon）发展了一种用图形方法求解受张力作用的树状绳索网络平衡位置的技术，其基础是西蒙·斯特芬（Simon Stevin）一个世纪前发表的研究成果。瓦里尼翁观察到，当绳索处于平衡状态时，可以画出一个图，其边是与各段绳索方向平行的线段，长度等于对应绳索中的张力大小，使得网络中交汇于同一点的所有绳索在图中形成一个闭合回路。他的这种“图示静力学”方法直到1725年才完整发表，此时已是其去世两年之后。这类图如今被称为互易力图或麦克斯韦-克雷莫纳图（Maxwell-Cremona diagrams），以纪念詹姆斯·克拉克·麦克斯韦（James Clerk Maxwell）和路易吉·克雷莫纳（Luigi Cremona），他们在19世纪后期（与卡尔·库尔曼等人一起）发展了一套丰富的互易图理论。

当然，还有许多其他常见的图的例子：棋盘游戏（可追溯至古代）；凸多面体的顶点与边（由古希腊哲学家正式研究，但起源更早）；星象图案的可视化（公元7世纪东亚已有发展）；骑士周游问题（9至10世纪由al-Adli、Rudrat.a、al-Suli等人描述）；迷宫（约1420年由乔瓦尼·丰塔纳以现代形式引入）；大地测量三角网（1533年由格玛·弗里修斯引入，1615年维勒布罗德·斯涅尔用其计算地球周长，1799年用于定义米制单位）；欧拉著名的柯尼斯堡七桥难题的部分解答（1735年）；电报及其他通信网络（1753年首次提出，19世纪初由罗纳兹、希林、高斯、韦伯等人发展，并于19世纪末实现全球部署）；电路（19世纪初由欧姆、麦克斯韦、基尔霍夫等人形式化）；分子结构式（1857年由奥古斯特·凯库勒独立提出，1858年由阿奇博尔德·库珀提出）；社交网络（1930年代中期由社会学家雅各布·莫雷诺首次研究）；数字电子电路（1886年由查尔斯·桑德斯·皮尔士提出，1937年由克劳德·香农确立现代形式）；当然，如果需要的话，还包括现代互联网。

图论关键概念的发展历史

“图”这一术语作为抽象数学概念，是由詹姆斯·西尔维斯特（James Sylvester）于1878年提出的，他借鉴了凯库勒的“化学图”（chemicographs），并在同事威廉·克利福德的建议下，将其用于描述某些代数不变量。“树”一词最早由阿瑟·凯莱（Arthur Cayley）于1857年用于指代无环连通图，尽管在此之前十年，古斯塔夫·基尔霍夫和卡尔·冯·施陶特已实际使用了树的抽象概念。第一本关于图论的著作由安德烈·圣-拉盖（André Sainte-Laguë）于1926年出版；十年后，德内什·柯尼希（Dénes Kőnig）出版了第一部系统的图论专著。