2017-06-12 2002浏览
日常生活中我们经历过收发快递，某快递公司的一辆货车需要在全国范围内收发快递，为了节省成本开支，公司需要对货车的行车路线提前进行规划，如何在多条行车路线中找到最节约成本的路线呢?这时我们可以借用Graph Algorithm。今天A/O Level考试信息网将对A-Level其中涉及到的单词进行梳理。
首先，来看一个图
这个图是Manchester以及周边五座城镇之间的距离及行车路线。单位为mile。
现在，一家快递公司需要将快递发送到这6个城镇，请问怎样的行车路线最节省开支呢?
在考虑之前，我们需要知道一些基础概念。
上述图为network(网图)，通常我们可以用network来模拟实际情况。
在图中，每个城镇都是vertices【单数为vertex】(或者叫nodes)。连接城镇的线叫做edges(或者arcs)。
那么问题就是怎样连接R O M T S B,使得它们之间的距离最短。
通过观察，我们会发现最短的距离是25英里。如下图：
这是这个网图的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?
答案下翻
只有左下及右上两幅是trees。
左上：形成了环路
右下：没有连通
Spanning Trees
一个图的spanning tree就是包含了所有vetices的子图。且它是一个tree。
一个graph可能有很多Spanning Trees。
假设你有一个无向连通图
连通：每一个vertex/node都可以通过其他任意一个vertex/ node到达
无向：edges不会有相关方向
那么一个图的spanning tree就是一个没有环路的连通子图。
下图一共有16个不同的 spanning trees，大家有时间的话，可以尝试画一画。
Minimum Spanning Tree
一个图的 minimum spanning tree即花费最小 的spanning tree。
请求出下图中的minimum spanning tree
答案下翻
在最开始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了么?以上为A/O Level考试信息网为大家整理的数学Graph Algorithm，大家要时常温故而知新哦!
上一篇 : O-level考试科目有哪些报名条件
下一篇 : GCE O-Level后的去向选择
(一) A/OLevel考试信息网考试信息网有大量转载的留学文章，仅代表作者个人观点，与A/OLevel考试信息网考试信息网无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容。文字的真实性、完整性、及时性本站不作任何保证和承诺，请读者仅作参考，并请自行核实相关内容
(二) 免费学习出于非商业性学习目的，出国留学版权归原作者所有。如有任何文章内容涉及版权问题，请在30日内与A/OLevel考试信息网考试信息网联系。
本课程由课窝教育新加坡中心提供服务与支持。
友情提示:未经A/OLevel考试信息网考试信息网书面认可,任何单位或个人不得转载、复制本网站内容：否则我们将追究法律责任。
备案号:
苏公网安备32011302322644号
增值电信业务经营许可证：苏B2-20190120 苏ICP备17009794号-16 Powered by marler.cn
版权:
2017-2021 AOLEVEL.COM.CN All Right Reserved.南京课窝教育科技有限公司版权所有
