图论及其应用25708

《图论及其应用25708》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9卷第2期重庆科技学院学报(自然科学版)2007年6月图论及其应用燕子宗张宝琪(长江大学,荆州434000)摘要:图论从诞生至今已近300年,但很多问题一直没有很好地解决。随着计算机科学的发展,图论又重新成为了人们研究讨论的热点,这里给出图论在现实生活中的一些应用。关键词:欧拉;图论;二分图;哈密顿回路;着色中图分类号:O157文献标识码:A文章编号:1673-1980(2007)02-0121-03在18世纪30年代,一个非常有趣的问题引起类图被称作二分图,经常应用在涉及匹配的问题中。了欧洲数学家

2、的浓厚兴趣,这个问题要求遍历普鲁例如,某公司现在正经历一次罢工,为了使公司在罢士的哥尼斯堡七桥中的每一座桥恰好一次后回到出工中照常运作,人事部确定了4项关键工作:销售、发点。欧拉证明了这是不可能完成的,此后,欧拉发维修、安全控制和会计,其中销售需要2人。表1给表了著名的论文《依据几何位置的解题方法》,这是出了每个人和他们能胜任的工作,判断是否所有工图论领域的第一篇论文,标志着图论的诞生。图论作都能有人来负责,设每人只能负责一项工作。的真正发展始于20世纪五六十年代之间,是一门既表1每个人与他们胜任的工

3、作古老又年轻的学科。A会计、销售图论极有趣味性,严格来讲它是组合数学的一B销售、安全控制个重要分支。虽然图论只是研究点和线的学问,但C销售、安全控制、维修其应用领域十分广阔,不仅局限于数学和计算机学D维修E安全、维修科,还涵盖了社会学、交通管理、电信领域等等。总的来说,图论这门学科具有以下特点:这看起来是社会学领域的问题,我们可以尝试①图论蕴含了丰富的思想、漂亮的图形和巧妙多种方法,而其中的一种方法就是将其化为图,建立的证明;一个图的模型。最基本的问题是如何描述它,什么是②涉及的问题多且广泛,问题外表

4、简单朴素,结点,什么是边?在本问题中,没有太多的选择,只有本质上却十分复杂深刻;人和工作。我们可试着用集合X中的结点来代表③解决问题的方法千变万化,非常灵活,常常人,用集合Y中的结点来代表工作。用边来代表图是一种问题一种解法。中结点之间的关系,在这里结点之间的关系是“人能由以上三个特点可以看出,图论与其它的数学否胜任工作”,因此,若某人能胜任工作,那么就在两分支不同,它不像群论、拓扑等学科那样有一套完整个结点之间加上一条边。由于销售需要2人,所以用的理论体系和解决问题的系统方法。而且图论所研2个结点S

5、1和S2来表示。如此得到二分图(Ⅰ),究的内容非常广泛,例如图的连通性、遍历性、图的(Ⅱ)给出了最大匹配,很容易看出每一项工作都有计数、图的着色、图的极值问题、图的可平面性等等。ABCDEABCDE集合X集合X1集合Y集合Y二分图aS1S2sraS1S2srⅠⅡ有一类非常重要的图,如树,它是图的特例,这图1每个人与他们胜任的工作二分图收稿日期:2007-01-04作者简介:燕子宗(1964-),男,湖北荆州人,博士,长江大学信息与数学学院副教授,从事最优化理论的教学与研究。·121·燕子宗,张宝琪:图

6、论及其应用人来负责。所有元素互不相邻。这类问题中比较常见的有:安排会议或考试的日程以免冲突,还有安排化学品的存2哈密顿回路储以避免互相反应。图论中许多理论和实际问题都需要我们以某例如一名设计师为实验室设计化学药品存储仓种方法遍历整个图。例如在某些问题中,我们的目库,希望建造尽量少的存储间。已知某些药品之间会标是求出一条迹或回路,满足经过每条边一次且仅起反应,不能存储在一起。作为简化,我们用字母a一次;在另一些问题中,我们可能需要求出一条路到n代表14种化学品;两种化学品之间的边代表它或圈,满足经过每个

7、结点一次且仅一次。其中最著们可能起化学反应,如图4。求所需最少存储间,并名的两个问题莫过于“旅行商”问题和“中国邮路”指出每种药品放入哪个存储间。问题。aafk例如:举行一个国际会议,有A,B,C,D,E,F,Gl7个人。已知下列事实:mbegjA会讲英语;hcB会讲英语和汉语;C会讲英语、意大利语和俄语;Ddln会讲日语和汉语;E会讲德语和意大利语;图3可能的化学反应示意图F会讲法语、日语和俄语;虽然图看起来很复杂,似乎色数会有爆炸性增G会讲法语和德语。长,但实际上很容易就可以验证图4的色数等于3,

8、试问这7个人应如何排座位,才能使每个人都而且图4是可唯一三着色的。在将图中的一个K3用能和他身边的人交谈?3种不同颜色着色之后,我们可以继续移动到与该我们还是用图来解决这个问题。依然是建立一K3相邻的结点为,如果这个结点的颜色已经唯一确个图的模型,确定结点和边。这里有“人和语言”,那定,我们就能继续处理直到完成整个过程。图4的唯么我们用结点来代表人,于是结点集合V={A,B,C,一三着色图使用了粉红(p)、褐色(t)和白色(w)。所D,E,F,G}对于任