教育论文图论应用问题探析

《教育论文图论应用问题探析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、图论应用问题探析图论应用问题探析是小柯论文网通过网络搜集，并由本站工作人员整理后发布的，图论应用问题探析是篇质量较高的学术论文，供本站访问者学习和学术交流参考之用，不可用于其他商业目的，图论应用问题探析的论文版权归原作者所有，因网络整理，有些文章作者不详，敬请谅解，如需转摘，请注明出处小柯论文网，如果此论文无法满足您的论文要求，您可以申请本站帮您代写论文，以下是正文。　　[摘要]图论从诞生至今已近300年，但很多问题一直没有很好地解决。随着计算机科学的发展，图论又重新成为了人们研究讨论的热点，这里给出图论在现实生活中的一些应用。　　[关键词]欧拉图论二分图哈密顿回路着色　　　　在18世纪30

2、年代，一个非常有趣的问题引起了欧洲数学家的浓厚兴趣，这个问题要求遍历普鲁士的哥尼斯堡七桥中的每一座桥恰好一次后回到出发点。欧拉证明了这是不可能完成的，此后，欧拉发表了著名的论文《依据几何位置的解题方法》，这是图论领域的第一篇论文，标志着图论的诞生。图论的真正发展始于20世纪五六十年代之间，是一门既古老又年轻的学科。　　图论极有趣味性，严格来讲它是组合数学的一个重要分支。虽然图论只是研究点和线的学问，但其应用领域十分广阔，不仅局限于数学和计算机学科，还涵盖了社会学、交通管理、电信领域等等。总的来说，图论这门学科具有以下特点：图论蕴含了丰富的思想、漂亮的图形和巧妙的证明；涉及的问题多且广泛，问题

3、外表简单朴素，本质上却十分复杂深刻；解决问题的方法千变万化，非常灵活，常常是一种问题一种解法。由以上三个特点可以看出，图论与其他的数学分支不同，它不像群论、拓扑等学科那样有一套完整的理论体系和解决问题的系统方法。而且图论所研究的内容非常广泛，例如图的连通性、遍历性、图的计数、图的着色、图的极值问题、图的可平面性等等。　　　　一、二分图　　　　有一类非常重要的图，如树，它是图的特例，这类图被称作二分图，经常应用在涉及匹配的问题中。例如，某公司现在正经历一次罢工，为了使公司在罢工中照常运作，人事部确定了4项关键工作：销售、维修、安全控制和会计，其中销售需要2人。表中给出了每个人和他们能胜任的工作

4、，判断是否所有工作都能有人来负责，设每人只能负责一项工作。　　这看起来是社会学领域的问题，我们可以尝试多种方法，而其中的一种方法就是将其化为图，建立一个图的模型。最基本的问题是如何描述它，什么是结点，什么是边？在本问题中，没有太多的选择，只有人和工作。我们可试着用集合X中的结点来代表人，用集合Y中的结点来代表工作。用边来代表图中结点之间的关系，在这里结点之间的关系是”人能否胜任工作”，因此，若某人能胜任工作，那么就在两个结点之间加上一条边。由于销售需要2人，所以用2个结点S1和S2来表示。如此得到二分图1，2给出了最大匹配，很容易看出每一项工作都有人来负责。　　　　二、哈密顿回路　　　　图论

5、中许多理论和实际问题都需要我们以某种方法遍历整个图。例如在某些问题中，我们的目标是求出一条迹或回路，满足经过每条边一次且仅一次;在另一些问题中，我们可能需要求出一条路或圈，满足经过每个结点一次且仅一次。其中最著名的两个问题莫过于“旅行商”问题和“中国邮路”问题。　　例如：举行一个国际会议，有A，B，C，D，E，F，G7个人。已知下列事实：A会讲英语；B会讲英语和汉语；C会讲英语、意大利语和俄语；D会讲日语和汉语；E会讲德语和意大利语；F会讲法语、日语和俄语；G会讲法语和德语。试问这7个人应如何排座位，才能使每个人都能和他身边的人交谈？我们还是用图来解决这个问题。依然是建立一个图的模型，确定结

6、点和边。这里有“人和语言”，那么我们用结点来代表人，于是结点集合V＝{A，B，C，D，E，F，G}对于任意的两点，若有共同语言，就在它们之间连一条无向边，可得边集E，图G＝（V，E）。　　如何排座位使每个人都能和他身边的人交谈？问题转化为在图G中找到一条哈密顿回路的问题（哈密顿回路即是通过每个结点一次且仅一次的回路）。而A-B-D-F-G-E-C-A即是图中的一条哈密顿回路。照这个顺序排座位就可以解决问题了。　　　　三、着色问题　　　　许多由图论描述的现实问题都需要把结点集或边集划分为一些不相交的子集，使同一子集中的所有元素互不相邻。这类问题中比较常见的有：安排会议或考试的日程以免冲突，还有

7、安排化学品的存储以避免互相反应。例如一名设计师为实验室设计化学药品存储仓库，希望建造尽量少的存储间。已知某些药品之间会起反应，不能存储在一起。作为简化，我们用字母a到n代表14种化学品；两种化学品之间的边代表它们可能起化学反应。求所需最少存储间，并指出每种药品放入哪个存储间。　　虽然这样给人感觉很复杂，似乎色数会有爆炸性增长，但实际上很容易就可以验证其色数等于3，而且是可唯一三着色的。在将其中的一个K3用3种