新东方网>留学>留学考试>A-level>正文

A Level数学 — Graph Algorithm之名词解释

2017-03-15 15:33

来源:新东方英联邦中学

作者:漆洋

  点击查看>>>CIE A Level 数学 S1 统计学排列的三大黄金法则 (上)

  大家平常都会收发快递,那么某快递公司的一辆货车需要在全国范围内收发快递,为了节省开支,公司需要提前规划货车的行车路线,如何在多条行车路线中找到最划算的呢?我们可以用Graph Algorithm。那么,今天就让我们一起来看一下在这个过程中会被用到的一些常用名词。

  首先,来看一个图

A Level数学 — Graph Algorithm之名词解释

  这个图是Manchester以及周边五座城镇之间的距离及行车路线。单位为mile。

  现在,一家快递公司需要将快递发送到这6个城镇,请问怎样的行车路线最节省开支呢?

  在考虑之前,我们需要知道一些基础概念。

  上述图为network(网图),通常我们可以用network来模拟实际情况。

  在图中,每个城镇都是vertices【单数为vertex】(或者叫nodes)。连接城镇的线叫做edges(或者arcs)。

  那么问题就是怎样连接R O M T S B,使得它们之间的距离最短。

  通过观察,我们会发现最短的距离是25英里。如下图:

A Level数学 — Graph Algorithm之名词解释

  这是这个网图的minimum spanning tree 最小生成树。

  最终答案包含了5个edges。minimum spanning tree 中edges的数量永远会比vertices少一个。MS这条ege的长度并不会被纳入答案,因为那样就形成了一个圈,即MSTM,不符合tree的定义。

  那么tree,spanning tree 和minimum spanning tree又分别是什么呢?

  Tree

  A tree is a connected undirected graph with no simple circuits.

  因为没有一个环路,所以一个tree不能有loops。

  因此,任何一个tree一定会是一个simple graph。

  Theorem: An undirected graph is a tree if and only if there is a unique simple path between any of its vertices.

  那么请问以下图中,哪些是tree?

A Level数学 — Graph Algorithm之名词解释

  答案下翻

  只有左下及右上两幅是trees。

  左上:形成了环路

  右下:没有连通

  Spanning Trees

  一个图的spanning tree就是包含了所有vetices的子图。且它是一个tree。

  一个graph可能有很多Spanning Trees。

  假设你有一个无向连通图

  连通:每一个vertex/node都可以通过其他任意一个vertex/ node到达

  无向:edges不会有相关方向

  那么一个图的spanning tree就是一个没有环路的连通子图。

  下图一共有16个不同的 spanning trees,大家有时间的话,可以尝试画一画。

A Level数学 — Graph Algorithm之名词解释

  Minimum Spanning Tree

  一个图的 minimum spanning tree即花费最小 的spanning tree。

  请求出下图中的minimum spanning tree

A Level数学 — Graph Algorithm之名词解释

  答案下翻

A Level数学 — Graph Algorithm之名词解释

  在最开始Manchester及周边城镇送快递的题中,我们发现只有一条spanning tree能给出最小值25,但并不是永远都是这样的,有可能对于某个graph,会有同样的最小值但是不同的行车路线。

  这题之所以可以用观察法是因为只有6个城镇。它的spanning tree较少。但要是有20个城镇,那么可能有的spanning trees会达到2.6*10^23个,通过观察法是不太可能有效率的找到minimum spanning tree的。

  那么,我们就需要应用algorithm来帮助我们提高效率。

  一般我们使用的是kruscal's algorithm和prim's algorithm。

  具体如何实施,请大家关注微信号,之后会分享哟~

  好啦,那让我们回顾下,你现在知道vertex/nodes,edges/arcs,tree,spanning tree,minimum spanning tree了么?大家要时常温故而知新哦!

  作者简介:

  漆洋,广州新东方国外考试部名师。曾任剑桥国际高中CN372数理化教师并参与CIE教师专业进修,现任澳洲预科MUFY物理全国教学教研主管、英联邦物理教研组长。热衷于启发学生思考,调动学生学习主动性。

  相关推荐:

  2017QS世界大学排名

  A-Level选课之英国大学心理学

  A-Level选读数理化报考更容易

  申请英国大学仍需A-Level成绩

  (编辑:秦洁)

新东方网托福官方微信:新东方托福 (微信号:xdftoefl

最新考试资讯、托福预测、托福解析,请扫一扫二维码,关注我们的官方微信! 

新东方留学考试辅导专区

班级名称 上课地点 上课时间 费用 详细

焦点推荐

版权及免责声明

凡本网注明"稿件来源:新东方"的所有文字、图片和音视频稿件,版权均属新东方教育科技集团(含本网和新东方网) 所有,任何媒体、网站或个人未经本网协议授权不得转载、链接、转贴或以其他任何方式复制、发表。已经本网协议授权的媒体、网站,在下载使用时必须注明"稿件来源:新东方",违者本网将依法追究法律责任。

本网未注明"稿件来源:新东方"的文/图等稿件均为转载稿,本网转载仅基于传递更多信息之目的,并不意味着赞同转载稿的观点或证实其内容的真实性。如其他媒体、网站或个人从本网下载使用,必须保留本网注明的"稿件来源",并自负版权等法律责任。如擅自篡改为"稿件来源:新东方",本网将依法追究法律责任。

如本网转载稿涉及版权等问题,请作者见稿后在两周内速来电与新东方网联系,电话:010-60908555。