第五章 图的基本概念 图论起源于1736年欧拉(Enler) 的第一篇 图论 论文, 解决了“哥尼斯堡的七桥问题” 。在哥尼斯堡的匹格河上有七座桥,如图 所示。 当时人们热衷于这样的游戏：设想从任一 个地方出发通过每座桥一次且仅一次后回 到原地, 这是否可能?但多次实践都发现不 行 1727 年欧拉的朋友向欧拉提出了这个问题 是否有解？ 1736 年欧拉用图论的方法解决了这个问题 ,写了第一篇图论的论文,成为图论的创始 人。 后来称此问题为哥尼斯堡七桥问题。 在图a中,用边表示桥,顶点表示岛屿和河的 两岸,便得到一个图,如图b 所示。 很显然,通过哥尼斯堡 七座桥中每一座一次 且仅一次的问题等价 于在图5.13 (b) 中找一 条闭链, 使得它的每一边出现 一次且仅一次, 也就是 如何一笔画的问题。 但在此之后100年间，没有大的进展。 直到Kirchhoff( 克希霍夫) 用树的理论解决了电网络问题 ， 1857年Cayler( 凯莱) 用统计不同构树的方法来计算 C n H 2n+1 同分异构体数目, 这些结果引起了人们的重视,图论的研究进入了一个发展 时期, 在此期间,出现了两个
