离散数学教学课件-14图的基本概念.pptVIP

14.4 图的矩阵表示 定义1. 设无向图G=(V, E), V={v1,v2,?,vn}, E={e1,e2,?,em} G的关联矩阵M(G)=[mij]n?m, 其中mij是vi和ej相关联的次数(0,1,2); G的邻接矩阵A(G)=[aij]n?n, 其中aij是连接vi和vj的边数. 关联矩阵M(G)的性质: (1) 每列元素之和为2; (2) 第i行元素之和为d(vi); 注:以上性质可证明握手定理. 问:邻接矩阵A(G)具有哪些性质? 定义2.设无环有向图D=(V,E), V={v1,v2,?,vn}, E={e1,e2,?,em}, 令 则称M(D)=[mij]n?m为D的关联矩阵. 定义3. 设有向图D=(V,E), V={v1,v2,?,vn}, 令aij为以vi为始点, 以vj为终点的有向边数, 则称A(D)=[aij]n?n为D的邻接矩阵. 关联矩阵M(D)的性质: (1) 每一列恰好一个1和-1; (2) 第i行中1的个数为d+(vi), -1的个数为d-(vi); 注: 以上性质可以证明握手定理. 问: 邻接矩阵A(D)的行和与列和分别等于什么? 定理1. 设A为有向图D的邻接矩阵, D的顶点集V={v1,v2,?,vn},则A?(??1)中元素aij(?)为D中vi到vj长度为?的通路数,其中aii(?)为vi到自身长度为?的回路数. 推论:设B?=A+A2+?+A?(??1),则B?中元素bij为D中vi到vj长度不超过?的通路数,其中bii为vi到自身长度不超过?的回路数. 定义4. 设D=(V, E)为有向图, V={v1,v2,?,vn}, 令 称P(D)=[pij]n?n为D的可达矩阵. 14.5 图的运算 定义1. 若G1和G2无公共顶点,则称G1与G2是不交的. 若G1和G2无公共边, 则称G1与G2是边不交的. 注: 不交的图?边不交的图. 定义2. 设G1=(V1, E1), G2=(V2, E2)为不含孤立点的两个无向(有向)图. (1)并图G1?G2=(V1?V2, E1?E2), (2)差图G1-G2=(V(G1[E1-E2]), E1-E2), (3)交图G1?G2=(V(G1[E1?E2]), E1?E2), (4)对称差G1⊕G2=(G1?G2)-(G1?G2). * * 第十四章 图的基本概念 14.1 图 14.2 通路与回路 14.3 图的连通性 14.4 图的矩阵表示 14.5 图的运算 定义1. 图G是指二元组(V(G), E(G)), 其中: (1) V(G)是非空有限集, 称为顶点集, 其中元素称为图G的顶点. (2) E(G)是顶点集V(G)中的无序或有序的元素偶对(vi,vj)组成的集合, 称为边集, 其中元素称为边. 14.1 图 通常用G=(V(G),E(G))表示图, 简记为G=(V,E). 通常用vivj表示边(vi,vj). 例: G=(V(G),E(G)), V(G)={v1,v2,v3,v4} E(G)={e1,e2,e3,e4,e5,e6} e1=v1v1,e2=v2v3,e3=v1v3, e4=v1v4,e5=v3v4,e6=v3v4 定义2. 图G的阶是指图的顶点数|V(G)|, |E(G)|表示图的边的数目. 定义3. 若一个图的顶点集和边集都是有限集,则称其为有限图. 只有一个顶点的图称为平凡图,其他的所有图都称为非平凡图. 定义4. 顶点集为空集的图称为空图(?);没有任何边的图称为零图. 平行边 环 定义5. 无环无重边的图称为简单图;含平行边的图称为多重图. 定义6.任意两点之间都有边的n阶无向简单图称为完全图,记作Kn.若n阶有向简单图D的基础图为Kn,则称D为n阶竞赛图. 定义7.若无向简单图G中每点的度都为k,则称G为k-正则图. 定义8.设G=(V,E)为无向简单图,令Ec={uv|u,v?V,uv?E},称Gc=(V,Ec)为G的补图. 2-正则图 零图 完全图 定义9. 若两个顶点之间有边连接,称这两个顶点相邻,这条边与这两个顶点关联;若两条边有公共顶点,称这两条边相邻. 定义10. 在无向图G=(V,E)中,v?V, NG(v)={u|uv?E,u?V}称为v的邻域, NG[v]=NG(v)∪{v}称为v的闭邻域, IG(v)={e|e?E,e与v关联}称为v的关联集, dG(v)=|IG(v)|称为v的度 注: 每个环给一个点贡献的度为2. 定义11. 在有向图D=(V