《9——第二部分通信网结构.ppt》由会员分享,可在线阅读,更多相关《9——第二部分通信网结构.ppt(241页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、通信网理论基础通信网理论基础 第二部分第二部分 通信网结构通信网结构南京邮电大学南京邮电大学张顺颐张顺颐2009年年3月月10日更新版日更新版1/26/20231參考書籍參考書籍n周炯槃:通信网理论基础,人民邮电出周炯槃:通信网理论基础,人民邮电出版社;版社;1991年;年;1/26/202321、图论基础、图论基础n网络结构用含点、线的图来表示,便于网络结构用含点、线的图来表示,便于研究;研究;n点:电路和网络的节点、各种通信设备点:电路和网络的节点、各种通信设备如交换机、节点机、路由器、传输设备、如交换机、节点机、路由器、传输设备、SDH等;等;n线:信道、各种有线、无线传输通路;线:信道
2、、各种有线、无线传输通路;1/26/20233图论基础图论基础基本定义:基本定义:n端集:端集:V=v1,v2,vn n边集:边集:E=e1,e2,en;n边集边集E 是端集是端集V 中中2个元的关系个元的关系R,即即 V V RE由是,由是,E 和和 V 组成图组成图G,记为:记为:G V,E;1/26/20234图论基础图论基础n几何图形表示网络的特点:几何图形表示网络的特点:1、在一个系统(网络)中,端点数目可以、在一个系统(网络)中,端点数目可以任意给定,链路则是其中任意两个端点任意给定,链路则是其中任意两个端点决定,它表示了决定,它表示了V 集中任意两个元之间集中任意两个元之间的关系
3、;的关系;2、若、若V i 和和Vj是端集中的任意两个元素,是端集中的任意两个元素,即即V i,Vj V,则由则由V i,Vj产生产生er,应应当满足条件:当满足条件:V i 和和Vj 是邻接关系。是邻接关系。1/26/20235图论基础图论基础3、邻接关系可以是任意选择的;、邻接关系可以是任意选择的;4、一般情况下,一个边集只能对应一对端,、一般情况下,一个边集只能对应一对端,(包括同一个端);(包括同一个端);5、但是多个(两个以上)的边,可以对应同一、但是多个(两个以上)的边,可以对应同一对端对端V i 和和Vj;定义:每一个边集所对应的两个端,定义:每一个边集所对应的两个端,V i 和
4、和Vj称称为与为与er有关联的端;有关联的端;存在边集存在边集er的两个端称为邻接端。的两个端称为邻接端。1/26/20236有向图和无向图有向图和无向图根据图的端间关系性质,可以把图分为有根据图的端间关系性质,可以把图分为有向图和无向图:向图和无向图:当当V i 和和Vj 的关系等价于的关系等价于Vj 和和V i 的关系时,的关系时,该图称为无向图;反之,称为有向图。该图称为无向图;反之,称为有向图。有向图和无向图,在通信网络中如同双工有向图和无向图,在通信网络中如同双工和单工传输信道。和单工传输信道。1/26/20237空图和孤立点图空图和孤立点图n空图:端集空图:端集V是空集,则不可能产
5、生边集是空集,则不可能产生边集E,这种图称为空图。空图是无端点的图,这种图称为空图。空图是无端点的图,当然也是无边的。当然也是无边的。n孤立点图:若边集孤立点图:若边集E是空集,但是端集可是空集,但是端集可以有元而不是空集,这些端集之间无联以有元而不是空集,这些端集之间无联系,这种图称为孤立点图。系,这种图称为孤立点图。n无端的图必无边,但是无边的图未必就无端的图必无边,但是无边的图未必就无端(点)。无端(点)。1/26/20238有限图和无限图有限图和无限图n当集合当集合V、E 都是有限集时,所构成的图都是有限集时,所构成的图称为有限图,一般遇到和讨论的都是有称为有限图,一般遇到和讨论的都是
6、有限图。限图。nV和和E 无限的情况,为无限图。无限的情况,为无限图。1/26/20239各种图的几何表示及性质各种图的几何表示及性质1、图的几何表示:、图的几何表示:端集端集V 中的元,用点表示;中的元,用点表示;边集边集E 中的元,用连线表示;中的元,用连线表示;示例:孤立点图;示例:孤立点图;无向图;无向图;有向图;有向图;1/26/202310关于边集的讨论关于边集的讨论1、图中某一边关联的两端,是同一个元、图中某一边关联的两端,是同一个元(端点),则称为自环;(端点),则称为自环;2、无向图中两个端之间存在两条或两条以、无向图中两个端之间存在两条或两条以上的边,则称为重边。重边的数量
7、并不上的边,则称为重边。重边的数量并不限定。重边可以合并,以简化计算。限定。重边可以合并,以简化计算。3、有向图中若重边的方向不同,则在通常、有向图中若重边的方向不同,则在通常的情况下,不称为重边,也不予合并。的情况下,不称为重边,也不予合并。但是有时也可以将其合并为无向边。但是有时也可以将其合并为无向边。1/26/202311关于边集的讨论关于边集的讨论4、无向边也可以分为两个方向相反的边,、无向边也可以分为两个方向相反的边,或是两个无向的边。或是两个无向的边。5、图的定义只考虑、规定其拓扑特性,并、图的定义只考虑、规定其拓扑特性,并不考虑其几何特性。这在网络中也是很不考虑其几何特性。这在网
8、络中也是很有用的。有用的。1/26/202312关于边集的讨论关于边集的讨论6、在需要考虑边集的几何特性时,应该对所讨、在需要考虑边集的几何特性时,应该对所讨论的边和端赋予某些数值这些数值称为论的边和端赋予某些数值这些数值称为“权权”或或“权值权值”,这种图称为,这种图称为“有权图有权图”。边或端的权,可以对应于网络的参数,例如:边或端的权,可以对应于网络的参数,例如:端:电压、交换机、节点机、路由器、光端机端:电压、交换机、节点机、路由器、光端机 等;等;边:电流、电阻、信道、带宽、速率、流量等;边:电流、电阻、信道、带宽、速率、流量等;1/26/202313图与集合图与集合子图:若图子图:
9、若图A的端集和边集分别为图的端集和边集分别为图G的端的端集和边集的子集(一部分),则图集和边集的子集(一部分),则图A是图是图G的子图。的子图。记为:记为:A G(图(图A是图是图G的子图);的子图);特例:特例:A=G(图(图A与图与图B相等);相等);推论:任何图都是自己的子图;推论:任何图都是自己的子图;若若AG,但,但A G,则,则A是是G的真子图;的真子图;若若AG,且,且GA,则必有则必有AG;1/26/202314图的运算图的运算设有两图,记为设有两图,记为G a 和和G b,由于我们现在只考虑图的拓扑性质,并不由于我们现在只考虑图的拓扑性质,并不考虑图的几何性质,因此图的运算,
10、是考虑图的几何性质,因此图的运算,是各图指定元素之间的运算。各图指定元素之间的运算。1/26/202315图的运算图的运算n并图:并图:若若G 中的端集和边集分别为图中的端集和边集分别为图 A和和B 中端中端集和边集的(合)并,则集和边集的(合)并,则G为图为图A和图和图B的并;的并;Vc=V a Vb,E=Ea Eb,则有:则有:G c=G a G b;1/26/202316图的运算图的运算n交图交图若若G 中的端集和边集分别为图中的端集和边集分别为图 A和和B 中端中端集和边集的公共部分,则集和边集的公共部分,则G为图为图A和图和图B的交;的交;Vd=V a Vb,Ed=Ea Eb,则有:
11、则有:Gd=G a G b;1/26/202317图的运算图的运算n差图:差图:从图从图G中去掉图中去掉图G和图和图G 的共有边和端(但的共有边和端(但是不影响结果形成图形),保留非共有是不影响结果形成图形),保留非共有的边及相关联的端,所得的图形,为差的边及相关联的端,所得的图形,为差图:图:Ve=V a Vb,Ee=Ea Eb,则有:则有:Ge=G a G b;1/26/202318图的运算图的运算n图的环和运算:图的环和运算:从图从图G a 和和 G b 的并图的并图G c=G a G b 中去中去掉图掉图G a 和和 G b 的共有部分,保留非共有的共有部分,保留非共有的边和端,得到环
12、和:的边和端,得到环和:Ge=G a G b;1/26/202319图的运算图的运算n空图的性质:空图的性质:1、若两图的交为空图(零),则两图的并、若两图的交为空图(零),则两图的并为该两图的直和(直接相加);为该两图的直和(直接相加);2、某图与其子图的差,为该两图的直差。、某图与其子图的差,为该两图的直差。若:若:G b Ga则:则:Ge=G a G b=G a-G b;1/26/202320图的运算图的运算n一般,由图的定义:一般,由图的定义:Ge=G a G b=G a G a G b;即图即图A和图和图B的差,等于从图的差,等于从图A中去掉图中去掉图A和图和图B的共有部分。的共有部
13、分。1/26/202321图的连接性图的连接性n端的度数:端的度数:图中某一端,与该端相关联的边的数目,图中某一端,与该端相关联的边的数目,称为该端的度数。称为该端的度数。1、端的度数的表示:、端的度数的表示:2、图的端的度数的性质:、图的端的度数的性质:3、链、径和环、链、径和环1/26/202322图的连接性图的连接性n端的度数的表示:端的度数的表示:d(v1)n有向图端的度数:有向图端的度数:nd(v1)表示离开或)表示离开或 从从v1射出的边数;射出的边数;nd(v1)表示进入或射入)表示进入或射入v1的边数;的边数;1/26/202323端的度数:端的度数:1、有、有n个端,个端,m
14、条边的端,必有条边的端,必有 n =d(vi)=2m;各端的度数之和为;各端的度数之和为 i=1 边数的边数的2倍;倍;2、任何图中,度数为奇数的端的数目必为、任何图中,度数为奇数的端的数目必为偶数(或为偶数(或为0););1/26/202324边序列、链、径和环边序列、链、径和环n边序列:有限条边的一种串行排列;在这种边序列:有限条边的一种串行排列;在这种排列中,边可以重复使用。排列中,边可以重复使用。n链:边序列中,去掉重复的边,即为链。链:边序列中,去掉重复的边,即为链。显然,链中是不存在重复的边的;显然,链中是不存在重复的边的;n径:径是既无重复的边,又无重复的端的边径:径是既无重复的
15、边,又无重复的端的边序列;径中,除起点和终点的度数是序列;径中,除起点和终点的度数是1外,外,其余任何一端的度数都是其余任何一端的度数都是2.n环:起点和终点是同一端的链,为环;环:起点和终点是同一端的链,为环;1/26/202325联结图联结图n联结图:图内任何两个端之间至少有一条径,联结图:图内任何两个端之间至少有一条径,则此图称为联结图。则此图称为联结图。n联结图中的各个端点都是相联的。否则为非联联结图中的各个端点都是相联的。否则为非联结图。结图。n联结图的特性:联结图是一个部分,而非联结联结图的特性:联结图是一个部分,而非联结图必然是多个部分。图必然是多个部分。n部分:指原图的一个子图
16、。而此子图是一个最部分:指原图的一个子图。而此子图是一个最大的联结图。大的联结图。1/26/202326联结图联结图n联结子图:是原图的一个子图。虽然原联结子图:是原图的一个子图。虽然原图是非联结图,但是组成该图的每个部图是非联结图,但是组成该图的每个部分(子图)都是联结图。分(子图)都是联结图。n最大的联结子图:组成该图的每个部分最大的联结子图:组成该图的每个部分都是联结图,并且是最大的子图。因为都是联结图,并且是最大的子图。因为如果该子图再加上属于该图其他的部分如果该子图再加上属于该图其他的部分边和端,必然是其它边和端,必然是其它“部分部分”的,显然的,显然就失去联结性,成为非联结图了。就
17、失去联结性,成为非联结图了。1/26/202327全联结图全联结图n全联结图:任何两端间都有边的图,称全联结图:任何两端间都有边的图,称为全联结图。为全联结图。n全联结图一般研究无向图。全联结图一般研究无向图。n无重边和自环的全联结图,其边数无重边和自环的全联结图,其边数m和和端数端数n之间的关系:之间的关系:mn(n-1)/2n全联结图是联结性最好的图。因此,骨全联结图是联结性最好的图。因此,骨干网一般要求由全联结图组成。干网一般要求由全联结图组成。1/26/202328正则图正则图n所有端的度数都相等的联结图,称为正则图。所有端的度数都相等的联结图,称为正则图。d(vi)常数;常数;i1,
18、2,3,n。n正则图的特点:由于各端的度数都相等,所以正则图的特点:由于各端的度数都相等,所以正则图的联结性最匀称。正则图的联结性最匀称。n无重边和自环的全联结图是正则图。此时,各无重边和自环的全联结图是正则图。此时,各端的度数端的度数 d(vi)n-1。n全联结图必然是正则图,但是正则图未必是全全联结图必然是正则图,但是正则图未必是全联结图。联结图。1/26/202329尤拉图尤拉图n各端度数都是偶数的图,称为尤拉图。此处偶各端度数都是偶数的图,称为尤拉图。此处偶数含数含2。n尤拉图可以是联结图也可以是非联结图。尤拉图可以是联结图也可以是非联结图。n尤拉图如果是非联结图,则其中的每个联结图尤
19、拉图如果是非联结图,则其中的每个联结图必然都是尤拉图。必然都是尤拉图。n尤拉图的特点:联结尤拉图中必定可以找到一尤拉图的特点:联结尤拉图中必定可以找到一个包含所有边的环;尤拉图中每个端的度数都个包含所有边的环;尤拉图中每个端的度数都是是2以上的偶数。必定满足各个端点一进一出以上的偶数。必定满足各个端点一进一出的条件,从而形成环。的条件,从而形成环。1/26/202330尤拉图尤拉图n反之,如果图中存在一个包含了所有边反之,如果图中存在一个包含了所有边的环,则该图必为联结的尤拉图。的环,则该图必为联结的尤拉图。n联结尤拉图的充要条件是图中存在一个联结尤拉图的充要条件是图中存在一个含所有边的闭链。
20、含所有边的闭链。n两个尤拉图的环和,仍为一个尤拉图。两个尤拉图的环和,仍为一个尤拉图。n一个非尤拉图,其中有几个子图可能是一个非尤拉图,其中有几个子图可能是尤拉图,并且这些尤拉子图的环和仍然尤拉图,并且这些尤拉子图的环和仍然是原图的尤拉子图。是原图的尤拉子图。1/26/202331M图图n图中只有两个端的度数是奇数,其余端的度数图中只有两个端的度数是奇数,其余端的度数是偶数,该图称是偶数,该图称M图。图。nM图可以是联结图,也可以是非联结图。图可以是联结图,也可以是非联结图。n非联结图的非联结图的M图中,除一个部分是图中,除一个部分是M图外,其图外,其余的部分均为尤拉图。余的部分均为尤拉图。n
21、M图中存在一个含所有边的链。其两个度数为图中存在一个含所有边的链。其两个度数为奇数的端点,一个是起点,一个是终点。奇数的端点,一个是起点,一个是终点。1/26/202332M图图nM图中不存在含所有边的环。故图中不存在含所有边的环。故M图不是图不是尤拉图。尤拉图。n任何一个尤拉图去掉一条边就构成任何一个尤拉图去掉一条边就构成M图图n反之,反之,M图在度数为奇数的两个端之间图在度数为奇数的两个端之间加一条边,就构成尤拉图。加一条边,就构成尤拉图。nM图可以实现最优化的路径。图可以实现最优化的路径。nM图的意义:邮递路线、一笔画、路由图的意义:邮递路线、一笔画、路由的优化和检测等;的优化和检测等;
22、1/26/202333汉密尔顿图(汉密尔顿图(H 图)图)n图中至少存在一个含所有的端的环,此图中至少存在一个含所有的端的环,此图称汉密尔顿图,即图称汉密尔顿图,即H 图。图。n汉密尔顿图中含所有端的环,称为汉密汉密尔顿图中含所有端的环,称为汉密尔顿环。尔顿环。n一个汉密尔顿图中可以有几个不同的汉一个汉密尔顿图中可以有几个不同的汉密尔顿环。密尔顿环。n汉密尔顿图的充要条件是:图中至少存汉密尔顿图的充要条件是:图中至少存在一个环含有所有的端。在一个环含有所有的端。1/26/2023342、树、树1、定义:任何两端之间都有径,且只有一、定义:任何两端之间都有径,且只有一条径,该图称为树。条径,该图
23、称为树。2、树的性质:、树的性质:n树是无环的联结图;因为树的任何两端树是无环的联结图;因为树的任何两端间只有一条径,不可能形成环。间只有一条径,不可能形成环。n树是最小的联结图;因为树的任何两端树是最小的联结图;因为树的任何两端间只有一条径,去掉其中任何一条径,间只有一条径,去掉其中任何一条径,则不成为联结图。则不成为联结图。1/26/202335树树n若树有若树有m条边、条边、n个端,则必有:个端,则必有:mn1;此论断可以用数学归纳法此论断可以用数学归纳法证明。证明。故,树的定义,也可以说:有故,树的定义,也可以说:有n个端、个端、n1条边的联结图,即为树。条边的联结图,即为树。n除单点
24、树外,树至少有两个端的度数为除单点树外,树至少有两个端的度数为1。1/26/202336树树3、树的分类:树可以分为:根树、星树、树的分类:树可以分为:根树、星树、线树等。线树等。4、主树:联结图、主树:联结图G,若,若T G,即,即T 是是 G的子图,且的子图,且T 含有含有G的所有端,则称的所有端,则称T是是G 的主树。的主树。1/26/202337树树n注意:主树是图注意:主树是图G 的一个子图,的一个子图,G本身不本身不一定是树。一定是树。n只有联结图才有主树,并且至少有一个只有联结图才有主树,并且至少有一个主树。非联结图没有主树。主树。非联结图没有主树。n有主树的图必为联结图,没有主
25、树的图有主树的图必为联结图,没有主树的图一定是非联结图。一定是非联结图。n图的主树的边称为树枝。非树枝的边称图的主树的边称为树枝。非树枝的边称为连枝。为连枝。1/26/202338图的阶和图的空度图的阶和图的空度n阶:联结图主树阶:联结图主树T 的树枝的数目,称为的树枝的数目,称为联结图联结图G的阶。的阶。n若图有若图有n个端,则它的阶是:个端,则它的阶是:(G)T n-1n图的空度:联结图图的空度:联结图G的连枝集中连枝的数,的连枝集中连枝的数,称为图称为图G的空度,记为的空度,记为。1/26/202339图的阶和图的空度图的阶和图的空度n若图有若图有m条边、条边、n个端时,其空度:个端时,
26、其空度:(G)GT mn1;图的空度和图的阶的关系:图的空度和图的阶的关系:(G)(G)m;n可见,图的主树的大小取决于其端的数可见,图的主树的大小取决于其端的数量。量。1/26/202340图的空度图的空度n图的空度图的空度(G)表示了主树覆盖该联结图的表示了主树覆盖该联结图的程度。程度。(G)越小,则主树对图的覆盖程度越小,则主树对图的覆盖程度越高。越高。(G)0,则表示图就是树,没有则表示图就是树,没有连枝。连枝。n图的空度图的空度(G)还可以表示图还可以表示图G的联结程度。的联结程度。(G)越大,即树的连枝越多,图的联结性越大,即树的连枝越多,图的联结性越好。越好。(G)0时的树,其联
27、结性是最差时的树,其联结性是最差的。这是最低的联结性。的。这是最低的联结性。1/26/202341非联结图的主树、主林和林补非联结图的主树、主林和林补n对于非联结图,可以把它分成对于非联结图,可以把它分成K个联结图,此个联结图,此时每个部分都是一个联结图。则每个部分时每个部分都是一个联结图。则每个部分(联结图)至少有一个主树。于是该非联结(联结图)至少有一个主树。于是该非联结图共有图共有K个主树。个主树。K个主树形成的集,称为主个主树形成的集,称为主林,余下的边形成的集称为林补。林,余下的边形成的集称为林补。1/26/202342非联结图非联结图n由于联结图的主树不是唯一的,故主林也不是唯一的
28、,由于联结图的主树不是唯一的,故主林也不是唯一的,林补也不是唯一的。林补也不是唯一的。n非联结图的阶和空度:若非联结图由非联结图的阶和空度:若非联结图由K个部分组成,个部分组成,n则非联结图的阶:则非联结图的阶:(G)T n-k;n非联结图的空度:非联结图的空度:(G)GT mnk;n可见,可见,k1时,就是联结图的情况。时,就是联结图的情况。1/26/202343非联结图的阶和空度非联结图的阶和空度n对于非联结图,主树和主林都不是唯一对于非联结图,主树和主林都不是唯一的,都可以有多个。但是其阶的,都可以有多个。但是其阶(G)和和空度空度(G)是确定的。是确定的。1/26/2023443、割和
29、环、割和环n讨论图的联结性时,需要研究树;讨论图的联结性时,需要研究树;n讨论图的破坏性时,则用讨论图的破坏性时,则用“割割”的概念。的概念。n割是指图的某些子集,它由边和端组成,割是指图的某些子集,它由边和端组成,若从图中去掉这些子集,则图的部分数若从图中去掉这些子集,则图的部分数增加。例如,原来图是联结的,去掉某增加。例如,原来图是联结的,去掉某一个或某些子集,联结图变成非联结图,一个或某些子集,联结图变成非联结图,该子集就是该子集就是“割割”。1/26/202345割端和割端集割端和割端集割端和割端集:割端和割端集:v 是图是图G的一个端,若去掉的一个端,若去掉v(及相关联的边)以后,使
30、得及相关联的边)以后,使得G的部分数增加,的部分数增加,则称则称v是是G的的“割端割端”。无割端的不可分图:有的图无割端,即在图中去无割端的不可分图:有的图无割端,即在图中去掉任何端,图的部分数不变。则这种图称为掉任何端,图的部分数不变。则这种图称为不可分图。无割端的图在通信中的地位很重不可分图。无割端的图在通信中的地位很重要。这种网络由于没有割端,所有任何端点要。这种网络由于没有割端,所有任何端点发生事故,也不会使得网络的部分数增加,发生事故,也不会使得网络的部分数增加,即网络的完整性不会收到破坏,稳定性很好。即网络的完整性不会收到破坏,稳定性很好。1/26/202346割端和割端集割端和割
31、端集n图去掉一个或者几个割端以后,部分数增加,图去掉一个或者几个割端以后,部分数增加,则这些端的集称为则这些端的集称为“割端集割端集”。n割端集对于网络的作用:网络存在割端集时,割端集对于网络的作用:网络存在割端集时,割端集受到破坏,或者发生事故,将使得网络割端集受到破坏,或者发生事故,将使得网络的完整性收到影响。的完整性收到影响。n图例图例316n割端集割端集n图中如果没有图中如果没有v5、v6,则该图为不可分图。则该图为不可分图。因为取消任何一端以后,仍然是联结图。因为取消任何一端以后,仍然是联结图。1/26/202347割端集、最小割端集割端集、最小割端集n最小割端集:图的割端集中存在端
32、数最最小割端集:图的割端集中存在端数最少的割端集,就是最小割端集。少的割端集,就是最小割端集。n最小割端集中割端的数量称为图的联结最小割端集中割端的数量称为图的联结度。度。n割端集的物理概念是,网络中若干端点割端集的物理概念是,网络中若干端点(割端)发生故障,将使得网络的联通(割端)发生故障,将使得网络的联通性受到影响,即不是完整的、统一的网性受到影响,即不是完整的、统一的网络。络。1/26/202348图的联结度图的联结度n图的联结度表示要破坏图的联结性的难图的联结度表示要破坏图的联结性的难度:度:n图的联结度越大,表示如果将图分成多图的联结度越大,表示如果将图分成多个部分,需要去掉的端点就
33、越多,网络个部分,需要去掉的端点就越多,网络越稳定,越不易被破坏;越稳定,越不易被破坏;n图的联结度越小,表示将图分成多个部图的联结度越小,表示将图分成多个部分时,只需要去掉少数的端点就可以了,分时,只需要去掉少数的端点就可以了,网络就不稳定,网络容易被破坏。网络就不稳定,网络容易被破坏。1/26/202349割边和割边集割边和割边集n设有一联结图设有一联结图G,S是其边子集(即若干是其边子集(即若干条边组成的子集),若在条边组成的子集),若在G中去掉中去掉S使得使得G成为非联结图,则称成为非联结图,则称S是是G的割边集。的割边集。n若若S是图是图G 的割边集,但如果的割边集,但如果S的任何真
34、的任何真子集都不再是割边集,则称子集都不再是割边集,则称S为割集。为割集。n可见,割集是最小的割边集。可见,割集是最小的割边集。n图图3171/26/202350研究割边集的意义研究割边集的意义n割边集的物理概念是,网络中如果若干链路割边集的物理概念是,网络中如果若干链路(边子集)发生故障,将使得网络成为非联结(边子集)发生故障,将使得网络成为非联结的,即不是完整的、统一的网络。的,即不是完整的、统一的网络。n对于图对于图317ne3,e4,e5,e6是割边集,不是割集;是割边集,不是割集;ne4,e5,e6,e1,e2,e1,e3,e6则是割集;则是割集;1/26/202351割集割集n最小
35、割边集的边数,称为图的结合度。最小割边集的边数,称为图的结合度。n图的结合度表示图的连通的程度。显然图的结合度表示图的连通的程度。显然图的结合度越大,说明最小割边集的边图的结合度越大,说明最小割边集的边数越多,这种情况下网络的可靠性越高,数越多,这种情况下网络的可靠性越高,因为使该图变成非联结图需要破坏的边因为使该图变成非联结图需要破坏的边数多。数多。1/26/202352关于图的讨论关于图的讨论*基本割集的概念:基本割集的概念:n割边集:图割边集:图G中去掉中去掉S,使得图使得图G成为非成为非联结图,则联结图,则S为图为图G的割边集;的割边集;n割集:若割集:若S的任何子集都不是的任何子集都
36、不是G的割边集,的割边集,则则S为割集。为割集。1/26/202353如何根据网络的主树求出割边如何根据网络的主树求出割边集?集?问题的提出:问题的提出:n如何对一个已知的网络,结合任一指定如何对一个已知的网络,结合任一指定的主树,求出其对应的割边集?的主树,求出其对应的割边集?n或者是如何求出其割集?或者是如何求出其割集?可以通过图(网络)的任一主树,从其基可以通过图(网络)的任一主树,从其基本割集得到。本割集得到。1/26/202354基本割集基本割集n由主树的树枝得出的割集,是基本割集。由主树的树枝得出的割集,是基本割集。即若即若T是联结图是联结图G的一个主树,取其中的一个主树,取其中的
37、一条树枝,加上某些连枝,则必能构的一条树枝,加上某些连枝,则必能构成一个割集,这种由树枝形成的割集就成一个割集,这种由树枝形成的割集就是基本割集。是基本割集。*基本割集只含有一条树枝。基本割集只含有一条树枝。1/26/202355基本割集基本割集*图图G有有n个端,则主树的树枝数为个端,则主树的树枝数为n1条。条。每次取其中一条树枝,加上若干连枝,每次取其中一条树枝,加上若干连枝,形成基本割集,共有形成基本割集,共有n1个。个。n图例。图例。n图图318的主树和连枝集。的主树和连枝集。1/26/202356基本割集的求法:图基本割集的求法:图318取任一主树,例如取任一主树,例如e1,e3,e
38、4,e6,则其则其连枝集为连枝集为e2,e5;n由一条树枝,加若干连枝,经判断,则可得基由一条树枝,加若干连枝,经判断,则可得基本割集:本割集:e1:S1e1,e5 e3:S2e3,e2 e4:S3e4,e5 e6:S4e6,e2,e5n这四个基本割集各与一条树枝对应,所以它们这四个基本割集各与一条树枝对应,所以它们是线性独立的。是线性独立的。1/26/202357基本割集基本割集*以基本割集中若干割集为基,用环和运算,可以生以基本割集中若干割集为基,用环和运算,可以生 4成一个子空间,形成成一个子空间,形成 2 115个个“元元”。则每个元或是一个割集,或是割集的并:则每个元或是一个割集,或
39、是割集的并:n当两个基本割集有公共连枝时,其环和是另一个割当两个基本割集有公共连枝时,其环和是另一个割集;集;n当两个基本割集无公共连枝时,其环和是两者的并。当两个基本割集无公共连枝时,其环和是两者的并。(环和运算:先并,后差运算;)(环和运算:先并,后差运算;)(子空间中元的个数,与树枝数有关;)(子空间中元的个数,与树枝数有关;)1/26/202358基本割集的求法基本割集的求法n基本割集的求法:图基本割集的求法:图318n 任取一主树,例如任取一主树,例如e1,e3,e4,e6,则其连枝集为则其连枝集为e2,e5;n则可得基本割集:则可得基本割集:e1:S1e1,e5 e3:S2e3,e
40、2 e4:S3e4,e5 e6:S4e6,e2,e5n这四个基本割集各与一条树枝对应,所以它们这四个基本割集各与一条树枝对应,所以它们是线性独立的。是线性独立的。1/26/202359基本割集的求法基本割集的求法将这四个基本割集相互进行环和运算,即取其中的将这四个基本割集相互进行环和运算,即取其中的2个、个、3个、个、4个基本割集进行环和(先并后差)运算:个基本割集进行环和(先并后差)运算:n每次取其中的每次取其中的2个基本割集进行环和运算,为个基本割集进行环和运算,为n=4中取中取2的组合,共的组合,共6种:种:S5 =S1 S2=S1S2 (S1与与S2无公共连枝无公共连枝)S6 =S1
41、S3=e1,e4 (S1与与S3有公共连枝)有公共连枝)S7 =S1 S4=e1,e2,e6(s1与与s4有公共连枝有公共连枝)S8 =S2 S3=S2S3 (s2与与s3无公共连枝)无公共连枝)S9 =S2 S4=e3,e5,e6(s2与与s4有公共连枝)有公共连枝)S10=S3 S4=e2,e4,e6(s3与与s4有公共连枝)有公共连枝)1/26/202360基本割集的求法基本割集的求法n 每次取其中的三个基本割集进行环和运算,为每次取其中的三个基本割集进行环和运算,为n中取中取3的组合,共的组合,共4种:种:S11=S1 S2 S3S1 S2 S6S2 (s2与与s6无公共连枝)无公共连
42、枝)S12=S1 S2 S4e1,e3,e6 S13=S1 S3 S4S6 S4 S6S4 (s6与与s4无公共连枝)无公共连枝)S14=S2 S3 S4e3,e4,e6 1/26/202361基本割集的求法基本割集的求法n每次取其中的四个基本割集进行环和运每次取其中的四个基本割集进行环和运算,为算,为n中取中取4的组合,共的组合,共1种:种:S15=S1 S2 S3 S4S6 S9 S6S91/26/202362基本割集的求法基本割集的求法n可见,共有:可见,共有:S1,S2,S3,S4,S6,S7,S9,S10,S12,S14 的结果为的结果为新的割集,共新的割集,共10个;个;n其它为割
43、集的并:其它为割集的并:S5,S8,S11,S13,S15 共共5个。割集的并是割边集,但个。割集的并是割边集,但不是最小割边集。因为进行并运算的两不是最小割边集。因为进行并运算的两个都是割集,因而它本身只能是割边集,个都是割集,因而它本身只能是割边集,而不可能是割集。而不可能是割集。1/26/202363基本割集的求法基本割集的求法n以以S5为例:为例:S5=S1 S2=S1S2 e1:S1e1,e5 e3:S2e3,e2nS1与与S2无公共连枝,其环和运算(先并无公共连枝,其环和运算(先并后差运算)中,在运算中无公共连枝被后差运算)中,在运算中无公共连枝被差掉,与并运算结果相同,所以,无公
44、差掉,与并运算结果相同,所以,无公共连枝的两个基本割集环和运算时,结共连枝的两个基本割集环和运算时,结果必为割集的并。果必为割集的并。1/26/202364基本割集的求法基本割集的求法n结论:结论:n当两个基本割集有公共连枝时,这两个当两个基本割集有公共连枝时,这两个基本割集的环和运算可以将其中的公共基本割集的环和运算可以将其中的公共连枝差掉,因而会生成一个新的割集;连枝差掉,因而会生成一个新的割集;n当两个基本割集无公共连枝时,这两个当两个基本割集无公共连枝时,这两个基本割集的环和运算不可能去掉任何一基本割集的环和运算不可能去掉任何一连枝,也就不可能生成一个新的割集。连枝,也就不可能生成一个
45、新的割集。但会生成新的割边集。但会生成新的割边集。1/26/202365 基本割集的求法基本割集的求法n以上的方法就是:以上的方法就是:1、从主树的树枝出发,得到联结图的基本割、从主树的树枝出发,得到联结图的基本割集;集;2、用环和运算,求得所有的割集;、用环和运算,求得所有的割集;求出图的任一主树对应的各个割集,就求出图的任一主树对应的各个割集,就得到哪几条边故障以后,图将失去连接得到哪几条边故障以后,图将失去连接性,成为非联结图。从而有利于网络的结构的性,成为非联结图。从而有利于网络的结构的维护。维护。1/26/202366基本环:基本环:n环:环是起点和终点为同一端的链。环:环是起点和终
46、点为同一端的链。n取一条连枝可以与某些树枝构成环。多条连枝取一条连枝可以与某些树枝构成环。多条连枝与若干条树枝当然也可以构成环。图与若干条树枝当然也可以构成环。图318n基本环:仅包含一条连枝的环,称为基本环。基本环:仅包含一条连枝的环,称为基本环。n环和基本环的数量:环和基本环的数量:n基本环由于由一条连枝与某些树枝构成,所有基本环由于由一条连枝与某些树枝构成,所有图的基本环最多只有图的基本环最多只有mn1个(即连枝数)个(即连枝数)1/26/202367基本环基本环基本环的数量等于连枝数,由于连枝数为基本环的数量等于连枝数,由于连枝数为 mn1条,条,m-n+1 故其环和为故其环和为2 1
47、个个“元元”。n由环和运算形成的由环和运算形成的“元元”中,有的是环,中,有的是环,有的是环的并。有的是环的并。1/26/202368环和基本环环和基本环n图图318nn5,m6,故主树树枝数为故主树树枝数为n14;n 连枝数为连枝数为642;n基本环数为基本环数为 2;m-n+1 2n环的数为环的数为2 12 -1=3;第三个环可以用基;第三个环可以用基本环的环和运算得到。本环的环和运算得到。n分别为分别为:设连枝为:设连枝为e2、e5n e2:C1e2,e3,e6;(基本环基本环)n e5:C2e5,e1,e6,e4;(;(基本环)基本环)n C3=C1 C2=e1,e2,e3,e4,e5
48、;1/26/202369环和基本环环和基本环n稍复杂的问题;稍复杂的问题;分析具有分析具有5个端、个端、7条边的图形(图条边的图形(图323)的基本环、环的组成;(留作作业)的基本环、环的组成;(留作作业)n图的对偶性:图的对偶性:两个边集两个边集E相同的图相同的图G1和和G2,若,若G2中每个无中每个无重复端的环都对应重复端的环都对应G1中的一个基本割集,反之中的一个基本割集,反之亦然,则亦然,则G1和和G2互为对偶图,或者称为两个互为对偶图,或者称为两个图具有对偶性。环与割集可以相互对应。图具有对偶性。环与割集可以相互对应。1/26/202370图的对偶性图的对偶性n由于图的对偶性,分析图
49、的割集,就等由于图的对偶性,分析图的割集,就等效于分析其对偶图的环。此点可在电路效于分析其对偶图的环。此点可在电路的分析中应用。的分析中应用。n图图320,G1中的三个割集个对应于中的三个割集个对应于G2中的三个环,即:中的三个环,即:G1中的割集中的割集e1,e2,e3与与G2中的环中的环 e1,e2,e3对应;对应;1/26/202371图的对偶性图的对偶性G1中的割集中的割集e1,e2,e3与与G2中的环中的环 e1,e2,e3对应;对应;G1中的割集中的割集e3,e4,e5与与G2中的环中的环 e3,e4,e5对应;对应;G1中的割集中的割集e1,e2,e4,e5 与与G2中的环中的环
50、 e1,e2,e4,e5 对应;对应;1/26/202372 图的对偶性图的对偶性n图图320,反之:,反之:G1中的六个环对应中的六个环对应G2中的六个割集,即中的六个割集,即 G1 中环中环e1,e2;与与G2 中对应边形成的割集中对应边形成的割集 G1中环中环 e2,e3,e4;与与G2中对应边形成的割集中对应边形成的割集 G1中环中环 e4,e5;与与G2中对应边形成的割集中对应边形成的割集 G1中环中环 e1,e3,e5;与;与G2中对应边形成的割集中对应边形成的割集 G1中环中环 e1,e3,e4 ;与;与G2中对应边形成的割集中对应边形成的割集 G1中环中环 e2,e3,e5;与