1
7.2 通路、回路与图的连通性
?简单通 (回 )路,初级通 (回 )路,复杂通 (回 )路
?无向连通图,连通分支
?弱连通图,单向连通图,强连通图
?点割集与割点
?边割集与割边 (桥 )
2
通路与回路
定义 给定图 G=<V,E>（ 无向或有向的 ）, G中顶点与边的交
替序列 ?=v0e1v1e2… elvl,
(1) 若 ?i(1?i?l),vi?1,vi是 ei的端点 (对于有向图,要求 vi?1是始点,
vi是终点 ),则称 ?为 通路,v0是 通路的起点,vl是 通路的终点,
l为 通路的长度, 又若 v0=vl,则称 ?为 回路,
(2) 若通路 (回路 )中所有顶点 (对于回路,除 v0=vl)各异, 则称为
初级通路 (初级回路 ).初级通路又称作 路径,初级回路又称
作 圈,
(3) 若通路 (回路 )中所有边各异,则称为 简单通路 (简单回路 ),
否则称为 复杂通路 (复杂回路 ),
3
通路与回路 (续 )
说明,
? 表示方法
① 用顶点和边的交替序列 (定义 ),如 ?=v0e1v1e2… elvl
② 用边的序列,如 ?=e1e2… el
③ 简单图中,用顶点的序列,如 ?=v0v1… vl
④ 非简单图中,可用混合表示法,如 ?=v0v1e2v2e5v3v4v5
? 环是长度为 1的圈,两条平行边构成长度为 2的圈,
? 在无向简单图中,所有圈的长度 ?3; 在有向简单图
中,所有圈的长度 ?2,
4
通路与回路 (续 )
? 在两种意义下计算的圈个数
① 定义意义下
在无向图中,一个长度为 l(l?3)的圈看作 2l个不同的
圈, 如 v0v1v2v0,v1v2v0v1,v2v0v1v2看作 3个不同的圈,
在有向图中,一个长度为 l(l?3)的圈看作 l个不同的
圈,
② 同构意义下
所有长度相同的圈都是同构的,因而是 1个圈,
5
通路与回路 (续 )
定理 在 n阶图 G中, 若从顶点 vi到 vj（ vi?vj） 存在通
路, 则从 vi到 vj存在长度小于等于 n?1的通路,
推论 在 n阶图 G中，若从顶点 vi到 vj（ vi?vj）存在通
路，则从 vi到 vj存在长度小于等于 n?1的初级通路,
定理 在一个 n阶图 G中，若存在 vi到自身的回路，则
一定存在 vi到自身长度小于等于 n的回路,
推论 在一个 n阶图 G中，若存在 vi到自身的简单回
路，则一定存在长度小于等于 n的初级回路,
6
无向图的连通性
设无向图 G=<V,E>,
u与 v连通, 若 u与 v之间有通路, 规定 u与自身总连通,
连通关系 R={<u,v>| u,v ?V且 u?v}是 V上的等价关系
连通图, 平凡图,任意两点都连通的图
连通分支, V关于 R的等价类的导出子图
设 V/R={V1,V2,…,Vk},G[V1],G[V2],…,G[Vk]是 G的
连通分支,其个数记作 p(G)=k,
G是连通图 ? p(G)=1
7
短程线与距离
u与 v之间的短程线, u与 v之间长度最短的通路
(u与 v连通 )
u与 v之间的距离 d(u,v),u与 v之间短程线的长度
若 u与 v不连通,规定 d(u,v)=∞,
性质,
d(u,v)?0,且 d(u,v)=0 ? u=v
d(u,v)=d(v,u)
d(u,v)+d(v,w)?d(u,w)
8
点割集
记 G?v,从 G中删除 v及关联的边
G?V?,从 G中删除 V?中所有的顶点及关联的边
G?e, 从 G中删除 e
G?E?,从 G中删除 E?中所有边
定义 设无向图 G=<V,E>,V??V,若 p(G?V?)>p(G)且
?V???V?,p(G?V??)=p(G),则称 V?为 G的 点割集, 若
{v}为点割集,则称 v为 割点,
9
点割集 (续 )
例 {v1,v4},{v6}是点割集,v6是割点,
{v2,v5}是点割集吗？
10
边割集
定义 设无向图 G=<V,E>,E??E,若 p(G?E?)>p(G)且 ?E???E?,
p(G?E??)=p(G),则称 E?为 G的 边割集, 若 {e}为边割集,则称 e
为 割边 或 桥,
在上一页的图中, {e1,e2},{e1,e3,e5,e6},{e8}等是边割集,
e8是桥, {e7,e9,e5,e6}是边割集吗？
几点说明,
Kn无点割集
n阶零图既无点割集, 也无边割集,
若 G连通, E?为边割集, 则 p(G?E?)=2
若 G连通,V?为点割集，则 p(G?V?)?2
11
有向图的连通性
设有向图 D=<V,E>
u可达 v,u到 v有通路, 规定 u到自身总是可达的,
可达具有自反性和传递性
D弱连通 (连通 ),基图为无向连通图
D单向连通, ?u,v?V,u可达 v 或 v可达 u
D强连通, ?u,v?V,u与 v相互可达
强连通 ?单向连通 ?弱连通
12
有向图的连通性 (续 )
定理 (强连通判别法 ) D强连通当且仅当 D中存在经过
每个顶点至少一次的回路
定理 (单向连通判别法 ) D单向连通当且仅当 D中存在
经过每个顶点至少一次的通路
(1) (2) (3)
例 下图 (1)强连通,(2)单连通,(3) 弱连通
13
有向图的 短程线与距离
u到 v的短程线, u到 v长度最短的通路 (u可达 v)
u与 v之间的距离 d<u,v>,u到 v的短程线的长度
若 u不可达 v,规定 d<u,v>=∞,
性质,
d<u,v>?0,且 d<u,v>=0 ? u=v
d<u,v>+d<v,w> ?d<u,w>
注意, 没有对称性
14
7.3 图的矩阵表示
?无向图的关联矩阵
?有向图的关联矩阵
?有向图的邻接矩阵
?有向图的可达矩阵
15
无向图的关联矩阵
平行边的列相同)4(
2)3(
),.,,,2,1()()2(
),.,,,2,1(2)1(
,
1
1
mm
nivdm
mjm
ji
ij
i
m
j
ij
n
i
ij
?
??
??
?
?
?
?
?
定义 设无向图 G=<V,E>,V={v1,v2,…,vn},E={e1,
e2,…,em},令 mij为 vi与 ej的关联次数, 称 (mij)n?m为 G
的关联矩阵, 记为 M(G),
性质
16
有向图的关联矩阵
?
?
?
?
?
?
?
的终点为，
不关联与，
的始点为
ji
ji
ji
ij
ev
ev
ev
m
1
0
,1
定义 设无环有向图 D=<V,E>,V={v1,v2,…,vn},
E={e1,e2,…,em},令
则称 (mij)n?m为 D的关联矩阵, 记为 M(D),
17
有向图的关联矩阵 (续 )
?
?
?
?
?
????
??
??
?
?
?
?
?
ji
ij
m
j
iij
m
j
iij
n
i
ij
m
nivdm
vdm
mjm
,
1
1
1
0)3(
,...,2,1),()1(
),()1()2(
),...,2,1(0)1(
性质
(4) 平行边对应的列相同
18
定义 设有向图 D=<V,E>,V={v1,v2,…,vn},E={e1,
e2,…,em},令 为顶点 vi邻接到顶点 vj边的条数，
称 ( )m?n为 D的邻接矩阵,记作 A(D),简记为 A,
性质
的回路数中长度为
的通路数中长度为
1)4(
1)3(
,...,2,1),()2(
,...,2,1),()1(
1
)1(
,
)1(
1
)1(
1
)1(
Da
Dma
njvda
nivda
n
i
ii
ji
ij
j
n
i
ij
i
n
j
ij
???
????
??
??
?
?
?
?
?
?
?
?
?
)1(
ija
)1(
ija
有向图的邻接矩阵
19
D中的通路及回路数
)(l
ija
)( l
iia
? ?
? ?
n
i
n
j
l
ija
1 1
)(
?
?
n
i
l
iia
1
)(
定理 设 A为 n阶有向图 D的邻接矩阵,则 Al(l?1)中
元素
为 D中 vi到 vj长度为 l 的通路数,
为 vi到自身长度为 l 的回路数,
为 D中长度为 l 的通路总数,
为 D中长度为 l 的回路总数,
20
D中的通路及回路数 (续 )
例 有向图 D如图所示,求 A,A2,A3,A4,
并回答诸问题,
(1) D中长度为 1,2,3,4的通路各有多
少条？ 其中回路分别为多少条？
(2) D中长度小于或等于 4的通路为多
少条？其中有多少条回路？
? ?
? ?
n
i
n
j
l
ijb
1 1
)(
?
?
n
i
l
iib
1
)(
推论 设 Bl=A+A2+… +Al(l?1),则 Bl中元素
为 D中长度小于或等于 l 的通路数,
为 D中长度小于或等于 l 的回路数,
21
例 (续 )
长度 通路 回路
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1004
0104
1005
0001
0103
1003
0104
0001
1002
0102
1003
0001
0101
1001
0102
0001
43
2
AA
AA
合计 50 8
1 8 1
2 11 3
3 14 1
4 17 3
22
有向图的可达矩阵
?
?
?
?
否则
可达
,1
,0 ji
ij
vv
p
定义 设 D=<V,E>为有向图,V={v1,v2,…,vn},令
称 (pij)n?n为 D的可达矩阵,记作 P(D),简记为 P,
性质,
P(D)主对角线上的元素全为 1,
D强连通当且仅当 P(D)的元素全为 1,
23
有向图的可达矩阵 (续 )
例 右图所示的有向图 D的可达矩阵为
?
?
?
?
?
?
?
?
?
?
?
?
?
1101
1101
1111
0001
P
7.2 通路、回路与图的连通性
?简单通 (回 )路,初级通 (回 )路,复杂通 (回 )路
?无向连通图,连通分支
?弱连通图,单向连通图,强连通图
?点割集与割点
?边割集与割边 (桥 )
2
通路与回路
定义 给定图 G=<V,E>（ 无向或有向的 ）, G中顶点与边的交
替序列 ?=v0e1v1e2… elvl,
(1) 若 ?i(1?i?l),vi?1,vi是 ei的端点 (对于有向图,要求 vi?1是始点,
vi是终点 ),则称 ?为 通路,v0是 通路的起点,vl是 通路的终点,
l为 通路的长度, 又若 v0=vl,则称 ?为 回路,
(2) 若通路 (回路 )中所有顶点 (对于回路,除 v0=vl)各异, 则称为
初级通路 (初级回路 ).初级通路又称作 路径,初级回路又称
作 圈,
(3) 若通路 (回路 )中所有边各异,则称为 简单通路 (简单回路 ),
否则称为 复杂通路 (复杂回路 ),
3
通路与回路 (续 )
说明,
? 表示方法
① 用顶点和边的交替序列 (定义 ),如 ?=v0e1v1e2… elvl
② 用边的序列,如 ?=e1e2… el
③ 简单图中,用顶点的序列,如 ?=v0v1… vl
④ 非简单图中,可用混合表示法,如 ?=v0v1e2v2e5v3v4v5
? 环是长度为 1的圈,两条平行边构成长度为 2的圈,
? 在无向简单图中,所有圈的长度 ?3; 在有向简单图
中,所有圈的长度 ?2,
4
通路与回路 (续 )
? 在两种意义下计算的圈个数
① 定义意义下
在无向图中,一个长度为 l(l?3)的圈看作 2l个不同的
圈, 如 v0v1v2v0,v1v2v0v1,v2v0v1v2看作 3个不同的圈,
在有向图中,一个长度为 l(l?3)的圈看作 l个不同的
圈,
② 同构意义下
所有长度相同的圈都是同构的,因而是 1个圈,
5
通路与回路 (续 )
定理 在 n阶图 G中, 若从顶点 vi到 vj（ vi?vj） 存在通
路, 则从 vi到 vj存在长度小于等于 n?1的通路,
推论 在 n阶图 G中，若从顶点 vi到 vj（ vi?vj）存在通
路，则从 vi到 vj存在长度小于等于 n?1的初级通路,
定理 在一个 n阶图 G中，若存在 vi到自身的回路，则
一定存在 vi到自身长度小于等于 n的回路,
推论 在一个 n阶图 G中，若存在 vi到自身的简单回
路，则一定存在长度小于等于 n的初级回路,
6
无向图的连通性
设无向图 G=<V,E>,
u与 v连通, 若 u与 v之间有通路, 规定 u与自身总连通,
连通关系 R={<u,v>| u,v ?V且 u?v}是 V上的等价关系
连通图, 平凡图,任意两点都连通的图
连通分支, V关于 R的等价类的导出子图
设 V/R={V1,V2,…,Vk},G[V1],G[V2],…,G[Vk]是 G的
连通分支,其个数记作 p(G)=k,
G是连通图 ? p(G)=1
7
短程线与距离
u与 v之间的短程线, u与 v之间长度最短的通路
(u与 v连通 )
u与 v之间的距离 d(u,v),u与 v之间短程线的长度
若 u与 v不连通,规定 d(u,v)=∞,
性质,
d(u,v)?0,且 d(u,v)=0 ? u=v
d(u,v)=d(v,u)
d(u,v)+d(v,w)?d(u,w)
8
点割集
记 G?v,从 G中删除 v及关联的边
G?V?,从 G中删除 V?中所有的顶点及关联的边
G?e, 从 G中删除 e
G?E?,从 G中删除 E?中所有边
定义 设无向图 G=<V,E>,V??V,若 p(G?V?)>p(G)且
?V???V?,p(G?V??)=p(G),则称 V?为 G的 点割集, 若
{v}为点割集,则称 v为 割点,
9
点割集 (续 )
例 {v1,v4},{v6}是点割集,v6是割点,
{v2,v5}是点割集吗？
10
边割集
定义 设无向图 G=<V,E>,E??E,若 p(G?E?)>p(G)且 ?E???E?,
p(G?E??)=p(G),则称 E?为 G的 边割集, 若 {e}为边割集,则称 e
为 割边 或 桥,
在上一页的图中, {e1,e2},{e1,e3,e5,e6},{e8}等是边割集,
e8是桥, {e7,e9,e5,e6}是边割集吗？
几点说明,
Kn无点割集
n阶零图既无点割集, 也无边割集,
若 G连通, E?为边割集, 则 p(G?E?)=2
若 G连通,V?为点割集，则 p(G?V?)?2
11
有向图的连通性
设有向图 D=<V,E>
u可达 v,u到 v有通路, 规定 u到自身总是可达的,
可达具有自反性和传递性
D弱连通 (连通 ),基图为无向连通图
D单向连通, ?u,v?V,u可达 v 或 v可达 u
D强连通, ?u,v?V,u与 v相互可达
强连通 ?单向连通 ?弱连通
12
有向图的连通性 (续 )
定理 (强连通判别法 ) D强连通当且仅当 D中存在经过
每个顶点至少一次的回路
定理 (单向连通判别法 ) D单向连通当且仅当 D中存在
经过每个顶点至少一次的通路
(1) (2) (3)
例 下图 (1)强连通,(2)单连通,(3) 弱连通
13
有向图的 短程线与距离
u到 v的短程线, u到 v长度最短的通路 (u可达 v)
u与 v之间的距离 d<u,v>,u到 v的短程线的长度
若 u不可达 v,规定 d<u,v>=∞,
性质,
d<u,v>?0,且 d<u,v>=0 ? u=v
d<u,v>+d<v,w> ?d<u,w>
注意, 没有对称性
14
7.3 图的矩阵表示
?无向图的关联矩阵
?有向图的关联矩阵
?有向图的邻接矩阵
?有向图的可达矩阵
15
无向图的关联矩阵
平行边的列相同)4(
2)3(
),.,,,2,1()()2(
),.,,,2,1(2)1(
,
1
1
mm
nivdm
mjm
ji
ij
i
m
j
ij
n
i
ij
?
??
??
?
?
?
?
?
定义 设无向图 G=<V,E>,V={v1,v2,…,vn},E={e1,
e2,…,em},令 mij为 vi与 ej的关联次数, 称 (mij)n?m为 G
的关联矩阵, 记为 M(G),
性质
16
有向图的关联矩阵
?
?
?
?
?
?
?
的终点为，
不关联与，
的始点为
ji
ji
ji
ij
ev
ev
ev
m
1
0
,1
定义 设无环有向图 D=<V,E>,V={v1,v2,…,vn},
E={e1,e2,…,em},令
则称 (mij)n?m为 D的关联矩阵, 记为 M(D),
17
有向图的关联矩阵 (续 )
?
?
?
?
?
????
??
??
?
?
?
?
?
ji
ij
m
j
iij
m
j
iij
n
i
ij
m
nivdm
vdm
mjm
,
1
1
1
0)3(
,...,2,1),()1(
),()1()2(
),...,2,1(0)1(
性质
(4) 平行边对应的列相同
18
定义 设有向图 D=<V,E>,V={v1,v2,…,vn},E={e1,
e2,…,em},令 为顶点 vi邻接到顶点 vj边的条数，
称 ( )m?n为 D的邻接矩阵,记作 A(D),简记为 A,
性质
的回路数中长度为
的通路数中长度为
1)4(
1)3(
,...,2,1),()2(
,...,2,1),()1(
1
)1(
,
)1(
1
)1(
1
)1(
Da
Dma
njvda
nivda
n
i
ii
ji
ij
j
n
i
ij
i
n
j
ij
???
????
??
??
?
?
?
?
?
?
?
?
?
)1(
ija
)1(
ija
有向图的邻接矩阵
19
D中的通路及回路数
)(l
ija
)( l
iia
? ?
? ?
n
i
n
j
l
ija
1 1
)(
?
?
n
i
l
iia
1
)(
定理 设 A为 n阶有向图 D的邻接矩阵,则 Al(l?1)中
元素
为 D中 vi到 vj长度为 l 的通路数,
为 vi到自身长度为 l 的回路数,
为 D中长度为 l 的通路总数,
为 D中长度为 l 的回路总数,
20
D中的通路及回路数 (续 )
例 有向图 D如图所示,求 A,A2,A3,A4,
并回答诸问题,
(1) D中长度为 1,2,3,4的通路各有多
少条？ 其中回路分别为多少条？
(2) D中长度小于或等于 4的通路为多
少条？其中有多少条回路？
? ?
? ?
n
i
n
j
l
ijb
1 1
)(
?
?
n
i
l
iib
1
)(
推论 设 Bl=A+A2+… +Al(l?1),则 Bl中元素
为 D中长度小于或等于 l 的通路数,
为 D中长度小于或等于 l 的回路数,
21
例 (续 )
长度 通路 回路
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1004
0104
1005
0001
0103
1003
0104
0001
1002
0102
1003
0001
0101
1001
0102
0001
43
2
AA
AA
合计 50 8
1 8 1
2 11 3
3 14 1
4 17 3
22
有向图的可达矩阵
?
?
?
?
否则
可达
,1
,0 ji
ij
vv
p
定义 设 D=<V,E>为有向图,V={v1,v2,…,vn},令
称 (pij)n?n为 D的可达矩阵,记作 P(D),简记为 P,
性质,
P(D)主对角线上的元素全为 1,
D强连通当且仅当 P(D)的元素全为 1,
23
有向图的可达矩阵 (续 )
例 右图所示的有向图 D的可达矩阵为
?
?
?
?
?
?
?
?
?
?
?
?
?
1101
1101
1111
0001
P
