图的矩阵表示.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,图的矩阵表示,无向图的关联矩阵,有向无环图的关联矩阵,有向图的邻接矩阵,有向图中的通路数与回路数,有向图的可达矩阵,1,无向图的关联矩阵,设无向图,G,=,V,=,v,1,v,2,v,n,E,=,e,1,e,2,e,m,.,令,m,ij,为,v,i,与,e,j,的关联次数,称(,m,ij,),n,m,为,G,的关联矩阵,记为,M,(,G,).,m,ij,的可能取值为:0,1,2,例如,e,1,e,2,e,3,e,4,e,5,e,6,v,5,v,1,v,2,v,3,v,4,M,(,G,)=,2 1 1 0 0 0,0 1 0 1 1 1,0 0 0 0 1 1,0 0 0 0 0 0,0 0 1 1 0 0,2,关联矩阵的性质,(6),e,j,是环,第,j,列的一个元素为2,其余为0,(5),v,i,是孤立点,第,i,行全为0,3,无环有向图的关联矩阵,则称(,m,ij,),n,m,为,D,的关联矩阵,记为,M,(,D,).,设无环有向图,D,=,V,=,v,1,v,2,v,n,E,=,e,1,e,2,e,m,.,令,(3),e,j,与,e,k,是平行边,第,j,列与第,k,列相同,(2)第,i,行1的个数等于,d,+,(,v,),第,i,行,1的个数等于,d,(,v,),性质:,4,实例,v,1,v,2,v,3,v,4,e,2,e,1,e,3,e,4,e,5,e,6,e,7,M,(,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,0,5,度为l 的回路数,等于D中长度为 l 的通路(含回路),v1到v4长为3的通路有 条,(4)长度小于等于4的回路共有多少条?,长为4的通路共有 条，其中有 条回路,1 1 0 0 0 1 1,度为l 的回路数,等于D中长度为 l 的通路(含回路),0 0 0 0 0 0,0 1 1 0 0 0 0,例1(1)v1到v4,v4到v1长为3的通路各有多少条?,(3)长为4的通路共有多少条?其中有多少条回路?,记作A(D),简记作A.,则称(mij)nm为D的关联矩阵,记为M(D).,0 0 1 1 0 0,例1(1)v1到v4,v4到v1长为3的通路各有多少条?,0 0 1 1 1 1 1,有向图的邻接矩阵,设有向图,D,=,V,=,v,1,v,2,v,n,E,=,e,1,e,2,e,m,令,为顶点,v,i,邻接到顶点,v,j,边的条数，称(),m,n,为,D,的邻接矩阵,记作,A,(,D,),简记作,A.,6,实例,A,=,1 1 0 0,0 0 1 0,1 0 0 0,1 0 2 0,v,1,v,2,v,3,v,4,7,有向图中的通路数与回路数,定理,14.11,设,A,为,n,阶有向图,D,的邻接矩阵,则,A,l,(,l,1),中元素,等于,D,中,v,i,到,v,j,长度为,l,的通路(含回路)数,等于,v,i,到自身长,度为,l,的回路数,等于,D,中长度为,l,的通路(含回路),总数,等于,D,中长度为,l,的回路总数.,8,有向图中的通路数与回路数(续),推论,设,B,l,=,A,+,A,2,+,A,l,(,l,1),则,B,l,中元素 等于,D,中,v,i,到,v,j,长度小于等于,l,的通路(含回路)数,等于,D,中,v,i,到,v,i,的长,度小于等于,l,的回路数,等于,D,中长度小于等于,l,的通路(含回路)数,为,D,中长度小于等于,l,的回路数.,9,例1(1)v1到v4,v4到v1长为3的通路各有多少条?,0 0 0 0 0 0,11 设A为n阶有向图D的邻接矩阵,则Al(l1)中元素,(3)ej与ek是平行边 第j列与第k列相同,v1到v2长为3的通路有1条,例1(1)v1到v4,v4到v1长为3的通路各有多少条?,(3)ej与ek是平行边 第j列与第k列相同,例1(1)v1到v4,v4到v1长为3的通路各有多少条?,有向图中的通路数与回路数,(2)第i行1的个数等于d+(v),第i行1的个数等于d(v),有向图中的通路数与回路数(续),11 设A为n阶有向图D的邻接矩阵,则Al(l1)中元素,设有向图D=,V=v1,v2,vn,E=e1,e2,em,令,称(pij)nn为D的可达矩阵,记作P(D),简记为P.,记作A(D),简记作A.,D中长为3的通路共有15条,其中回路3条,v1到v2长为3的通路有1条,长为4的通路共有 条，其中有 条回路,实例(续),A,=,1 1 0 0,0 0 1 0,1 0 0 0,1 0 2 0,A,2,=,1 1 1 0,1 0 0 0,1 1 0 0,3 1 0 0,A,3,=,2 1 1 0,1 1 0 0,1 1 0 0,3 3 1 0,A,4,=,3 2 1 0,1 1 0 0,2 1 1 0,4 3 1 0,v,1,到,v,2,长为3的通路有1条,v,1,到,v,3,长为3的通路有1条,v,1,到自身长为3的回路有2条,D,中长为3的通路共有15条,其中回路3条,v,1,v,2,v,3,v,4,10,有向图的可达矩阵,性质:,P,(,D,),主对角线上的元素全为1.,D,强连通当且仅当,P,(,D,),的元素全为1.,设有向图,D,=,V,=,v,1,v,2,v,n,令,称(,p,ij,),n,n,为,D,的可达矩阵,记作,P,(,D,),简记为,P,.,11,实例,例1,(1),v,1,到,v,4,v,4,到,v,1,长为3的通路各有多少条?,(2),v,1,到自身长为1,2,3,4的回路各有多少条?,(3)长为4的通路共有多少条?其中有多少条回路?,(4)长度小于等于4的回路共有多少条?,(5)写出,D,的可达矩阵,并问,D,是强连通的吗?,解,v,1,v,2,v,3,v,4,A,=,1 2 1 0,0 0 1 0,0 0 0 1,0 0 1 0,12,实例(续),v,1,到,v,4,长为3的通路有 条,A,2,=,1 2 3 1,0 0 0 1,0 0 1 0,0 0 0 1,A,3,=,1 2 4 3,0 0 1 0,0 0 0 1,0 0 1 0,A,4,=,1 2 6 4,0 0 0 1,0 0 1 0,0 0 0 1,3,v,4,到,v,1,长为3的通路有 条,0,v,1,到自身长为1,2,3,4的回路各有 条,1,长为4的通路共有 条，其中有 条回路,16,3,长度小于等于4的回路共有 条,8,可达矩阵,非强连通,单连通,P,=,1 1 1 1,0 1 1 1,0 0 1 1,0 0 1 1,13,