离散数学第十四讲
2006-5-24
北京邮电大学电子工程学院
2
例7.4 观察下列图,试分别给出一条通路、简单通路、 初级通路和圈?
e1 v2
e5 v4
v1 e3 e2
e4 e6 e8
通路:v1e2v3e3 v2e3v3e4v2e6v5e7v3 简单通路: v1e2v3e4v2e6v5e7v3 v3 初级通路:v1e2v3 e7 圈:v3e4v2e6v5e7v3
2006-5-24
北京邮电大学电子工程学院
12
7.3.1 无向图的关联矩阵
定义7.21 设G=<V,E>,V={v1,v2,…vn}, E={e1,e2,…em},令mij为顶点vi 与边 ej 的关联次数,则称
(mij)n×m为图G的关联矩阵,记为M(G)
v1
v6
⎡1 0 1 0 1 0 1 0⎤
e1
e7 e8
⎢⎢1
1
0
0
0
0
0
0
⎥ ⎥
v2 e3 e2
e5
v5
e6
M
(G
)
=
⎢0 ⎢⎢0
⎢0
1 0 0
1 0 0
1 1 0
0 1 0
0 1 1
0 0 1
0⎥
0
⎥ ⎥
1⎥
v3 e4 v4
⎢
⎥
⎣0 0 0 0 0 0 0 1⎦
(a)
2006-5-24
北京邮电大学电子工程学院
13
无向图的关联矩阵的性质:
北京邮电大学电子工程学院
1
eΓ定和度l∈,义v=Elv分当7,0e.别11v其v40称1=中e给v2为l…e时定i通是,e图l路关v称lG称Γ联=此为<的顶通V顶起点,路E点点v>为i-,v1和,0回v到设j终的路vv点l边0的。, ,,v通1…l则路称交v,为l∈替简通V序,称路列e为Γ1,路的e2。…长v0 若路Γ的所有边e1,e2… el互不相同,则称Γ为简单
通路或一条迹;若回路中的所有边互不相同,则称回路
为简单回路。
定不相若同Γ)的,所则有称顶Γ点为v0初,v1级…通vl路互或不一相条同路(径此;时若所回有路边中一 除v0=vl外,其余顶点各不相同(所有边也各不相同), 则称此回路为初级回路或圈。
由以上定义可知:初级通路(回路)一定是简单通
路(回路),但反之不成立。
n×n
v1
v2
2006-5-24
v4
⎡1 2 1 0⎤
A(D) = ⎢⎢0 0 1 0⎥⎥
⎢0 0 0 1⎥
v3
⎢⎣0 0 1 0⎥⎦
北京邮电大学电子工程学院
18
A( D)有如下性质:
n
nn
n
∑ ∑ ∑ ∑ (1) ( ) ai(j1) = d + νi , ( ) ai(j1) = d + νi = m
j =1
i=1 j=1
i =1
n
nn
n
∑ ∑ ∑ ∑ (2) ( ) ai(j1) = d − νi , ( ) ai(j1) = d − νi = m
i =1
j=1 i=1
j =1
(
3)
有
(1)
,
(
2
)
n
可知,∑
n
∑
ai(j1)为D中边的总数,也
i=1 j=1
∑ 是D中长度为1的通路总数; n ai(i1)为D中环的个 i =1
2006-5-24
北京邮电大学电子工程学院
14
m
∑ (4) mij = 0 ⇔ νi是孤立。 j =1
(5) 若第j列与第k列相同,ej与ek平行。
7.3.2 有向图的关联矩阵
定义7.22 设D=<V,E>中无环存在,V={v1,v2,…vn}, E={e1,e2,…em},令
mij
=
⎧ ⎪ ⎨
1 0
最小割点集)。若某一个顶点构成点割集,则称该顶
点为割点。
a
f
a
e
f 左边的图,点e
b
eb
即是割点,但 其余顶点均不
是割点。
c
d
c
d
(a)
(b)
2006-5-24
北京邮电大学电子工程学院
8
定义7.18 设无向图G=<V,E>为连通图,若有边集 E1⊂E,使图G删除了E1的所有边后,所得的子图是不 连通的,而删除了E1的任何真子集后,所得到的子图 仍是连通图,则称E1是G的边割集(使得V不连通的最 小割边集)。若某一条边构成一个边割集,则称该顶 点为割边(或桥)。
6 03 )
a1(34 )
= = =
3,ν 4,ν 6,ν
1到ν 1到ν 1到ν
3长度为 3长度为 3长度为
2的通路有 3的通路有 4的通路有
3条 4条 6条
a1(12) = 1,ν 1到ν 1长度为 2的通路有 1条 a1(13) = 1,ν 1到ν 1长度为 3的通路有 1条 a1(14) = 1,ν 1到ν 1长度为 4的通路有 1条
n
(1) ∑ mij = 2 ( j = 1, 2, , m ) i =1
这说明每条边关联2个顶点(环关联的两个顶点重合)。
n
(2) ∑ mij = d (νi ) j =1
第 i 行元素之和为顶点vi的度数。
nn
n
(3) 2m = ∑ ∑ mij = ∑ d (νi )
i=1 i=1
i =1
这正是握手定理的结论。
2006-5-24
北京邮电大学电子工程学院
20
⎡1 2 3 1⎤
⎡1 2 4 3⎤
A2 (D) = ⎢⎢0 0 0 1⎥⎥, A3 (D) = ⎢⎢0 0 1 0⎥⎥
⎢0 0 1 0⎥
⎢0 0 0 1⎥
⎢⎣0 0 0 1⎥⎦
⎢⎣0 0 1 0⎥⎦
⎡1
A4 (D) = ⎢⎢0
⎢0 ⎢⎣0
2 0 0 0
d(vi,vj)满足下列性质: (1) d(vi,vj)≥0,若vi=vj,则等号成立。 (2)满足三角不等式,即:
d(vi,vj)+ d(vj,vk)≥ d(vi,vk) 无向图中,还有对称性,即:d(vi,vj)= d(vj,vi)
2006-5-24
北京邮电大学电子工程学院
10
定义7.20 若D是一个有向图,如果略去D中各有向边的 方向后所得无向图G是连通的,则称D是弱连通图;若D 中任意两个顶点至少一个可达另一个,则称D为单向连 通图;若D中任意两个顶点都是相互可达的,则称D是强
讨论的是连通性,而状态空间的分解讨论的是可达
性)
2006-5-24
北京邮电大学电子工程学院
6
定义7.16 若图G只有一个连通分支,则称G是连通图 (类似于马氏链的不可约性)。
对于连通图,常常因删除了图中的点或边,而影响
了图的连通性。所谓在图中删除顶点v,即是把v及与v关
联的边全部删除,如在下图(a)中删除顶点e得
mn
⇒ ∑ ∑ mij = 0(M (D)中所有元素的代数和为 0) j=1 i=1
( ) ( ) m
m
∑ ∑ (2) mij = 1 = d + (ν i ), mij = −1 = −d − (ν i )
j=1
j=1
( ) ( ) n m
n
nm
⇒ ∑ ∑ mij = 1 = ∑ d + (ν i ) = m = −∑ ∑ mij = −1
ν
i为e
的始点
j
ν i与e j不关联
⎪⎩− 1
ν
i为e
的终点
j
则:称 (mij)n×m为图D的关联矩阵。
2006-5-24
北京邮电大学电子工程学院
15
v1 e1
v6
e7 e8
e9
v2
e3
e5
v5
e2
e6
e4 v3
v4 ⎡ 1 0 1 0 1 0 1 0 0 ⎤
(a)
M(D)
=
⎢⎢−1
⎢0
⎢ ⎢
v5
2006-5-24
北京邮电大学电子工程学院
3
图中的通路和回路有如下性质:
定理7.3 在一个n阶图中,若从顶点vi到vj (vi ≠ vj)存 在一条通路,则从vi到vj 存在长度小于等于n-1的通 路。
证明:若从顶点vi到vj (vi ≠ vj)存在一条通路,该路 上的顶点序列是:vi, … vk… vj,如果这条路有l条边, 则序列中必有l+1个顶点。若l+1>n,即 l>n-1,则必有 顶点vs 在序列中不止出现一次,即必有顶点序列vi, … vs… vs… vj,那么在路上去掉从vs到vs的这些边,仍是 vi到vj 的一条路;若此路的长度仍然大于n-1,则重复 进行以上过程,直到找到vi到vj 的一条长度小于等于n1的路为止。
0
1 −1 0
0 −1 0
0 1 −1
0 0 −1
0 0 −1
0 0 0
0 0 0
0
⎥ ⎥
0⎥
0
⎥ ⎥
⎢ 0 0 0 0 0 1 −1 1 −1⎥
⎢
⎥
⎢⎣ 0 0 0 0 0 0 0 −1 −1⎥⎦
2006-5-24
北京邮电大学电子工程学院
16
有向图的关联矩阵的性质:
n
(1)∑ mij = 0, j = 1,2, m, i =1
7.2 通路、回路、图的连通性
深刻理解通路与回路、简单通路、简单回路、初级 通路、初级回路、无向图顶点间的连通、有向图顶点 间的可达等概念