5欧拉图与汉密尔顿图.ppt
《5欧拉图与汉密尔顿图.ppt》由会员分享,可在线阅读,更多相关《5欧拉图与汉密尔顿图.ppt(47页珍藏版)》请在三一文库上搜索。
1、1,图的矩阵表示,1. 关联矩阵M(D), M(G) 2. 邻接矩阵A(D), 邻接矩阵A(G) 3. 用A的幂求不同长度通路(回路)总数 4. 可达矩阵P(D), 连通矩阵P(G),2,无向图关联矩阵,设G=是无向图,V=v1,v2,vn, E=e1,e2,em 关联矩阵(incidence matrix): M(G)=mijnm,(每个顶点确定一行,每条边确定一列), mij = vi与ej的关联次数 2, vi与ej关联,且ej是环 mij = 1, vi与ej关联,且ej不是环 0, vi不与ej关联,3,无向图关联矩阵(例),v1,v2,v4,v3,e1,e2,e3,e4,e6,e5
2、,4,无向图关联矩阵(性质),每列和为2: ni=1mij=2 ( ni=1mj=1mij=2m ) 每行和为d(v): d(vi)=mj=1mij 孤立点:全0行 平行边: 相同两列 环:对应列中只有一个2其余是0,5,有向图关联矩阵,设D=是无环有向图, V=v1,v2,vn, E=e1,e2,em 关联矩阵(incidence matrix): M(D)=mijnm , (每个顶点确定一行,每条边确定一列) 1, vi是ej的起点 mij = 0, vi与ej不关联 -1, vi是ej的终点,6,有向图关联矩阵(例),v1,v2,v4,v3,e1,e2,e3,e5,e4,e6,7,有向图
3、关联矩阵(性质),每列和为零: ni=1mij=0 每行绝对值和为d(v): d(vi)=mj=1mij, 其中1的个数为d+(v), -1的个数为d-(v) 握手定理: ni=1mj=1mij=0 平行边: 相同两列,8,无向图邻接矩阵,设G=是无向简单图,V=v1,v2,vn 邻接矩阵(adjacence matrix): A(G)=aijnn, aii=0, 1, vi与vj相邻,ij aij = 0, vi与vj不相邻,v1,v2,v4,v3,9,无向图邻接矩阵(性质),A(G)对称: aij= aji 每行(列)和为顶点度: ni=1aij=d(vj) 握手定理: ni=1nj=1a
4、ij=ni=1d(vj)=2m,v2,v3,10,邻接矩阵与通路数,设A(D)=A=aijnn, Ar=Ar-1A (r2), Ar=aij (r)nn, 定理1: aij (r) =从vi到vj长度为r的通路总数ni=1nj=1aij (r) =长度为r的通路总数 ni=1aii (r) =长度为r的回路总数. #,整数乘和整数加,11,用邻接矩阵求通路数(例),12,邻接矩阵与通路数,设Ar=Ar-1A,(r2), Ar=aij(r)nn, 推论1: aii (2) =d(vi). # 推论2: G连通距离d(vi,vj)=minr|aij(r)0,ij. #,13,连通矩阵,只考虑有无,
5、不考虑有多少条 设G=是无向简单图, V=v1,v2,vn, 连通矩阵: P(G)=pijnn, 1, 若vi与vj连通 pij = 0, 若vi与vj不连通,14,连通矩阵(性质),主对角线元素都是1: viV, vi与vi连通 连通图: 所有元素都是1 伪对角阵: 对角块是连通分支的连通矩阵 设Br=A+A2+Ar= bij(r)nn, 则ij, pij=1 bij(n-1) 0,15,连通矩阵(例),v1,v4,v3,v2,v6,v5,16,有向图邻接矩阵,设D=是有向图,V=v1,v2,vn 邻接矩阵(adjacence matrix): A(D)=aijnn, aij = 从vi到v
6、j的边数,v1,v2,v4,v3,17,有向图邻接矩阵(性质),每行和为出度: nj=1aij=d+(vi) 每列和为入度: ni=1aij=d-(vj) 握手定理: ni=1nj=1aij=ni=1d-(vj)=m 环个数: ni=1aii,18,邻接矩阵与通路数,设A(D)=A=aijnn, Ar=Ar-1A (r2), Ar=aij(r)nn, 定理2: aij(r)=从vi到vj长度为r的通路总数 ni=1nj=1aij(r)=长度为r的通路总数 ni=1aii (r) =长度为r的回路总数,19,用邻接矩阵求通路数(例),20,可达矩阵,设D=是有向图,V=v1,v2,vn, 可达矩
7、阵: P(D)=pijnn, 1, 从vi可达vj pij = 0, 从vi不可达vj,21,可达矩阵(性质),主对角线元素都是1: viV, 从vi可达vi 强连通图: 所有元素都是1 伪对角阵: 对角块是强连通分支的可达矩阵 ij, pij=1 bij (n-1) 0,22,图的运算,定义14.27 设图G1=, G2=,若 V1V2= , 则称G1与G2 是不交的. 若 E1E2= ,则称 E1与E2 是不重的. 由定义知,不交的图必然是边不交的,但反之 不真。,23,图的运算,定义14.28 设图G1=, G2=为不含孤立点的 两个图(它们同为无向图或同为有向图). (1)称以 V1V
8、2为顶点集,以 E1E2 为边集的图为G1与 G2 的并图,记作 G1G2 ,即G1G2 =.,24,图的运算,(2)称以E1- E2为边集,以 E1- E2中边关联的顶点组成的集合为顶点集的图为 G1与 G2的差图,记作 G1- G2. (3)称以E1E2为边集,以 E1E2中边关联的顶点组成的集合为顶点集的图为 G1与 G2的交图,记作 G1G2. (4)称以E1E2为边集,以 E1E2中边关联的顶点组成的集合为顶点集的图为 G1与 G2的交图,记作 G1G2.,25,图的运算,在定义14.28中应注意以下几点: 1.若G1= G2,则G1G2= G1G2= G1(G2),而G1-G2=
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 欧拉图 汉密尔顿
链接地址:https://www.31doc.com/p-3018229.html