A Level数学

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

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

　　首先，来看一个图

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

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

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

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

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

　　那么问题就是怎样连接ROMTSB,使得它们之间的距离最短。

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

　　这是这个网图的minimumspanningtree最小生成树。

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

　　那么tree，spanningtree和minimumspanningtree又分别是什么呢?

　　Tree

　　Atreeisaconnectedundirectedgraphwithnosimplecircuits.

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

　　因此，任何一个tree一定会是一个simplegraph。

　　Theorem：Anundirectedgraphisatreeifandonlyifthereisauniquesimplepathbetweenanyofitsvertices.

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

　　答案下翻

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

　　左上：形成了环路

　　右下：没有连通

　　SpanningTrees

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

　　一个graph可能有很多SpanningTrees。

　　假设你有一个无向连通图

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

　　无向：edges不会有相关方向

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

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

　　MinimumSpanningTree

　　一个图的minimumspanningtree即花费最小的spanningtree。

　　请求出下图中的minimumspanningtree

　　答案下翻

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

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

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

　　一般我们使用的是kruscal’salgorithm和prim’salgorithm。

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

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

　　作者简介：

　　相关推荐：

　　2017QS世界大学排名

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

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

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

　　(编辑：秦洁)

　　1″class=”xdf_content_detail_pagenagtion”>

上文整理了A Level数学的信息，希望文章里的这些信息考生们能认真的阅读，如果是想再了解其它方面的信息，请点击咨询英思德精英国际网站或复制【IAC0627】添加老师微信咨询！