含有平行边的图称为多重图。也称若图中某两个结点之间的边数多于一条,又允许顶点通过同一条边和自己关联,则称为多重图。多重图的定义和简单图是相对的。
定义
在无向图中,关联一对顶点的无向边如果多于1条,则称这些边为平行边,平行边的条数称为
重数。在
有向图中,关联一对顶点的有向边如果多于1条,并且这些边的始点与终点相同(也就是他们的方向相同),称这些边为平行边。含平行边的图称为多重图,既不含平行边也不含
环的图称为
简单图。
在图1和图2中,(a)中 与 是平行边,在(b)中 与 是平行边;注意, 与 不是平行边。图1和图2两个都不是简单图。
基础概念
一个图是一个有序的二元组,记作G,其中
(1) 是有限非空集合,称为顶点集,其元素称为顶点或结点。
(2) 是有限集合,称为边集,E中每个元素都有V中的结点对与之对应,称为边。
边e既可以是有向的,也可以是无向的。有向边与有序结点对 对应,这时称u为e的起点,v为e的终点。无向边与无序结点对 对应,u,v称为e的两个端点。
(3)将图的集合定义转化成图形表示之后,常用 表示图的边 ,称顶点或边用字母标定的图为标定图,否则称为非标定图。
(4)将有向图各有向边均改成无向边后的无向图称为原有向图的
基图。
(6)若 ,则通常称它为 图。p称为图G的
阶。(1,0)图称为
平凡图。边集E为空集的图称为
零图。顶点集V和边集E都是有限集的图称为有限图。 、
(7)若 ,则称点u与点v相
邻接。并说点u与边e相
关联,点v与边e相关联。同样,若边e和边f有一个共同的端点,则也称边e和边f相邻接。没有边关联于它的顶点称为
孤立点,不与其他任何边相邻接的边称为孤立边。
多重图的矩阵表示
可以用类似于有向图的方法,用
矩阵来表示一个多重图,其中每个元素 ,若从 到 无边相连,则有 ;若有边相连,且其重数为k,则 。
有向多重图
图3中的图形描绘了一个有向多重图(directed multi-graph)。在顶点W上有一个有向环(directed loop)h,从V到X存在平行有向边(parallel directed edges)i和j。因为有向图也是一种特殊的有向多重图,所以在有向多重图上给出的定义也可以应用于有向图。
注意:诸如f和m这样的有向边不是平行有向边,但i和j是平行有向边。
如果对每个 ,则称顶点和有向边的交替序列
为从 到 的有向通路(directed path)。这条有向通路的长度为n,即有向边的数目。所以R,a,S,b,T, e,W是一条从R到W长度为3的通路,也可以记作:R,S,T,W或a,b,e。由于从V到X存在两条有向边,有向通路V,i,X,k,U,m,V,j,X不能只用顶点来描述。但是,这条有向通路可以通过仅列出有向边i,k,m,j来描述。此外,T,b,S,d,V不是有向通路,因为有向边b不是从T到S而是从S到T的。同样,不存在从Y出发的长度为正数的有向通路。如前所述,一个顶点是长度为0的有向通路。
有向通路a,d,g是一条从R到W的简单有向通路(simple directed path)。即没有重复顶点的有向通路。有向通路a,d,i,k,m,g不是简单有向通路,这是因为顶点V重复出现了,容易看出每条有向通路都包含一条简单有向通路。
定理 每一条U-V有向通路都包含一条U-V简单有向通路。
图3中的有向通路a,d,f,c是一个有向回路(directed cycle),因为在这条从P到R的长度为正数的有向通路中不存在其他被访问两次的顶点。但是,b,e,g,d不是有向回路,这是因为有向边g和d的方向不对。h和f,m都可看作有向回路。有向通路k,m,f,c,a,d不是有向回路,这是因为顶点U和V出现了两次。在有向多重图D中,如果对每对顶点A和B都存在一条从A到B的有向通路,那么称D为强连通(strongly connected)的。所以,在一个强连通的有向多重图中,可以沿着有向边,按照某条路线从任何一个顶点出发到达其他任何一个顶点。