每周学点大数据 | No.14 图论基础回顾

No.14期

图论基础回顾

Mr. 王:我们再讲一个时间亚线性算法——平面图直径的求解。平面图是图论中的一个概念,在大数据算法的很多地方都会涉及图的相关内容,所以这里我们还是要回顾一下图论的知识。

首先来看看什么是图。其实很多文献对图的定义都是不尽相同的,但是整体的描述差异不大。

我们一般用G(V,E)来表示一个图,其中G 表示这个图,V是这个图的顶点集合,E是这个图的边集合。

图的例子

比如在上面的图G(V,E)中:

V={A,B,C,D,E}

E={(A,E),(A,D),(A,C),(B,E),(B,D),(B,C),(D,C),(D,E)}

整体上图可以分为两种:有向图和无向图。这里的有向和无向是相对边来说的。在无向图中,边是没有方向的,连接顶点u 和v 的边可以记为(u,v),当然也可以记为(v,u)。由于边是没有方向的,所以这两种表示法表示的是同一条边。在无向图中,每一条边都是双向可达的,如果有边(u,v)存在的话,那么u是v的邻居,v也是u的邻居。与u直接相连的边的数量,叫作u的度数。

而在有向图中则不然,每一条边都是有方向的,也就是说,(u,v)这条边表示的是从u指向v的一条边;而(v,u)这条边表示的是从v指向u的一条边。它们都是单向可达的。如果仅有(u,v)这条边存在,u可以通过(u,v)到达v,但v却不能通过这条边到达u,即(u,v)和(v,u)是两条不同的边。以u为起点的边,叫作u的出度;以u为终点的边,叫作u的入度。在图形表示中,我们使用带有箭头的线来表示有向边。

我们使用的图多数都是加权图。在加权图中,有的是边加权,也就是说,边不仅仅是一条边,在边的上面有一个权重,这个权重也可以叫作边的长度,在边不加权的图中,我们一般认为边的长度为1。还有的是图的顶点具有一个权值。当然,也有顶点和边均具有权值的加权图。

小可:我想一些城市的互联关系,或者说地图就可以抽象成一个加权图吧,图的边权用来表示两个城市之间的距离。

Mr. 王:没错。就用交通地图来举个例子,我们想从一个城市到达另一个城市,而这两个城市之间并没有一条直接相连的公路。我们会选择途经另一个城市,所以就有了路径的产生。如果从一个顶点u到另一个顶点v中间途经数个顶点w1,w2,w3,…,并且这些顶点之间的边都存在的话,我们称<u,w1,w2,w3,…,v>是一条路径。

小可:嗯,这在现实中也是非常普遍存在的。

Mr. 王:我们定义路径的长度,为途经的边的个数。如果中间的那些顶点w1,w2,w3,…没有重复的,我们称之为简单路径。如果u和v是同一个顶点,并且至少经过一条边的话,我们称这条路径是一个回路。

小可若有所思,说:如果u本身有一条边指向自己,就是有一个圈,这样也是回路吗?

Mr. 王:虽然没有经过任何一个其他顶点,但是中间经过了一条边,它也是一条回路。相应的,如果回路中没有出现重复的顶点,这就是一条简单回路。

Mr. 王:另外,在无向图中,如果每两个顶点之间都有一条路径,我们称它是连通图。

小可:这样每个顶点就都连在一起了,整个图是连通的。

Mr. 王:几个可达的顶点之间构成的最大的集合,称作连通分量。这个最大的集合是指,如果几个点之间是连通的,只要再添加图中的任何一个顶点就都不再连通。连通分量是一个图的子图。还有一种判定连通图的方法,就是如果一个无向图只有一个连通分量的话,那么它就是连通的。

小可:嗯,在无向图中是这样的,那么在有向图中又如何呢?

Mr. 王:由于有向图的边是有方向的,所以存在这样一种情况,就是虽然两个顶点是有一条边“连着”的,但是却是单向可达的。在这种情况下,我们不能说它是连通的。在无向图中,如果图中每对顶点都互相可达,我们才能认为它是“连通”的,称作强连通图。

小可:的确,相互可达才能达到我们判定它连通这个目的。

Mr. 王:相应的,几个可达的顶点之间构成的最大的集合,称作强连通分量。这与无向图类似,只是必须要注意,对于有向图的连通,我们必须要考虑相互连通这个问题。

内容来源:灯塔大数据

原文发布于微信公众号 - 灯塔大数据(DTbigdata)

原文发表时间:2016-11-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏天天P图攻城狮

Android上实现频域均衡器

本篇文章主要介绍了将录音从时域数据转化成频域数据的方法。

49220
来自专栏程序猿

博弈之取石子问题

取石子问题 有一种很有意思的游戏,就是有物体若干堆,可以是火柴棍或是围棋子等等均可。两个人轮流从堆中取物体若干,规定最后取光物体者取胜。这是我国民间很古老的一个...

44490
来自专栏水击三千

经纬度转换-----度分秒以及经纬度和米

经纬度互换 度(DDD):E 108.90593度    N 34.21630度     如何将度(DDD):: 108.90593度换算成度分秒(DMS)东经...

64170
来自专栏计算机视觉战队

利用深度学习消去反光

越来越接近毕业季了,相信很多同学都结束了论文的撰写以及论文审批,现在就坐等着毕业论文答辩和毕业典礼了!其实我也是这样的一个状态,但是期间大Boss还是会安排很多...

16910
来自专栏UAI人工智能

深度学习入门教程 第一讲

18230
来自专栏大数据文摘

改变计算技术的 9 个伟大算法

26430
来自专栏大数据

大数据图:循环点阵

本文的内容最初由Marko Rodriguez和Bobby Norton在Aurelius博客上共同撰写。

35650
来自专栏AI研习社

文本分类又来了,用 Scikit-Learn 解决多类文本分类问题

在商业领域有很多文本分类的应用,比如新闻故事通常由主题来分类;内容或产品常常被打上标签;基于如何在线谈论产品或品牌,用户被分成支持者等等。

17810
来自专栏小樱的经验随笔

ACM训练计划

看完人家的博客,发现任重道远。。。 一位高手对我的建议: 一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功.acm主要是考算法的,主要时间...

559110
来自专栏机器学习算法原理与实践

贝叶斯个性化排序(BPR)算法小结

    在矩阵分解在协同过滤推荐算法中的应用中,我们讨论过像funkSVD之类的矩阵分解方法如何用于推荐。今天我们讲另一种在实际产品中用的比较多的推荐算法:贝叶...

35530

扫码关注云+社区

领取腾讯云代金券