维普资讯 http://www.cqvip.com 第９卷第２期 重庆科技学院学报（自然科学版） ２００７年６月 图论及其应用 燕子宗张宝琪 （长江大学，荆州４３４０００） 摘要：图论从诞生至今已近３００年，但很多问题一直没有很好地解决。随着计算机科学的发展，图论又重新成为了人 们研究讨论的热点，这里给出图论在现实生活中的一些应用。 关键词：欧拉；图论；二分图；哈密顿回路；着色 中图分类号：０１５７ 文献标识码：Ａ 文章编号：１６７３—１９８０（２００７）０２—０１２１—０３ 在１８世纪３０年代，一个非常有趣的问题引起 了欧洲数学家的浓厚兴趣，这个问题要求遍历普鲁 士的哥尼斯堡七桥中的每一座桥恰好一次后回到出 发点。欧拉证明了这是不可能完成的，此后，欧拉发 类图被称作二分图，经常应用在涉及匹配的问题中。 例如。某公司现在正经历一次罢工，为了使公司在罢 工中照常运作。人事部确定了４项关键工作：销售、 维修、安全控制和会计，其中销售需要２人。表１给 出了每个人和他们能胜任的工作．判断是否所有工 表了著名的论文《依据几何位置的解题方法》，这是 图论领域的第一篇论文，标志着图论的诞生。图论 的真正发展始于２０世纪五六十年代之间，是一门既 古老又年轻的学科。 作都能有人来负责，设每人只能负责一项工作。 表１每个人与他们胜任的工作 会计、销售 销售、安全控制 图论极有趣味性。严格来讲它是组合数学的一 个重要分支。虽然图论只是研究点和线的学问，但 销售、安全控制、维修 维修 其应用领域十分广阔，不仅局限于数学和计算机学 科。还涵盖了社会学、交通管理、电信领域等等。总 的来说．图论这门学科具有以下特点： 安全、维修 这看起来是社会学领域的问题。我们可以尝试 多种方法。而其中的一种方法就是将其化为图，建立 一①图论蕴含了丰富的思想、漂亮的图形和巧妙 的证明； 个图的模型。最基本的问题是如何描述它，什么是 ②涉及的问题多且广泛，问题外表简单朴素， 本质上却十分复杂深刻； 结点，什么是边？在本问题中，没有太多的选择，只有 人和工作。我们可试着用集合 中的结点来代表 ③解决问题的方法千变万化，非常灵活，常常 是一种问题一种解法。 人．用集合ｙ中的结点来代表工作。用边来代表图 中结点之间的关系，在这里结点之间的关系是“人能 否胜任工作”。因此，若某人能胜任工作，那么就在两 个结点之间加上一条边。由于销售需要２人，所以用 ２个结点．ｓ 和．ｓ 来表示。如此得到二分图（Ｉ）， 由以上三个特点可以看出。图论与其它的数学 分支不同。它不像群论、拓扑等学科那样有一套完整 的理论体系和解决问题的系统方法。而且图论所研 究的内容非常广泛。例如图的连通性、遍历性、图的 计数、图的着色、图的极值问题、图的可平面性等等。 （ＩＩ）给出了最大匹配，很容易看出每一项工作都有 Ｂ Ｃ Ｄ Ｅ Ａ Ｂ Ｃ Ｄ Ｅ １二分图 有一类非常重要的图，如树，它是图的特例，这 收稿日期：２００７—０１—０４ ０ Ｓｌ ｓ ｒ ０ Ｓｌ Ｓ２ ｓ Ｉ Ⅱ 图１每个人与他们胜任的工作二分图 作者简介：燕子宗（１９６４一），男，湖北荆州人，博士，长江大学信息与数学学院副教授，从事最优化理论的教学与研究。 ?１２１? 维普资讯 http://www.cqvip.com 燕子宗。张宝琪：图论及其应用 人来负责。 所有元素互不相邻。这类问题中比较常见的有：安排 会议或考试的日程以免冲突，还有安排化学品的存 储以避免互相反应。 例如一名设计师为实验室设计化学药品存储仓 库。希望建造尽量少的存储问。已知某些药品之间会 起反应，不能存储在一起。作为简化，我们用字母口 到／７．代表１４种化学品；两种化学品之间的边代表它 ２哈密顿回路 图论中许多理论和实际问题都需要我们以某 种方法遍历整个图。例如在某些问题中，我们的目 标是求出一条迹或回路，满足经过每条边一次且仅 一次；在另一些问题中，我们可能需要求出一条路 或圈。满足经过每个结点一次且仅一次。其中最著 们可能起化学反应，如图４。求所需最少存储问，并 名的两个问题莫过于“旅行商”问题和“中国邮路” 问题 例如：举行一个国际会议，有Ａ， ｃ， Ｅ Ｇ ７个人。已知下列事实： Ａ会讲英语； 会讲英语和汉语； Ｃ会讲英语、意大利语和俄语； Ｄ会讲日语和汉语； Ｅ会讲德语和意大利语； Ｆ会讲法语、日语和俄语； 会讲法语和德语。 试问这７个人应如何排座位，才能使每个人都 能和他身边的人交谈？ 我们还是用图来解决这个问题。依然是建立一 个图的模型，确定结点和边。这里有“人和语言”，那 么我们用结点来代表人，于是结点集合Ｖ＝ ， ｅ Ｄ，Ｅ Ｇ１对于任意的两点，若有共同语言，就在它 们之间连一条无向边，可得边集Ｅ，图Ｇ＝（Ｖ，Ｅ），如 下图： Ｇ 图２座位安排模型图 如何排座位使每个人都能和他身边的人交谈？ 问题转化为在图Ｇ中找到一条哈密顿回路的问题 ｒ哈密顿回路即是通过每个结点一次且仅一次的回 路）。而Ａ—Ｂ—Ｄ— Ｇ—Ｅ—Ｃ 即是图中的一条哈密 顿回路。照这个顺序排座位就可以解决问题了。 ３着色问题 许多由图论描述的现实问题都需要把结点集 或边集划分为一些不相交的子集，使同一子集中的 ?１２２? 指出每种药品放人哪个存储间。 图３可能的化学反应示意图 虽然图看起来很复杂。似乎色数会有爆炸性增 长，但实际上很容易就可以验证图４的色数等于３， 而且图４是可唯一三着色的。在将图中的一个Ｋ 用 ３种不同颜色着色之后。我们可以继续移动到与该 Ｋ 相邻的结点为，如果这个结点的颜色已经唯一确 定．我们就能继续处理直到完成整个过程。图４的唯 一三着色图使用了粉红（ｐ）、褐色（ｔ）和白色（Ｗ）。所 以可以得知，总共需要三问存储间，化学品将按如下 方案存储：在粉红存储间中，我们存储ｆ、ｈ、 、ｋ和ｌ； 在褐色存储问中，我们放置ｂ、ｄ、ｅ、ｍ和／７．；在白色 存储问中安排口、ｃ、ｇ和 。 图４图３的唯一三着色图 如果能在平面内将图画出且使其边各不相交 叉．那么这个图就是可平面化的。可平面图曾经受到 了多年的广泛关注，其原因在于一个长期困惑人们 的问题“四色猜想”。这个问题描述起来很简单，就是 能否只用四种颜色来着色平面图，相邻的部分颜色 要不相同，但最终花费了１００多年的时间才得到证 明，证明最终公布于１９７７年，当时引起了强烈反响， 维普资讯 http://www.cqvip.com 燕子宗．张宝琪：图论及其应用 国为这是第一个广泛利用计算机做出的证明。现如 今，可平面图在其应用领域仍然占有很重要的地位． 例如场地布局或是电路板设计等。 院出版社．１９８８． 参考文献 ［１】舒贤林，徐志才．图论基础及其应用［Ｍ】．北京：北京邮电学 ４结论 从上面的例子我们可以看出，图论的应用十分 ［２】张先迪，李正良．图论及其应用［Ｍ】．北京：高等教育出版 社．２００５． ［３】谢政，戴丽，陈挚．关于图论课教学的思考［Ｊ１．数学理论与应 广泛，如果我们在学习的过程中能打下坚实的基础， 用，２００５，２５（４）． 就有能力将图论的思想应用到纷乱复杂的现实问题 ［４】Ｂｕｃｋｌｅｙ，Ｆ．Ｌｅｗｉｎｔｅｒ，Ｍ．Ａ Ｆｒｉｅｎｄｌｙ Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ Ｇｒａｐｈ 中去。 Ｔｈｅｏｒｙ［Ｍ］．Ｂｅｉｊｉｎｇ：Ｔｓｉｎｇｈｕａ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ，２００５． Ｏｎ Ｇｒａｐｈ Ｔｈｅｏｒｙ ａｎｄ Ｉｔｓ Ａｐｐｌｉｃａｔｉｏｎ ＹＡＮＺｉ－ｚｏｎｇ ＺＨＡＮＧＢａｏ－ｑｉ （Ｙａｎｇｔｚｅ Ｕｎｉｖｅｒｓｉｔｙ，Ｊｉｎｇｚｈｏｕ ４３４０２３） Ａｂｓｔｒａｃｔ：Ｇｒａｐｈ ｔｈｅｏｒｙ ｈａｓ ａｒｏｕｎｄ ３００ ｙｅａｒｓ ｏｆｈｉｓｔｏｒｙ，ｂｕｔ ｍａｎｙ ｐｒｏｂｌｅｍｓ ｈａｖｅｎ’ｔ ｂｅｅｎ ｓｏｌｖｅｄ．Ｗｉｔｈ ｔｈｅ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ，ｇｒａｐｈ ｔｈｅｏｒｙ ｂｅｃｏｍｅｓ ｈｏｔ ｐｏｉｎｔ ａｇａｉｎ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｔｈｅ ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｇｒａｐｈ ｔｈｅｏｒｙ ｉｓ ｄｉｓｃｕｓｓｅｄ． Ｋｅｙ ｗｏｒｄｓ：Ｅｕｌｅｒ；ｇｒａｐｈ ｔｈｅｏｒｙ；ｅｑｕｉｎｏｃｔｉａｌ ｇｒａｐｈ；Ｈａｍｉｌｔｏｎ’Ｓ ｃｉｒｃｕｉｔ；ｄｙｅ （上接第１１０页） Ａｎ Ｉｍｐｒｏｖｅｄ Ｆａｓｔ Ｓｅａｒｃｈ Ａ１ｇｏｒｉ廿ｕｎ ＺＨＯＵ Ｈｏｎｇ 。ＷＵＭｉｎｇ－ｆａｎｇａ （１．Ｃｈｏｎｇｑｉｎｇ Ｕｎｉｖｅｒｓｉｙｔ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈｏｎｇｑｉｎｇ ４０００５０； ２．Ｃｈｏｎｇｑｉｎｇ Ｕｎｉｖｅｒｓｉｙｔ，Ｃｈｏｎｇｑｉｎｇ ４０００４４） Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｐｕｔｓ ｆｏｒｗａｒｄ ｔｏ ｔｈｅ ｈ ｅｘａｇｏｎ ｓｅａｒｃｈ ａｒｉｔｈｍｅｔｉｃ ｗｉｔｈ ｓｅｌｆ－ａｄａｐｔａｔｉｏｎ，ｗｈｉｃｈ ｉｎｃｌｕｄｅｓ ｍａｉｎ ｔｅｃｈｎｉｑｕｅｓ ｓｕｃｈ ａｓ ｄｉｆｅｒｅｎｔｉａｔｉｏｎ ｏｆ ｚｅｒｏ ｍｏｖｅｍｅｎｔ ｖｅｃｔｏｒ ｂｅｆｏｒｅｈａｎｄ，ｅｎａｃｔｍｅｎｔ ｖａｌｕｅ ｏｆ ｓｔｉｌＩｎｅｓｓ ｔｏ ｔｅｒｍｉｎａｔｅ ｍｏｖｅｍｅｎｔ ｅｓｔｉｍａｔｅ，ｕｓｉｎｇ ｓｐａｃｅ ａｎｄ ｔｉｍｅ ｂｏｒｄｅｒ ｐｉｅｃｅ ｔｏ ｅｓｔｉｍａｔｅ ｔｈｅ ｍｏｖｅｍｅｎｔ ｔｙｐｅ ｃｕｒｒｅｎｔｌｙ，ｃｈｏｏｓｉｎｇ ｓｔａｒｔｉｎｇ ｐｏｉｎｔ ｗｉｔｈ ｓｅｌｆ－ａｄａｐｔａｔｉｏｎ ｂａｓｅｄ ｏｎ ｍｏｖｅｍｅｎｔ ｔｙｐｅ ａｎｄ ｓｅａｒｃｈ ｓｔｒａｔｅｇｙ ｉｎｔｅｇｒａｔｅｄ ｈｅｘａｇｏｎ ｓｅａｒｃｈ ａｒｉｔｈｍｅｔｉｃ ａｎｄ ｄｉａｍｏｎｄ—ｓｈａｐｅｄ ｓｅａｒｃｈ ａｒｉｔｍｈｅｔｉｃ．Ｔｈｅ ｒｅｓｕｌｔ ｏｆ ｅｘｐｅｒｉｍｅｎｔ ｄｅｍｏｎｓｔｒａｔｅｓ ｔｈａｔ ｔｈｅ ａｒｉｔｍｈｅｔｉｃ ｄｅｃｒｅａｓｅｓ ｈｔｅ ｓｅａｒｃｈ ｃｏｕｎｔ ｎｕｍｂｅｒ ｅｆｆｅｃｔｉｖｅｌｙ，ｔｈｅ ｐｒｅｃｉｓｉｏｎ ｉｓ ｒｅｌａｔｉｖｅｌｙ ｃｌｏｓｅ ｔｏ ＦＳ ａｒｉｔｈｍｅｔｉｃ，ａｎｄ ｓｅａｒｃｈ ｅｆｉｆｃｉｅｎｃｙ ｉｓ ｉｍｐｒｏｖｅｄ ｉｎ ｓｏｍｅ ｄｅｇｒｅｅ． Ｋｅｙ ｗｏｒｄｓ：ｖｉｄｅｏ ｃｏｍｐｒｅｓｓｉｏｎ；ｍｏｔｉｏｎ ｅｓｔｉｍａｔｉｏｎ；ｑｕｉｃｋ—ｈｕｎｔｉｎｇ （上接第１１８页） Ｎｅｗｔｏｎ Ｉｔｅｒａｔｉｖｅ Ｍｅｔｈｏｄ ｆｏｒ ａ Ｎｏｎｌｉｎｅａｒ Ｐｒｏｂｌｅｍｓ ｏｆ Ｉｎｆｉｌｔｒａｔｅｓ Ｓｕｒｆａｃｅ ｉｎ Ｈｅａｐ Ｌｅａｃｈｉｎｇ Ｐｒｏｃｅｓｓ ＵＺｈｕａｎ—ｂａｏ ＸＵＤａ （Ｈｕｎａｎ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｙｔ，Ｃｈａｎｇｓｈａ ４ １ ００８ １） Ａｂｓｔｒａｃｔ：Ｔｏ ｓｔｕｄｙ ｔｈｅ ｍｅｃｈａｎｉｓｍ ｏｆ ｈｅａｐ ｌｅａｃｈｉｎｇ ｐｒｏｃｅｓｓ，Ｎｅｗｔｏｎ ｉｔｅｒａｔｉｖｅ ｍｅｔｈｏｄ ｉｓ ａｐｐｌｉｅｄ ｔｏ ｆｉｎｄ ｔｈｅ ｓｏｌｕ— ｔｉｏｎ ｆｏｒ ｎｏｎｌｉｎｅａｒ ｉｎｆｉｌｔｒａｔｅｓ ｓｕｒｆａｃｅ ｅｑｕａｔｉｏｎ．Ｔｈｅ ｅｒｒｏｒ ｒｅａｃｈｅｓ ａｆｔｅｒ １ ４ ｉｔｅｒａｔｉｏｎｓ ＳＯ ｔｈａｔ ｉｔ Ｃａｎ ｐｒｏｖｅ ｈｔｉｓ ｃｏｎｖｅｒ— ｇｅｎｃｅｉｓ ｅｆｆｅｃｔｉｖｅ． 誊 Ｋｅｙ ｗｏｒｄｓ：Ｎｅｗｔｏｎ ｉｔｅｒａｔｉｖｅ ｍｅｔｈｏｄ；ｎｏｎｌｉｎｅａｒ ｐｒｏｂｌｅｍ；ｉｎｆｉｌｔｒａｔｅｓ ｓｕｒｆａｃｅ ?１２３?
图论及其应用
