图论是近几十年发展起来的一门应用十分广泛的运筹学分.docx

第九章 图论 图论是近几十年发展起来的一门应用十分广泛的运筹学分支，它已被广泛地应 用于物理学、化学、控制论、信息论、管理科学、计算机等各个领域。由于其应用 领域的广泛性，图论受到了社会各界的广泛重视。 图论思想的出现，可以追溯到 1736 年欧拉 （Euler ）发表的一篇关于 哥尼斯堡 （K?nigsberg）七桥问题的论文。为对图论思想的产生有一直观的认识，以对后续 的学习有些帮助，在此先介绍几个在古典图论中具有重要影响的经典问题。 1．欧拉 （Euler） 回路问题 哥尼斯堡是东普鲁士的一座城市，第二次世界大战后划归苏联，也就是现在的 加里宁格勒。 Pregel 河流经此城市，河中有两个孤岛，两岸与两岛之间有七座桥相 连，如图 9-1 所示。当时那里的居民热衷于这样一个问题：从一个点出发，能否通 过每座桥一次且仅一次，最后回到原来的出发点？ 这个问题的提出虽是出自游戏，但它的思想却有着重大的意义。由于 EuIer 率 先解决了这一问题，故称其为 Euler 回路问题。 EuIer 把图 9-1 抽象为图 9-2，用 A、 B 、C 、 D 四点分别表示两岸和两岛，两点间的连 线 表示沟通它们的桥梁；因此，问 题转化为从 A 、 B 、C 、 D 中任一点出发，通过每条边一次且仅一次，最后回到原出 发点，问这样的路径是否存在？于是问题变得简洁多了。 A Pregel C D 图 9-1 B 图 9-2 欧拉证明了这样的路径是不存在的，因为图 9-2 中的每一个点都只与奇数条线 相关联，所以不可能不重复地一笔画出这个图。我们也可以这样来分析，对于开始 的点，有一“去”就必然有一“回” ，一去一回构成偶数条关联边；对于中间的点， 有一“来”就必然有一“去” ，一来一去也构成偶数条关联边；所以实现这样的路径 要求图 9-2 中的每一个点都有偶数条关联边。显然，图 9-2 中的点不满足这样的要 求，所以这样的路径不存在。 2．雷姆塞（ Ramsey）问题 雷姆塞问题是这样的：任意 6 个人在一起，如果不存在单方认识，那么 6 人中 205 要不是有 3 人彼此相互认识，必有 3 人互不相识；即二者必居其一。 用图的办法很容易给 Ramsey 问题以证明。设 v1 、 v2 、 v3 、 v4 、 v5 、 v6 分别 代表这 6 个人。相互认识的两个人对应的顶点用 实线相连 ，互不相识的两个人对应 的顶点用 虚线相连 。因为两个人要么相互认识，要么互不相识，所以任意一点与其 它 5 个点都有一线相连，或是 实线 或是 虚线 ；这样问题便转化为在由此所得的 6 点 图中，至少存在一个由 实线 或虚线 所构成的 三角形 。 任意取一个点 vt （t {1,2,3,4 ,5 ,6} ），它与其它 5 个点的 5 条连线中至少有 3 条同为实线或同为虚线。 不妨假设有 3 条同为实线， 且另一端点分别为 vi 、vj 和 vk 。 如图 9-3 所示， 如果 vi 、 vj 和 vk 这 3 个顶点形成的三角形一定是虚线三角形， 那么 问题得到证明；如果不然，那么由 vi 、 vj 和 vk形成的三角形就至少有一条实线边， 不妨设为 vi vk ，则由 vt 、 vi 和 vk形成的三角形就一定是实线三角形，问题同样也 得到证明。 vi vt vk v j 图 9-3 图 9-4 3．哈米尔顿（ Hamilton ）回路问题 在图 9-4 中 20 个顶点分别表示世界的 20 个名城。两点之间的连线表示两城市 间的航线， Hamilton 回路问题要求从某一城市出发，遍历各城市一次且仅一次，最 后返回原来的出发地。因 Hamil