点击查看>>>CIE A Level 数学 S1 统计学排列的三大黄金法则 (上)
大家平常都会收发快递,那么某快递公司的一辆货车需要在全国范围内收发快递,为了节省开支,公司需要提前规划货车的行车路线,如何在多条行车路线中找到最划算的呢?我们可以用Graph Algorithm。那么,今天就让我们一起来看一下在这个过程中会被用到的一些常用名词。
首先,来看一个图
这个图是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了么?大家要时常温故而知新哦!
作者简介:
漆洋,广州新东方国外考试部教师。曾任剑桥国际高中CN372数理化教师并参与CIE教师专业进修,现任澳洲预科MUFY物理全国教学教研主管、英联邦物理教研组长。热衷于启发学生思考,调动学生学习主动性。
相关推荐:
(编辑:秦洁)