每周学点大数据 | 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. 王：相应的，几个可达的顶点之间构成的最大的集合，称作强连通分量。这与无向图类似，只是必须要注意，对于有向图的连通，我们必须要考虑相互连通这个问题。

内容来源：灯塔大数据