图的基本概念

Published on 2016 - 06 - 20

有向图与无向图

图(Graph)是由顶点集合和顶点间的二元关系集合(即边的集合或弧的集合)组成的数据结构,通常可以用G(V,E)来表示。其中顶点集合(Vertext Set)边的集合(Edge Set)分别用V(G)和E(G)表示。V(G)中的元素称为顶点(Vertex),用u、v等符号表示;顶点个数称为图的阶(Order),通常用n表示。E(G)中的元素称为边(Edge),用e等符号表示;边的个数称为图的边数(Size),通常用m表示。

例如,图1(a)所示的图可以表示为G1(V,E)。其中,顶点集合V(G1)={1,2,3,4,5,6},集合中的元素为顶点(用序号代表,在其他图中,顶点集合中的元素也可以是其他标识顶点的符号,如字母A、B、C等);边的集合为:

E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(4,5)}

在上述边的集合中,每个元素(u,v)为一对顶点构成的无序对(用圆括号括起来),表示与顶点u和v相关联的一条无向边(Undirected Edge),这条边没有特定的方向,因此(u,v)与(v,u)是同一条的边。如果图中所有的边都没有方向性,这种图称为无向图(Undirected Graph)

图1(b)所示的图可以表示为G2(V,E),其中顶点集合V(G2)={1,2,3,4,5,6,7},集合中的元素也为顶点的序号;边的集合为:

E(G2)={<1,2>,<2,3>,<2,5>,<2,6>,<3,5>,<4,3>,<5,2>,<5,4>,<6,7>}

在上述边的集合中,每个元素<u,v>为一对顶点构成的有序对(用尖括号括起来),表示从顶点u到顶点v的有向边(Directed Edge),其中u是这条有向边的起始顶点(Start Vertex),简称起点,v是这条有向边的终止顶点(End Vertex),简称终点,这条边有特定的方向,由u指向v,因此<u,v>与<v,u>是两条不同的边。例如,在图1(b)有向图G2中,<2,5>和<5,2>是两条不同的边。如果图中所有的边都是有方向性的,这种图称为有向图(Directed Graph)。有向图中的边也可以称为弧(Arc)。有向图也可以表示成D(V,A),其中A为弧的集合。

有向图的基图(Ground Graph):忽略有向图所有边的方向,得到的无向图称为该有向图的基图。例如,图1(c)所示为图1(b)中有向图G2的基图。

说明:如果一个图中某些边具有方向性,而其他边没有方向性,这种图可以称为混合图(Mixed Graph);

完全图、稀疏图、稠密图

许多图论算法的复杂度都与图中顶点个数n或边的数目m有关,甚至m与n×(n-1)之间的相对关系也会影响图论算法的选择。下面介绍几个与顶点个数、边的数目相关的概念。

完全图(Complete Graph):如果无向图中任何一对顶点之间都有一条边,这种无向图称为完全图。在完全图中,阶数和边数存在关系式:m=n×(n-1)/2。例如,图2(a)所示的无向图就是完全图。阶为n的完全图用Kn表示。例如,图2(a)所示的完全图为4阶完全图K4。

有向完全图(Directed Complete Graph):如果有向图中任何一对顶点u和v,都存在<u,v>和<v,u>两条有向边,这种有向图称为有向完全图。在有向完全图中,阶数和边数存在关系式:m=n×(n-1)。例如,图2(b)所示的有向图就是有向完全图。

稀疏图(Sparse Graph):边或弧的数目相对较少(远小于n×(n-1))的图称为稀疏图。有的文献认为,边或弧的数目m<nlog(n)的无向图或有向图,称为稀疏图。例如,图3(a)所示的无向图可以称为稀疏图。

稠密图(Dense Graph):边或弧的数目相对较多的图(接近于完全图或有向完全图)称为稠密图。例如,图3(b)所示的无向图可以称为稠密图。

平凡图(Trivial Graph):只有一个顶点的图,即阶n=1的图称为平凡图。相反,阶n>1的图称为非平凡图(Nontrivial Graph)。

零图(Null Graph):边的集合E(G)为空的图,称为零图。

顶点与顶点、顶点与边的关系

在无向图和有向图中,顶点与顶点之间的关系,以及顶点与边的关系是通过“邻接(Adjacency)”这个概念来表示的。

在无向图G(V,E)中,如果(u,v)是E(G)中的元素,即(u,v)是图中的一条无向边,则称顶点u与顶点v互为邻接顶点(Adjacent Vertex),边(u,v)依附于(Attach To)顶点u和v,或称边(u,v)与顶点u和v相关联(Incident)。此外,称有一个共同顶点的两条不同边为邻接边(Adjacent Edge)

例如,在图1(a)所示的无向图G1中,与顶点2相邻接的顶点有1,3,4,5,6,而依附于顶点2的边有(2,1),(2,3),(2,4),(2,5)和(2,6)。

在有向图G(V,E)中,如果<u,v>是E(G)中的元素,即<u,v>是图中的一条有向边,则称顶点u邻接到(Adjacent To)顶点v,顶点v邻接自(Adjacent From)顶点u,边<u,v>与顶点u和v相关联

例如,在图1(b)所示的有向图G2中,顶点2分别邻接到顶点3,5,6,邻接自顶点1和5;有向边<2,6>的顶点2邻接到顶点6,顶点6邻接自顶点2;顶点2分别与边<2,3>,<2,5>,<2,6>,<1,2>和<5,2>相关联等。

顶点的度数及度序列

与顶点度数有关的概念

顶点的度数(Degree):一个顶点u的度数是与它相关联的边的数目,记作deg(u)。例如,在图1(a)所示的无向图G1中,顶点2的度数为5,顶点5的度数为3等。

在有向图中,顶点的度数等于该顶点的出度与入度之和。其中,顶点u的出度(Outdegree)是以u为起始顶点的有向边(即从顶点u出发的有向边)的数目,记作od(u);顶点u的入度(Indegree)是以u为终点的有向边(即进入到顶点u的有向边)的数目,记作id(u)。顶点u的度数:deg(u)=od(u)+id(u)。例如,在图1(b)所示的有向图G2中,顶点2的出度为3,入度为2,度数为:3+2=5。

在无向图和有向图中,边数m和所有顶点度数总和都存在如下关系。

定理1 在无向图和有向图中,所有顶点度数总和,等于边数的两倍,即:

这是因为,不管是有向图还是无向图,在统计所有顶点度数总和时,每条边都统计了两次。

偶点与奇点:为方便起见,把度数为偶数的顶点称为偶点(Even Vertex),把度数为奇数的顶点称为奇点(Odd Vertex)。

推论1 每个图都有偶数个奇点。

孤立顶点(Isolated Vertex):度数为0的顶点,称为孤立顶点。孤立顶点不与其他任何顶点邻接。

叶(Leaf):度数为1的顶点,称为叶顶点,也称叶顶点(Leaf Vertex)或端点(End Vertex)。其他顶点称为非叶顶点。

图G的最小度(Minimum Degree):图G所有顶点的最小的度数,记为δ(G)。

图G的最大度(Maximum Degree):图G所有顶点的最大的度数,记为∆(G)。

例如,图1(a)所示的无向图没有孤立顶点,顶点6为叶顶点;δ(G)=1,∆(G)=4;等。

度序列与Havel-Hakimi定理

度序列(Degree Sequence):若把图G所有顶点的度数排成一个序列s,则称s为图G的度序列。例如,图1(a)所示的无向图G1的度序列为

s:2,5,4,3,3,1;或s′:1,2,3,3,4,5;或s″:5,4,3,3,2,1。

其中序列s是按顶点序号排序的,序列s′是按度数非减顺序排列的,序列s″是按度数非增顺序排列的。给定一个图,确定它的度序列很简单,但是其逆问题并不容易,即给定一个由非负整数组成的有限序列s,判断s是否是某个图的度序列。

序列是可图的(Graphic):一个非负整数组成的有限序列如果是某个无向图的度序列,则称该序列是可图的。判定一个序列是否是可图的,有以下Havel-Hakimi定理。

定理2(Havel-Hakimi定理) 由非负整数组成的非增序列s:d1,d2,…,dn(n≥2,d1≥1)是可图的,当且仅当序列

是可图的。序列s1中有n-1个非负整数,s序列中d1后的前d1个度数(即d2~dd1+1)减1后构成s1中的前d1个数。

例如,判断序列s:7,7,4,3,3,3,2,1是否是可图的。删除序列s的首项7,对其后的7项每项减1,得到:6,3,2,2,2,1,0。继续删除序列的首项6,对其后的6项每项减1,得到:2,1,1,1,0,-1,到这一步出现了负数。由于图中不可能存在负度数的顶点,因此该序列不是可图的。

再举一个例子,判断序列s:5,4,3,3,2,2,2,1,1,1是否是可图的。删除序列s的首项5,对其后的5项每项减1,得到:3,2,2,1,1,2,1,1,1,重新排序后为:3,2,2,2,1,1,1,1,1。继续删除序列的首项3,对其后的3项每项减1,得到:1,1,1,1,1,1,1,1。如此再陆续得到序列:1,1,1,1,1,1,0;1,1,1,1,0,0;1,1,0,0,0;0,0,0,0。由此可判定该序列是可图的。

Havel-Hakimi定理实际上给出了根据一个序列s构造图(或判定s不是可图的)的方法:把序列s按照非增顺序排序以后,其顺序为d1,d2,…,dn;度数最大的顶点设为v1,将它与度数次大的前d1个顶点之间连边,然后这个顶点就可以不管了,即在序列中删除首项d1,并把后面的d1个度数减1;再把剩下的序列重新按非增顺序排序,按照上述过程连边;……;直到建出完整的图,或出现负度数等明显不合理的情况为止。

例如,对序列s:3,3,2,2,1,1构造图,设度数从大到小的6个顶点为v1~v6。首先v1与v2、v3、v4连一条边,如图4(a)所示;剩下的序列为2,1,1,1,1。如果后面4个1对应顶点v3、v4、v5、v6,则应该在v2与v3、v2与v4之间连边,最后在v5与v6之间连边,如图4(b)所示。如果后面4个1对应顶点v5、v6、v3、v4,则应该在v2与v5、v2与v6之间连边,最后在v3与v4之间连边,如图4(c)所示。可见,由同一个可图的序列构造出来的图不一定是唯一的。

二部图与完全二部图

二部图(Bipartite Graph):设无向图为G(V,E),它的顶点集合V包含两个没有公共元素的子集:X={x1,x2,…,xs}和Y={y1,y2,…,yt},元素个数分别为s和t;并且xi与xj之间(1≤i,j≤s)、yl与yr之间(1≤l,r≤t)没有边连接,则称G为二部图,有的文献也称为二分图。

例如,图5(a)所示的无向图就是一个二部图。

完全二部图(Complete Bipartite Graph):在二部图G中,如果顶点集合X中每个顶点xi与顶点集合Y中每个顶点yl都有边相连,则称G为完全二部图,记为Ks,t,s和t分别为集合X和集合Y中的顶点个数。在完全二部图Ks,t中一共有s×t条边。

例如,如图5(b)所示的K2,3和图5(c)所示的K3,3都是完全二部图。

观察图6(a)和图6(c)所示两个图,表面上看起来这两个图都不是二部图。但仔细观察,发现图6(a)中3个黑色顶点互不相邻,3个白色顶点也互不相邻,每个黑色顶点都与3个白色顶点相邻,因此图6(a)实际上也是K3,3,如图6(b)所示。同样,图6(c)中4个黑色顶点互不相邻,4个白色顶点也互不相邻,对这8个顶点进行编号后,重新画成图6(d)所示的图,发现图6(c)实际上也是一个二部图。

一个图是否为二部图,可由下面的定理判别。

定理3 一个无向图G是二部图当且仅当G中无奇数长度的回路。

图的同构

从图6可知,有些图之间看起来差别很大,比如图6(a)和图6(b)、图6(c)和图6(d),但经过改画后,它们实际上是同一个图。

又如,图7(a)和图7(b)两个图表面上看差别也很大,但是对图7(b)按照图中的顺序给每个顶点编号后发现,这两个图实际上也是同一个图。

图的同构(Isomorphism):设有两个图G1和G2,如果这两个图区别仅在于图的画法与(或)顶点的标号方式,则称它们是同构的。意思就是说这两个图是同一个图。关于同构的严格定义,请参考其他教材。

子图与生成树

设有两个图G(V,E)和G′(V′,E′),如果V′⊆V,且E′⊆E,则称图G′是图G的子图(Subgraph)。例如,图8(a)、图8(b)所示的无向图都是图1(a)所示的无向图G1的子图,而图8(c)、图8(d)所示的有向图都是图1(b)所示的有向图G2的子图。

生成树(Spanning Tree):一个无向连通图的生成树是它的包含所有顶点的极小连通子图,这里所谓的极小就是边的数目极小。如果图中有n个顶点,则生成树有n-1条边。一个无向连通图可能有多个生成树。

例如,图1(a)所示的无向图G1的一个生成树如图9(a)所示。为了更形象地表示这个生成树,在图9(b)中把它画成了以顶点1为根结点的树,在图9(c)中把它画成了以顶点3为根结点的树。

观察图10,其中图10(b)和图10(c)都是图10(a)的子图,这两个子图的顶点集相同,为V′={2,3,4,5},但边集不相同。图10(b)保留了原图中V′内各顶点间的边,而在图10(c)中,原图的边(3,5)和(3,2)被去掉了。因此有必要进一步讨论子图。

设图G′(V′,E′)是图G(V,E)的子图,且对于V′中的任意两个顶点u和v,只要(u,v)是G中的边,则一定是G′中的边,此时称图G′为由顶点集合V′诱导的G的子图(Subgraph of G Induced By V′),简称为顶点诱导子图(Vertex-Induced Subgraph),记为G[V′]。根据定义,在图10中,图10(b)是由V′={2,3,4,5}诱导的子图,图10(c)和图10(d)都不是顶点诱导子图。

类似地,对于图G的一个非空的边集合E′,由边集合E′诱导的G的子图是以E′作为边集,以至少与E′中一条边关联的那些顶点构成顶点集V′,这个子图G′(V′,E′)称为是G的一个边诱导子图(Edge-Induced Subgraph),记为G[E′]。根据定义,在图10中,图10(b)、图10(c)和图10(d)都是边诱导子图。

说明:由于边必须依附于顶点而存在,所以对于“某条边属于子图,但该边某个顶点不属于子图”的情形,是没有意义的。

路径

路径是图论中一个很重要的概念。在图G(V,E)中,若从顶点vi出发,沿着一些边经过一些顶点vp1,vp2,…,vpm,到达顶点vj,则称顶点序列(vi,vp1,vp2,…,vpm,vj)为从顶点vi到顶点vj的一条路径(Path),或称为通路,其中(vi,vp1),(vp1,vp2),…,(vpm,vj)为图G中的边。如果G是有向图,则<vi,vp1>,<vp1,vp2>,…,<vpm,vj>为图G中的有向边。

路径长度(Length):路径中边的数目通常称为路径的长度。

例如,在图1(a)所示的无向图G1中,顶点序列(1,2,5,4)是从顶点1到顶点4的路径,路径长度为3,其中(1,2),(2,5),(5,4)都是图G1中的边;另外,顶点序列(1,3,4)也是从顶点1到顶点4的路径,路径长度为2。

在图1(b)所示的有向图G2中,顶点序列(3,5,2,6)是从顶点3到顶点6的路径,路径长度为3,其中<3,5>,<5,2>,<2,6>都是图G2中的有向边;而从顶点7到顶点1没有路径。

简单路径(Simple Path):若路径上各顶点vi,vp1,vp2,…,vpm,vj均互相不重复,则这样的路径称为简单路径。例如,在图1(a)所示的无向图G1中,路径(1,2,5,4)就是一条简单路径。

回路(Circuit):若路径上第一个顶点vi与最后一个顶点vj重合,则称这样的路径为回路。例如,在图1中,图G1中的路径(2,3,4,5,2)和图G2中的路径(5,4,3,5)都是回路。回路也称为环(Loop)。

简单回路(Simple Circuit):除第一个和最后一个顶点外,没有顶点重复的回路称为简单回路。简单回路也称为圈(Cycle)。长度为奇数的圈称为奇圈(Odd Cycle),长度为偶数的圈称为偶圈(Even Cycle)

连通性

连通性也是图论中一个很重要的概念。在无向图中,若从顶点u到v有路径,则称顶点u和v是连通(Connected)的。如果无向图中任意一对顶点都是连通的,则称此图是连通图(Connected Graph);相反,如果一个无向图不是连通图,则称为非连通图(Disconnected Graph)

如果一个无向图不是连通的,则其极大连通子图称为连通分量(Connected Component),这里所谓的极大是指子图中包含的顶点个数极大。

例如,图1(a)所示的无向图G1就是一个连通图。在图G1中,如果去掉边(2,6),则剩下的图就是非连通的,且包含两个连通分量,一个是由顶点1、2、3、4、5组成的连通分量,另一个是由顶点6构成的连通分量。

又如,图11所示的无向图也是非连通图。其中顶点1、2、3和5构成一个连通分量,顶点4、6、7和8构成另一个连通分量。

在有向图中,若对每一对顶点u和v,既存在从u到v的路径,也存在从v到u的路径,则称此有向图为强连通图(Strongly Connected Digraph)。例如,图12(a)和图12(b)所示的有向图就是强连通图。

对于非强连通图,其极大强连通子图称为其强连通分量(Strongly Connected Component)。例如,图13(a)所示的有向图G2就是非强连通图,它包含3个强连通分量,如图13(b)所示。其中,顶点2、3、4、5构成一个强连通分量,在这个子图中,每一对顶点u和v,既存在从u到v的路径,也存在从v到u的路径;顶点1、6、8也构成一个强连通分量,顶点7自成一个强连通分量。

权值、有向网与无向网

权值(Weight):某些图的边具有与它相关的数,称为权值。这些权值可以表示从一个顶点到另一个顶点的距离、花费的代价、所需的时间等。如果一个图,其所有边都具有权值,则称为加权图(Weighted Graph),或者称为网络(Net)。根据网络中的边是否具有方向性,又可以分为有向网(Directed Net)无向网(Undirected Net)。网络也可以用G(V,E)表示,其中边的集合E中每个元素包含3个分量:边的两个顶点和权值。

例如,图14(a)所示的无向网可表示为G1(V,E),其中顶点集合V(G1)={1,2,3,4,5,6,7};边的集合为:

E(G1)={(1,2,28),(1,6,10),(2,3,16),(2,7,14),(3,4,12),(4,5,22),(4,7,18),(5,6,25),(5,7,24)}

在边的集合中,每个元素的第3个分量表示该边的权值。

如图14(b)所示的有向网可以表示为G2(V,E),其中顶点集合V(G1)={1,2,3,4,5,6,7};边的集合为:

E(G2)={<1,2,12>,<2,4,85>,<3,2,43>,<4,3,65>,<5,1,58>,<5,2,90>,<5,6,19>,<5,7,70>,<6,4,24>,<7,6,50>}

同样在边的集合中,每个元素的第3个分量也表示该边的权值。

参考文档