第5 章图的基本概念
图论的内容十分丰富,应用相当广泛。许多学科,诸如运筹学、信息论、控制论、网络理
论、博弈论、化学、生物学、物理学、社会科学、语言学、计算机科学等,都以图作为工具来解决
实际问题和理论问题。随着计算机科学的发展,图论在以上各学科中的作用越来越大,同时
图论本身也得到了充分的发展。本书在第5~7章中介绍与计算机科学关系密切的图论
内容。
5.无向图及有向图
1
在集合论中已给出了集合与卡氏积的概念,这里还需要给出多重集与无序积的概念。
集合中的元素不重复出现,当允许元素重复出现时称作多重集。如,{a,c,c} a,
b,c}作为集合是相同的,而作为多重集是不相同的。
a,b,c,与{
设A、
B
为两个集合,称
{{b}|
a
∈
A
∧
b
∈B}
a,
将无序对{b} a,、
为
A
与
B
的无序积,记作A&B。为方便起见, a,记作(b)。无论ab
是否
相同,显然有(b)b,)。例如, a1,B={b2},则
a,=(
a
设A={a2},b1,
A&
B
={(b1),(b2),(b1),(b2)}
a1,a1,a2,a2,
A&
A
={(a1),(a2),(a2)}
a1,a1,a2,
定义5.1
一个无向图
G
是一个二元组<V,E>,其中
(1)
V
是一个非空的有穷集合,
V
中元素称为顶点或结点;
称为
G
的顶点集,
(2)
E
是无序积V&
V
的一个多重子集,称为
G
的边集,
E
中元素称为无向边或简称边。
图
G
的顶点集记作V(G),边集记作E(G)。在图的运算中,有时会产生顶点集为.的
结果,因而规定顶点集为.的图为空图。
以上给出的是一个无向图的数学定义,还可以用图形表示无向图,这样更直观。用小圆
圈或实心点表示顶点,用连接两个顶点的线段表示边,其中顶点的位置、线段的曲直及是否
相交都无关紧要。例如,G=<V,V={v2,v4,v2,
v5},E={(v2),(v2),(
E>,v1,v3,v1,v2,
v1,v1,v1,
v3),(
定义5.
v3),(v3),(v4)},
G
的图形如图51(a)所示。
2
一个有向图
D
是一个二元组<V,E>,其中
(1)
V
是一个非空的有穷集合,
V
中元素称为顶点或结点;
称为
D
的顶点集,
(2)
E
是卡氏积V×V
的多重子图,称为
D
的边集,其元素称为有向边或边。
也用V(D)、E(D)分别表示有向图
D
的顶点集和边集。有向图
D
也可以用图形表示,
与无向图不同的是,用带箭头的连线表示有向边。例如,=E>,其中V={v1,
D
<V,v2,
v3,v5},
E
{<v1,v2>,<v3,v4>,<v2,v5>,
v4,=v1>,<v3,v2>,<v3,v4>,<v4,
<v5,v4>,<v1,
v2>},
D
的图形如图51(b)所示。为方便起见,也可以给边起个名字。例
·120· 离散数学(第六版)
如,在图5-1(a)中,用e1 表示边(v2,e2 表示边(v1,v2)等。在图5-1(b)中,用e1 表示
边<v1,e2 表示边<v1,
v2),
v1>,v2>等。
图5-
1
无向图和有向图通称为图,但有时也把无向图简称图。常用
G
表示无向图,用
D
表示
有向图。有时又用
G
泛指无向图或有向图。
有
n
个顶点的图(无向图或有向图)称为
n
阶图。没有一条边的图称为零图。一阶零
图,即只有一个顶点
定义5.3
、没有边的图,称为平凡图
设
。e=(v) 则称uv
为
e
的端
点,和v)
在无向图G=<V,E>中, u,是
G
的一条边,、
则
e
与u( 关联。无边关联的顶点称为孤立点。若一条边所关联的两个顶点重合,
称此边为环。若u≠v,则称
e
与u(和v)的关联次数为1;若u=v,称
e
与
u
的关联次数为
2;若
w
不是
e
的端点,则称
e
与
w
的关联次数为0。
若存在一条边
e
以顶点u、
v
为端点,则称u、
v
是相邻的。若两条边e、e'至少有一个公
共端点,则称e、e'是相邻的。
在图5-1(中,v1,v1、e2 与v1 v2 的关联次数均为1。v5
a) e2=(v2),v2 为e2 的端点,、
是孤立点。e1 是环,而v2 与v4 不相邻。e1
e1 与v2 的关联次数为2。v1 与v2 是相邻的,
e2 与e3 也是相邻的,与e2
定义5.4
是相邻的,
在有向图D=<V,E
而
>
e
中1,
与e4 不相邻
v
。
>是
D
的一条有向边,
设e=<u,则称
u
为
e
、
e
与u(
的始点,
v
为
e
的终点,也称uv
为
e
的端点,和v)关联。无边关联的顶点称为孤立
点。若一条有向边的始点与终点重合,则称此边为环。
若存在一条边
e
以顶点
u
为始点、以
v
为终点,则称
u
邻接到v。若边
e
的终点与边e'
的始点重合,则称e、e'是相邻的。
在图5-b) 边e2=<v1,v1 是e2 的始点,v1 邻接到v2。e1
1(中, v2>,v2 是e2 的终点,
是环,无孤立点。边e1 与e2 是相邻的,而e2 与e3 不是相邻的。
定义5.5
e2 与e5 也是相邻的
,
在无向图中,顶点
v
作为边的端点的次数之和为
v
的度数,简称度,记
作
在有向图中,称顶点
v
作为边的始点的次数之和为
v
的出度, v);
的终点的次数之和为
v
的入度,记作d-v); 简
(称
v
作为边的端点的次数之和为
v
的度数,
d
称
(
度
)。
,记作d()。显然,d(v)=d+(v)+d-(v)。
记作d+(称
v
作为边
-1((v) d(=d(=d(=1(v1)2,=
在图5中,0。在图5中,d+(d-(
a) v1)4,v2)4,v5)-b) =v1)
1,d(=v2)1,v2)3,v2)4。注意, -a) v2 作为环e1 的端
d+(d
v1)3,=(=d(=在图51(中,
点是2次。在图5-1(b)中,v1 作为环e1 的一次始点、一次终点和2次端点。
第5章图的基本概念·121·
点,
称度数为1的顶点为悬挂顶点,它所关联的边为悬挂边。在图5-a) v4 为悬挂顶
e6 为悬挂边。
1(中,
对于无向图G=<V,E>,记
=mad(
Δ(G)x{v)|
v
∈V}
=mn{v)|
v
∈V}
分别称为
G
的最大度和最小度
δ。
(G)id(
对于有向图D=<V,E>,除了最大度Δ(D)、最小度δ(D)外,还有最大出度Δ+(D)、
最大入度Δ-(D)、最小出度δ+(D)、最小入度δ-(D), 分别定义如下:
Δ(D)x{v)|
v
∈V}
=mad(
δ(D)id(
=mn{v)|
v
∈V}
Δ+
(d+
(
D)=max{v)|
v
∈V}
-
Δ-((
D)=max{dv)|
v
∈V}
δ+
(d+
(
D)=min{v)|
v
∈V}
δD)=min{dv)|
v
∈V}
a) 4,
-(
1(中,
-(
2,3,3,1,
在图51(中,0。图5b) 4,Δ+Δ-δ+-0。
-Δ=δ=-Δ=δ====δ=
定理5.握手定理) 设图G=<V,1(
下面定理给出图中顶点度数与边数之间的关系。
v1,},
数|E|=m,则
E>为无向图或有向图,
V
={v2,…,vn
边
d(
Σ(n) vi)=2m
i=1
证明每条边有两个端点,所有顶点的度数之和等于它们作为端点的次数之和,因此恰
好等于边数的2倍。
握手定理是图论中的基本定理,它有一个重要推论。
推论任何图(无向的或有向的)中,度数为奇数的顶点个数是偶数。
定理5.2
对有向图来说,还有下面的定理
E
。
>,V={v1,vn
=m,
设有向图D=<V,v2,…,},|E|则
-
vi)(
=
i=1 i=1
可类似定理5.Σ(n) d+
(Σ(n) dvi)=
m
1证明。
以上两个定理及其推论都是非常重要的,希望记住它们并能灵活运用。
设V={v2,…,
n
} 称(v1),v2),…,vn
)) 为
G
的度数序
v1,v为图
G
的顶点集, d(d(d(
列。有向图还有入度序列和出度序列。图5-1(a)的度数序列为(4,4,3,1,0), 图5-1(b)的
3,4,3,4,1,3,0,3,2,1,3,1,
度数序列为
例5.1(2), 入度序列为(1), 出度序列为(1)。
(1)(3,3,2,3)、(5,2,3,1,4)能成为图的度数序列吗? 为什么?
(2)已知图
G
中有10 条边,4个度数为3的顶点,其余顶点的度数均小于或等于2,
G
中至少有多少个顶点? 为什么?
解(1)由于这两个序列中,奇数个数均为奇数,由握手定理的推论可知,它们都不能
成为图的度数序列。
·122· 离散数学(第六版)
(2)图中边数m=10,由握手定理可知,
G
中各顶点度数之和为20,4个3度顶点占去
12 度,还剩8度。若其余全是2度顶点,还需要4个顶点来占用这8度,所以
G
至少有8个
顶点
定义5.6
。
在无向图中,关联一对顶点的无向边如果多于1条,称这些边为平行边。
平行边的条数称为重数。
在有向图中,如果有多于1条的边的始点与终点相同,则称这些边为有向平行边,简称
平行边。
含平行边的图称为多重图。既不含平行边也不含环的图称为简单图。
-a) e4 与e5 是平行边。在图5
在图51(中,1(b)
中,而e7 与e8 不是平行边。这两个
e3 与e4 是平行边,
图都不是简单图。图5-2中所示的3个图都是简单图。
定义5.7
设G=<V,
E
>是
n
阶无向简单图,
若
G
中任何顶点都与其余的n-1个顶点相邻,则称
G
图5-
2
为
n
阶无向完全图,记作Kn
。
设D=<V,E>为
n
阶有向简单图, v∈V(既有有向边
v>, u>,
若对于任意的顶点u,u≠v),
<u,又有<v,则称
D
是
n
阶有向完全图。
定义5.8
在图5-2中(a)为K4,(b)为K5,(c)为3阶有向完全图。
设G=<V,E>,G'=<V'
,E'>是两个图。若V'
.
V
且E'.E,则称G'
是
G
的子图,
G
是G'的母图,记作G'.G。
若G'.
G
且G'≠G(即V'
.
V
或E'
.E), 则称G'是
G
的真子图。
若G'.
G
且V'=V,则称G'是
G
的生成子图。
设V1.V,且V1≠.,以V1 为顶点集,以所有两个端点均在V1 中的边为边集的
G
的
子图,称为V1 导出的导出子图,记作G[]。
V1
设E1.E,且E1≠.,以E1 为边集,以E1 中边关联的所有顶点为顶点集的
G
的子图,
称为E1 导出的导出子图,记作G[E1]。
在图5-图53(图53(均为图53(的子图,-c) -b)
3中,-b)、-c) -a) 图53(是生成子图。图53(是
顶点子集{v2} 也是边子集{e5} -c) e1,
v1,的导出子图, e4,的导出子图。图53(又是边子集{
e3,的导出子图。图53(图53(是图53(的子图, -e) 也是边
e4} -e)、-f) -d) 图53(是生成子图,
子集{e1,e3} -f) e1}
的导出子图。图53(是边子集{的导出子图。
图5-
3
定义5.9
注意,每个图都是本身的子图。
..G=<V,..设G=<V,E>是
n
阶无向简单图。
G
的补图
G
定义如下:..E>,
第5章图的基本概念·123·
..u,v)|u,u,
有向简单图的补图可类似定义。
在图5-4中,图5-4(a)是图5-4(b)的补图,当然图5-4(b)也是图5-4(a)的补图,也就是
说,图5-4(a)和图5-4(b)互为补图。图5-4(c)和图5-4(d)互为补图。
其中E={(v∈
V
且(v).E}。
图5-
4
图是表达事物之间关系的工具。在画图时,由于顶点位置的不同,边的直、曲不同,同一
个事物之间的关系可能画出不同形状的图来,因而引出了图同构的概念。
设两个无向图G1=<V1,E1>,G2=<V2,E2>,如果存在双射函数f:
V1→V2, u,'=(f(f(
定义5.10
使得对于任意的e=(v)∈E1 当且仅当eu),v))∈E2,并且
e
与e'的重
数相同,则称G1 与G2 是同构的,记作G1.G2。
可类似定义两个有向图同构,只是还要考虑有向边的方向。
--b.v2,
在图55中,图55(a)与图5-5(b)同构,顶点之间的对应关系为a.v1,c.v3,
d.v4,。不难验证,图5-5(c)与图55(d)同构。图5-5(c)称为彼德森图。
e.v5
图5-
5
显然,顶点数相同,边数相同,度数序列相同(不计顺序)等都是两个图同构的必要条件,
还可以找到更多的必要条件。只要不满足某个必要条件,就说明这两个图不同构。例如,在
图5-5中,在图5-f)中存在3个彼此不相邻的顶点,而在图55(中却找不到3个彼此不
5(
5(与图5f)
-e)
边的条数相相邻的顶点,因此图5-e) -5(不同构。注意这两个图的顶点个数相同,
同,每个顶点都是3度顶点,但这些都是图同构的必要条件,不是充分条件。至今还没有找
到便于判断的图同构的充分必要条件。要证明两个图同构,只能根据定义,找到顶点之间满
足条件的双射,至今还不知道更好的方法。
例5.2
(1)画出4个顶点3条边的所有非同构的无向简单图。
(2)画出3个顶点2条边的所有非同构的有向简单图。
解(1)直观上容易看出,4个顶点3条边的所有非同构的无向简单图只有图5-6(a)、
图5-6(b)、图5-6(c)所示的3个图。
-d)、-e)、-f)、
(2)3个顶点2条边的所有非同构的有向简单图只有图56(图56(图56(
图5-6(g)所示的4个图。3个顶点2条边的非同构的无向简单图只有1个,由它可派生出3
·124· 离散数学(第六版)
-d)、-e)、-f)。
个非同构的有向简单图为图56(图56(图56(
图5-
6
5.2
通路、回路和图的连通性
通路与回路是图论中两个重要而又基本的概念。本节所述定义一般来说既适合无向
图,也适合有向图;否则,将加以说明或分开定义。
设图
G
中顶点和边的交替序列Γ=v0e1v1e2…lvl,若vi-1和vi
是ei
的
端点(当
G
是有向图时,-
i
的始点,v是ei
的终点i=2,…,则称
Γ
为顶
定义5.11
要求vi1是ei ),(e) 1,l,
点v0 到vl
的通路。v0 和vl
分别称为此通路的起点和终点,
Γ
中边的数目
l
称为
Γ
的长
度。当v0=vl
时,此通路称为回路。
若
Γ
中的所有边互不相同,则称
Γ
为简单通路。当v0=vl
时,称此简单通路为简单
回路。若
Γ
中除v0,外所有顶点互不相同, 则称此通路为初级通路或路
vl
所有边也互不相同,
径。当v0=vl
时,称此初级通路为初级回路或圈。
有边重复出现的通路称为复杂通路,有边重复出现的回路称为复杂回路。
在上述定义中,回路是通路的特殊情况。但通常都是当起点与终点不同时才说是通路。
在一般情况下,如果顶点互不相同,必有边也互不相同。在初级通路(回路)的定义中既要求
顶点互不相同,又要求边互不相同, u,从
u
到v,
这只是为了排除一种特殊情况:沿着边(v)
再沿着这条边回到v。它不是初级回路。根据定义,初级通路(回路)都是简单通路(回路),
但反之不真。
通路和回路是图的子图。图5-7给出了通路、回路的示意图。图5-7(a)为v0 到v4 的
长为4的初级通路(路径)。图5-7(c)为v0 到v7 的长为8的简单通路。图5-7(e)是v0 到
v0 的长为5的初级回路。图5-7(g)为v0 到v0 长为8的简单回路。图5-7(b)、图5-7(d)、
图5-f)、-h) 简单通路、简单回路的示意图。
7(图57(分别为有向图中的初级通路、初级回路、
在有向图的通路或回路中,注意箭头方向的一致性。
在无向图中,环和两条平行边构成的回路分别为长度为1和2的初级回路(圈)。在有
向图中,环和两条方向相反边构成的回路分别为长度为1和2的初级回路(圈)。
图中的通路和回路有下述性质。
在一个
n
阶图中,若从顶点
u
到v(u≠v)存在通路,则从
u
到
v
存在长度
小于或等于n-1的通路。
证明设v0e1v1e2v2…是从u=v0 到v=
l
的一个通路,如果l>n-1,由于图中只
有
n
个顶点,在v0,vl 中(e) 一(v) 定有两个是相同的。(v) 设vi(l) =vj
,那么viei+1vi+1…ejvj
定理5.3
v1,…,i<j,
是一条回路,删去这条回路,得到v0e1v1…viej+1…elvl
仍是从u=v0 到v=vl
的一个通路,
第5章图的基本概念·125·
图5-
7
其长度减少j-i。如果它的长度仍大于n-1,则可以重复上述做法,直到得到长度不超过n-1
的通路为止。
推论在一个
n
阶图中,若从顶点
u
到v(存在通路,则从
u
到
v
存在长度小于
或等于n-1的初级通路。
u≠v)
下述定理和推论可类似证明。
在一个
n
阶图中,如果存在
v
到自身的回路,则存在
v
到自身长度小于或
等于
n
的回路。
推论在一个
n
阶图中,如果存在
v
到自身的简单回路,则存在
v
到自身长度小于或
等于
n
的初级回路。
在一个无向图
G
中,若从顶点
u
到
v
存在通路(当然从
v
到
u
也存在通
路), 则称
u
与
v
是连通的。规定任何顶点与自身总是连通的。
在一个有向图
D
中,若从顶点
u
到
v
存在通路,则称
u
可达v。规定任何顶点到自身
总是可达的。
若无向图
G
是平凡图或
G
中任意两个顶点都是连通的,则称
G
是连通
图;否则,称
G
是非连通图。
易知,在无向图中,顶点之间的连通关系是等价关系。设
G
为一个无向图,
R
是
G
中顶
点之间的连通关系。按照
R
可将V(G) 设为V1,Vk
。由它们导
定理5.4
定义5.12
定义5.13
划分成若干等价类, V2,…,
出的导出子图
G
[V1],
G
[V2],…,
G
[Vk
]称为
G
的连通分支,
G
的连通分支个数记
为p(G)。
例如,图5-8中的图有3个连通分支。
定义5.14
设
D
是一个有向图,如果略去
D
中各有向边的方向后所得无向图是连通
·126· 离散数学(第六版)
图,则称
D
是弱连通图,简称连通图。若
D
中任意两个顶点至少一个可达另一个,则称
D
是单向连通图。若
D
中任何一对顶点都是相互可达的,则称
D
是强连通图。
在图5-9中,图5-9(a)为强连通图,图5-9(b)为单向连通图,图5-9(c)是(弱)连通图。
图5-
8
图5-
9
显然,强连通图一定是单向连通图,单向连通图一定是弱连通图,但反之不真。
设无向图G=<V,E>,
'
.V,
'
中的所有顶点及其关联的边,称作删
V从
G
中删除V
除V'
,把删除V'
后的图记作G-V'。又设E'.E,从
G
中删除E'
中的所有边,称作删除
E'
,把删除E'
后的图记作G-E'。
定义5.15
设无向图G=<V,E>,V'.V,若p(G-V')>p(G), 且对V'
的任何
真子集V″
,p(G-V″)=p(G), 则称V'
为
G
的点割集。若点割集中只有一个顶点v,则称
v
为割点。
又E'.E,若p(G-E')>p(G), 且对E'的任何真子集E″
,
p(G-E″)=p(G), 则称E'是
G
的边割集,简称割集。若边割集中
只有一条边e,则称
e
为割边或桥。
在图5-v3,}、{为点割集,v6 都是割点。
10 中,{v5}、{v2 v6} v2、
{v2} 因为它的真子集{v2}已经是点割集了。类似
v4,不是点割集,
图510
地,{v6}也不是点割集。-v{
1,
}、{e5}、{e2,}、{e1,e5}、{e7}、{e8}、
e3,e4 e4,e1,e3 e2,e6,e6,
{等都是边割集, e6,e8}、{e8,e2,都不是边割集。
e9} 其中e9 是桥。{e7,e6,e1,e5}
5.图的矩阵表示
3
前面介绍了图的集合描述和图形表示,本节介绍图的矩阵表示。用矩阵表示图便于用
代数方法研究图,同时也便于计算机的存储和处理。由于矩阵的行列有固定的顺序,因此在
用矩阵表示图之前,必须规定图的顶点和边的顺序。本节讨论图的关联矩阵、邻接矩阵和可
达矩阵。
1.
无向图的关联矩阵
设无向图
G
=
E
>,{v1,v2,…,},
E
=e1,
}, 令mi为顶点v与边ej
的关联次数,称()为
G
的关联
矩
<V,
V
=vn
{e2,…,
emj i
mijn×m
阵,记为
M
(G)。
显然mij
的可能取值为0(vi
与ej
不关联)、1(vi
与ej
关联1
次)、2(与ej
关联2次,即ej
是以v为端点的环)。例如,图5-11 图5-11
vi i
的关联矩阵为
M (G)=
1 1 1 0 0
0 1 1 1 0
1 0 0 1 2
0 0 0 0 0
.
è
....
.
.
.
÷÷÷÷
÷
无向图的关联矩阵具有下述性质。
(1)每列恰好有两个1或一个2,这是因为每条边关联两个顶点(环关联的两个顶点重合)。
(2)第i 行元素之和为vi 的度数,Σm
j=1
mij =d(vi)。
(3)所有元素之和等于2m ,即
Σm
j=1Σn
i=1
mij =Σn
i=1Σm
j=1
mij =Σn
i=1
d(vi)=2m
这正是握手定理的内容。
(4)vi 为孤立点当且仅当第i 行全为0。如上面的第4行。
(5)ej 与ek 为平行边当且仅当第j 列与第k 列相同。如上面的第2列和第3列。
给定图G 的关联矩阵,不难画出G 的图形(在同构的意义下)。
2.有向图的关联矩阵
这里要求有向图D 中没有环。设无环有向图D =<V,E >,V ={v1,v2,…,vn },E =
{e1,e2,…,em },令
mij =
1, vi 为ej 的始点
0, vi 与ej 不关联
-1, vi 为ej 的终点
ì
.
í
..
..
则称(mij)n×m 为D 的关联矩阵,记作M (D )。
例如,图5-12的关联矩阵为
M (D )=
1 -1 0 0 0
-1 0 1 -1 1
0 0 0 0 -1
0 1 -1 1 0
.
è
....
.
.
.
÷÷÷÷
÷
有向图的关联矩阵具有下述性质:
(1)每列恰好有一个1和一个-1。
(2)第i 行1的个数等于d+ (vi),-1的个数等于d- (vi)。M (D )中所有1的个数等
于所有-1的个数,都等于m 。
3.有向图的邻接矩阵
设有向图D =<V,E>,V={v1,v2,…,vn },|E|=m 。令a(1) ij 为vi 邻接到vj 的边的
条数,称(a(1) ij )n×n 为D 的邻接矩阵,记作A(D )。
例如,图5-13的邻接矩阵为
第5章 图的基本概念·127·
图 5-12
图 5-13
A(D )=
1 2 1 0
0 0 1 0
0 0 0 1
0 0 1 0
.
è
....
.
.
.
÷÷÷÷
÷
有向图的邻接矩阵具有下述性质。
(1)第i 行元素之和等于d+ (vi),Σn
j=1
a(1) ij =d+ (vi)。
(2)第j 列元素之和等于d- (vj),Σn
i=1
a(1) ij =d- (vj)。
(3)所有元素之和等于边数,Σn
i=1Σn
j=1
a(1) ij =m 。
每条边是一条长度为1的通路,而环是长度为1的回路,因而Σn
i=1Σn
j=1
a(1) ij 是D 中长度为
1的通路(含回路)数,而Σn
i=1
a(1) ii 为D 中长度为1的回路总数。一般地,记A =A(D ),Al =
(a(l) ij )n×n 。可以证明下述定理和推论。
定理5.5 设A 为有向图D 的邻接矩阵,V={v1,v2,…,vn},则Al(l≥1)中元素a(l) ij
为vi 到vj 长度为l 的通路数,Σn
i=1Σn
j=1
a(l) ij 为D 中长度为l 的通路(含回路)总数,其中
Σn
i=1
a(l) ii 为D 中长度为l 的回路数。
推论 设Br=A+A2+…+Ar(r≥1),则Br 中元素b(r) ij 为D 中vi 到vj 长度小于或等
于r 的通路数,Σn
i=1Σn
j=1
b(r) ij 为D 中长度小于或等于r 的通路(含回路)总数,其中Σn
i=1
b(r) ii 为D
中长度小于或等于r 的回路总数。
注意:在这里通路和回路可以是初级的、简单的,也可以是复杂的,并且把回路看成通
路的特殊情况,即在计算通路数时把回路包括在内。在计算通路数和回路数时是在定义的
意义下,而不是在同构的意义下。也就是说,当表示通路或回路的顶点边序列不同时认为它
们是不同的通路或回路。例如,在图5-12 中,v1e1v2e3v4e2v1、v2e3v4e2v1e1v2 和
v4e2v1e1v2e3v4 实际上是同一条回路,而在定义意义下它们是3条回路。
在图5-13中,计算得到
·128· 离散数学(第六版)