一、顶点(vertex)
上图中黑色的带数字的点就是顶点,表示某个事物或对象。由于图的术语没有标准化,因此,称顶点为点、节点、结点、端点等都是可以的。叫什么无所谓,理解是什么才是关键。
二、边(edge)
上图中顶点之间蓝色的线条就是边,表示事物与事物之间的关系。需要注意的是边表示的是顶点之间的逻辑关系,粗细长短都无所谓的。包括上面的顶点也一样,表示逻辑事物或对象,画的时候大小形状都无所谓。
三、同构(Isomorphism )
先看看下面2张图:
首先你的感觉是这2个图肯定不一样。但从图(graph)的角度出发,这2个图是一样的,即它们是同构的。前面提到顶点和边指的是事物和事物的逻辑关系,不管顶点的位置在哪,边的粗细长短如何,只要不改变顶点代表的事物本身,不改变顶点之间的逻辑关系,那么就代表这些图拥有相同的信息,是同一个图。同构的图区别仅在于画法不同。
四、有向/无向图(Directed Graph/ Undirected Graph)
最基本的图通常被定义为“无向图”,与之对应的则被称为“有向图”。两者唯一的区别在于,有向图中的边是有方向性的。下图即是一个有向图,边的方向分别是:(1->2), (1-> 3), (3-> 1), (1->5), (2->3), (3->4), (3->5), (4->5), (1->6), (4->6)。要注意,图中的边(1->3)和(3->1)是不同的。有向图和无向图的许多原理和算法是相通的。
五、权重(weight)
边的权重(或者称为权值、开销、长度等),也是一个非常核心的概念,即每条边都有与之对应的值。例如当顶点代表某些物理地点时,两个顶点间边的权重可以设置为路网中的开车距离。下图中顶点为4个城市:Beijing, Shanghai, Wuhan, Guangzhou,边的权重设置为2城市之间的开车距离。有时候为了应对特殊情况,边的权重可以是零或者负数,也别忘了“图”是用来记录关联的东西,并不是真正的地图。
六、路径/最短路径(path/shortest path)
在图上任取两顶点,分别作为起点(start vertex)和终点(end vertex),我们可以规划许多条由起点到终点的路线。不会来来回回绕圈子、不会重复经过同一个点和同一条边的路线,就是一条“路径”。两点之间存在路径,则称这2个顶点是连通的(connected)。
还是上图的例子,北京->上海->广州,是一条路径,北京->武汉->广州,是另一条路径,北京—>武汉->上海->广州,也是一条路径。而北京->武汉->广州这条路径最短,称为最短路径。
路径也有权重。路径经过的每一条边,沿路加权重,权重总和就是路径的权重(通常只加边的权重,而不考虑顶点的权重)。在路网中,路径的权重,可以想象成路径的总长度。在有向图中,路径还必须跟随边的方向。
值得注意的是,一条路径包含了顶点和边,因此路径本身也构成了图结构,只不过是一种特殊的图结构。
七、环(loop)
环,也成为环路,是一个与路径相似的概念。在路径的终点添加一条指向起点的边,就构成一条环路。通俗点说就是绕圈。
上图中,北京->上海->武汉->广州->北京,就是一个环路。北京->武汉->上海->北京,也是一个环路。与路径一样,有向图中的环路也必须跟随边的方向。环本身也是一种特殊的图结构。
八、连通图/连通分量(connected graph/connected component)
如果在图G中,任意2个顶点之间都存在路径,那么称G为连通图(注意是任意2顶点)。
上面那张城市之间的图,每个城市之间都有路径,因此是连通图。而下面这张图中,顶点8和顶点2之间就不存在路径,因此下图不是一个连通图,当然该图中还有很多顶点之间不存在路径。
上图虽然不是一个连通图,但它有多个连通子图:0,1,2顶点构成一个连通子图,0,1,2,3,4顶点构成的子图是连通图,6,7,8,9顶点构成的子图也是连通图,当然还有很多子图。我们把一个图的最大连通子图称为它的连通分量。0,1,2,3,4顶点构成的子图就是该图的最大连通子图,也就是连通分量。连通分量有如下特点:
1)是子图;
2)子图是连通的;
3)子图含有最大顶点数。注意:“最大连通子图”指的是无法再扩展了,不能包含更多顶点和边的子图。0,1,2,3,4顶点构成的子图已经无法再扩展了。
显然,对于连通图来说,它的最大连通子图就是其本身,连通分量也是其本身。
九、有向图/无向图的度数
对于无向图
每个顶点的度数就是它连接边的数量
对于有向图
入度就是:有向图的某个顶点作为终点的次数和。
出度就是:有向图的某个顶点作为起点的次数和。
十、简单图
一个图G若满足:不存在重复边、不存在顶点到自身的边,则称图G为简单图。
十一、多重图
若图G中某两个结点之间的边数多于一条,又允许顶点通过同一条边和自己关联,则G为多重图。多重图的定义和简单图是相对的。
十二、完全图(也称简单完全图)
对于无向图,|E|的取值范围是0到n(n-1)/2,有n(n-1)/2条边的无向图称为完全图,在完全图中任意两个顶点之间都存在边。
对于有向图,|E|的取值范围是0到n(n-1),有n(n-1)条弧的有向图称为有向完全图,在有向完全图中任意两个顶点之间都存在方向相反的两条弧。
十三、强连通图、强连通分量
在有向图中,若从顶点v到顶点w和从顶点w到顶点v之间都有路径,则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的,则称此图为强连通图。有向图的极大强连通子图称为有向图的强连通分量。
注意:强连通图、强连通分量只是针对有向图而言的。
十四、稠密图和稀疏图
边数很少的图称为稀疏图,反之称为稠密图。稀疏和稠密本身是模糊的概念,稀疏图和稠密图常常是相对而言的。一般当图G满足|E| < |V|log|V|时,可以将G视为稀疏图。
十五、简单回路
除第一个顶点和最后一个顶点外,其余顶点不重复出现的回路称为简单回路。
十六、距离
从顶点u出发到顶点v的最短路径若存在,则此路径的长度称为从u到v的距离。若从u到v根本不存在路径,则记该距离为无穷。
十七、有向树
一个顶点的入度为0、其余顶点的入度均为1的有向图,称为有向树。
课后习题
【2019年真题】用有向无环图描述表达式(x+y)*((x+y)/x),需要的顶点个数至少是
A. 5 B. 6 C. 8 D. 9
参考答案:A
【2017年真题】已知无向图G含有16条边,其中度为4的顶点个数为3,度为3的顶点个数为4,其他顶点的度均小于3。图G所含的顶点个数至少是()
A.10 B.11 C.13 D.15
参考答案:B
【2010年真题】若无向图 G=(V, E)中含有 7 个顶点,要保证图 G 在任何情况下都是连通的,则需要的边数最少是()。
A.6 B.15 C.16 D.21
参考答案:C
答案解析:考查图的连通性。
要保证无向图 G 在任何情况下都是连通的,即任意变动图 G 中的边,G 始终保持连通,首先需要 G的任意六个结点构成完全连通子图 G1,需 15 条边,然后再添一条边将第 7 个结点与 G1 连接起来,共需 16 条边。
【2009年真题】下列关于无向连通图特性的叙述中,正确的是()。
I. 所有顶点的度之和为偶数
II. 边数大于顶点个数减 1
III. 至少有一个顶点的度为 1
A. 只有Ⅰ
B.只有Ⅱ
C.Ⅰ和Ⅱ
D.Ⅰ和Ⅲ
参考答案:A
答案解析:考查无向连通图的特性。
每条边都连接了两个结点,则在计算顶点的度之时,这条边都被计算了两次,故所有顶点的度之和为边数的两倍,显然必为偶数。而 ii 和 iii 则不一定正确,如:对顶点数 N≥1 无向完全图不存在一个顶点的度为 1,并且边数与顶点数的差要大于 1。
登录后开始许愿
一站成硕