《离散数学：第7章 图的基本概念 (2)》由会员分享，可在线阅读，更多相关《离散数学：第7章 图的基本概念 (2)（29页珍藏版）》请在金锄头文库上搜索。
1、7.2 通路、回路、图的连通性通路、回路、图的连通性 简简单单通通(回回)路路, 初初级级通通(回回)路路, 复复杂杂通通(回回)路路无向连通图无向连通图, 连通分支连通分支弱连通图弱连通图, 单向连通图单向连通图, 强连通图强连通图点割集与割点点割集与割点边割集与割边边割集与割边(桥桥) 1通路与回路通路与回路 定定义义 给给定定图图G=（无无向向或或有有向向的的），G中中顶顶点点与与边边的的交交替序列替序列 =v0e1v1e2elvl，(1) 若若 i(1 i l), vi 1, vi是是ei的的端端点点(对对于于有有向向图图, 要要求求vi 1是是始始点点, vi是是终终点点), 则则称
2、称 为为通通路路, v0是是通通路路的的起起点点, vl是是通通路路的终点的终点, l为为通路的长度通路的长度. 又若又若v0=vl，则称则称 为为回路回路.(2) 若若通通路路(回回路路)中中所所有有顶顶点点(对对于于回回路路, 除除v0=vl)各各异异，则则称称为为初初级级通通路路(初初级级回回路路).初初级级通通路路又又称称作作路路径径, 初初级级回回路路又称作又称作圈圈.(3) 若若通通路路(回回路路)中中所所有有边边各各异异, 则则称称为为简简单单通通路路(简简单单回回路路), 否则称为否则称为复杂通路复杂通路(复杂回路复杂回路).2说明(1) 初级通路初级通路(回路回路)是简单通路
3、是简单通路(回路回路), 但反之不真但反之不真初级通路初级通路非初级的简单通路非初级的简单通路初级回路初级回路非初级的非初级的简单回路简单回路3通路与回路通路与回路( (续续) )说明说明:n表示方法表示方法 用用 顶顶 点点 和和 边边 的的 交交 替替 序序 列列 (定定 义义 ), 如如 =v0e1v1e2elvl 用边的序列用边的序列, 如如 =e1e2el 简单图中简单图中, 用顶点的序列用顶点的序列, 如如 =v0v1vl 非简单图中非简单图中,可用混合表示法可用混合表示法,如如 =v0v1e2v2e5v3v4v5n环是长度为环是长度为1的圈的圈, 两条平行边构成长度为两条平行边构
4、成长度为2的圈的圈.n在无向简单图中在无向简单图中, 所有圈的长度所有圈的长度 3; 在有向简单图在有向简单图中中, 所有圈的长度所有圈的长度 2. 4通路与回路通路与回路( (续续) )n在两种意义下计算的圈个数在两种意义下计算的圈个数 定义意义下定义意义下 在在无无向向图图中中, 一一个个长长度度为为l(l 3)的的圈圈看看作作2l个个不不同同的的圈圈. 如如v0v1v2v0 , v1v2v0v1 , v2v0v1v2, v0v2v1v0 , v1v0v2v1 , v2v1v0v2看作看作6个不同的圈个不同的圈. 在在有有向向图图中中, 一一个个长长度度为为l(l 3)的的圈圈看看作作l个
5、个不不同同的的圈圈. 同构意义下同构意义下 所有长度相同的圈都是同构的所有长度相同的圈都是同构的, 因而是因而是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到自身的回路，则到自身的回路，则
6、一定存在一定存在vi到自身长度小于等于到自身长度小于等于n的回路的回路.推论推论 在一个在一个n阶图阶图G中，若存在中，若存在vi到自身的简单回到自身的简单回路，则一定存在长度小于等于路，则一定存在长度小于等于n的初级回路的初级回路. 6无向图的连通性无向图的连通性 设设无向图无向图G=,u与与v连通连通: 若若u与与v之间有通路之间有通路. 规定规定u与自身总连通与自身总连通.连通关系连通关系 R=| u,v V且且u v是是V上的等价关系上的等价关系连通图连通图:任意两点都连通的图任意两点都连通的图. 平凡图是连通图平凡图是连通图.连通分支连通分支: V关于连通关系关于连通关系R的的等价类
7、的导出子图等价类的导出子图 设设V/R=V1,V2,Vk, GV1, GV2, ,GVk是是G的连通分支的连通分支, 其个数记作其个数记作p(G)=k.G是连通图是连通图 p(G)=17短程线与距离u与与v之之间间的的短短程程线线:u与与v之之间间长长度度最最短短的的通通路路(设设u与与v连连通通)u与与v之间的距离之间的距离d(u,v):u与与v之间短程线的长度之间短程线的长度若若u与与v不连通不连通, 规定规定d(u,v)=.性质：性质：(1) d(u,v) 0, 且且d(u,v)=0 u=v(2) d(u,v)=d(v,u)(3) d(u,v)+d(v,w) d(u,w) 例如例如 a与
8、与e之间的短程线之间的短程线:ace,afe. d(a,e)=2, d(a,h)= abcde f ghi8点割集点割集 记记 G v: 从从G中删除中删除v及关联的边及关联的边 G V : 从从G中删除中删除V 中所有的顶点及关联的边中所有的顶点及关联的边 G e : 从从G中删除中删除e G E : 从从G中删除中删除E 中所有边中所有边定定义义 设设无无向向图图G=, V V, 若若p(G V )p(G)且且 V V , p(G V )=p(G), 则则称称V 为为G的的点点割割集集. 若若v为点割集为点割集, 则称则称v为为割点割点.9点割集点割集( (续续) )例例 v1,v4, v
9、6是点割集是点割集, v6是割点是割点. v2,v5是点割集吗？是点割集吗？ 10边割集边割集定定义义 设设无无向向图图G=, 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 为边割集，则为
10、边割集，则p(G E )=2若若G连通，连通，V 为点割集，则为点割集，则p(G V ) 2 11有向图的连通性有向图的连通性 设有向图设有向图D=u可达可达v: u到到v有通路有通路. 规定规定u到自身总是可达的到自身总是可达的.可达具有自反性和传递性可达具有自反性和传递性D弱连通弱连通(连通连通): 基图为无向连通图基图为无向连通图D单向连通单向连通: u,v V，u可达可达v 或或v可达可达u D强连通强连通: u,v V，u与与v相互可达相互可达强连通强连通单向连通单向连通弱连通弱连通 12有向图的连通性有向图的连通性( (续续) ) 定定理理(强强连连通通判判别别法法) D强强连连通
11、通当当且且仅仅当当D中中存存在在经经过每个顶点至少一次的回路过每个顶点至少一次的回路定定理理(单单向向连连通通判判别别法法) D单单向向连连通通当当且且仅仅当当D中中存存在经过每个顶点至少一次的通路在经过每个顶点至少一次的通路 (1)(2)(3)例例 下图下图(1)强连通强连通, (2)单连通单连通, (3) 弱弱连通连通13有向图的有向图的短程线与距离短程线与距离u到到v的短程线的短程线: u到到v长度最短的通路长度最短的通路 (u可达可达v)u与与v之间的距离之间的距离d: u到到v的短程线的长度的短程线的长度若若u不可达不可达v, 规定规定d=.性质：性质： d 0, 且且d=0 u=v
12、 d+d d 注意注意: 没有对称性没有对称性14作业：P173:T7.16自由练习自由练习:T7.17157.3 图的矩阵表示图的矩阵表示 无向图的关联矩阵无向图的关联矩阵有向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵有向图的邻接矩阵有向图的可达矩阵有向图的可达矩阵 16无向图的关联矩阵设设无无向向图图G=, V=v1, v2, , vn, E=e1, e2, , em. 令令mij为为vi与与ej的关联次数的关联次数, 称称(mij)n m为为G的关联矩阵的关联矩阵, 记为记为M(G). mij的可能取值为的可能取值为:0,1,2例如例如e1e2e3e4e5e6v5v1v2v3v4M(G
13、)=2 1 1 0 0 00 1 0 1 1 10 0 0 0 1 10 0 0 0 0 00 0 1 1 0 0 17关联矩阵的性质(6) ej是环是环 第第j列的一个元素为列的一个元素为2, 其余为其余为0(5) vi是孤立点是孤立点 第第i行全为行全为018无环有向图的关联矩阵则称则称(mij)n m为为D的关联矩阵的关联矩阵, 记为记为M(D).设设无无环环有有向向图图D=, V=v1, v2, , vn, E=e1, e2, , em. 令令(3) ej与与ek是平行边是平行边 第第j列与第列与第k列相同列相同(2) 第第i行行1的个数等于的个数等于d+(v), 第第i行行 1的个数
14、等于的个数等于d (v)性质性质:19实例v1v2v3v4e2e1e3e4e5e6e7M(D)= 1 1 0 0 0 1 1 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 0 020有向图的邻接矩阵设有向图设有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令令 为顶点为顶点vi邻接到邻接到顶点顶点vj边的条数，称边的条数，称( )n n为为D的邻接矩阵的邻接矩阵, 记作记作A(D), 简记作简记作A.21实例A=1 1 0 00 0 1 01 0 0 01 0 2 0v1v2v3v422 D中的通路及回路数中的通路及回路数定理定理 设
15、设A为为n阶有向图阶有向图D的邻接矩阵的邻接矩阵, 则则Al(l 1)中中元素元素 为为D中中vi到到vj长度为长度为 l 的通路数，的通路数， 为为vi到自身长度为到自身长度为 l 的回路数，的回路数， 为为D中长度为中长度为 l 的通路总数，的通路总数， 为为D中长度为中长度为 l 的回路总数的回路总数. 23D中的通路及回路数中的通路及回路数(续续)例例 有向图有向图D如图所示如图所示, 求求A, A2, A3, A4, 并回答诸问题：并回答诸问题：(1) D中长度为中长度为1, 2, 3, 4的通路各有多的通路各有多 少条？其中回路分别为多少条？少条？其中回路分别为多少条？(2) D中
16、长度小于或等于中长度小于或等于4的通路为多的通路为多 少条？其中有多少条回路？少条？其中有多少条回路？ 推论推论 设设Bl=A+A2+Al(l 1), 则则Bl中元素中元素 为为D中长度小于或等于中长度小于或等于l 的通路数，的通路数， 为为D中长度小于或等于中长度小于或等于l 的回路数的回路数.24例例(续续) 长度长度 通路通路 回路回路 合计合计 50 818 1211 3314 1417 325有向图的可达矩阵性质性质:P(D)主对角线上的元素主对角线上的元素pii全为全为1. D强连通当且仅当强连通当且仅当P(D)的元素全为的元素全为1.设有向图设有向图D=, V=v1, v2, ,
17、 vn, 令令 称称(pij)n n为为D的可达矩阵的可达矩阵, 记作记作P(D), 简记为简记为P. 26实例例例6.11 (1) v1到到v4,v4到到v1长为长为3的通路各有多少条的通路各有多少条?(2) v1到自身长为到自身长为1,2,3,4的回路各有多少条的回路各有多少条?(3) 长为长为4的通路共有多少条的通路共有多少条?其中有多少条回路其中有多少条回路?(4) 长度小于等于长度小于等于4的回路共有多少条的回路共有多少条?(5) 写出写出D的可达矩阵的可达矩阵, 并问并问D是强连通的吗是强连通的吗?解解v1v2v3v4A=1 2 1 00 0 1 00 0 0 10 0 1 027
18、实例(续)v1到到v4长为长为3的通路有的通路有 条条,A2=1 2 3 10 0 0 10 0 1 00 0 0 1A3=1 2 4 30 0 1 00 0 0 10 0 1 0A4=1 2 6 40 0 0 10 0 1 00 0 0 13v4到到v1长为长为3的通路有的通路有 条条0v1到自身长为到自身长为1,2,3,4的回路各有的回路各有 条条1长为长为4的通路共有的通路共有 条，其中有条，其中有 条回路条回路163长度小于等于长度小于等于4的回路共有的回路共有 条条8可达矩阵可达矩阵非非强连通强连通,单连通单连通 P=1 1 1 10 1 1 10 0 1 10 0 1 1A=1 2 1 00 0 1 00 0 0 10 0 1 0B4=4 8 14 80 0 2 20 0 2 20 0 2 228作业：P173:T7.18自由练习自由练习:T7.19-T7.2129
