离散数学图的基本概念.pptVIP

*第1页，共28页，星期日，2025年，2月5日第6章图6.1图的基本概念6.2图的连通性6.3图的矩阵表示6.4几种特殊的图*第2页，共28页，星期日，2025年，2月5日6.1图的基本概念6.1.1无向图与有向图6.1.2顶点的度数与握手定理6.1.3简单图、完全图、正则图、圈图、轮图、方体图6.1.4子图、补图6.1.5图的同构*第3页，共28页，星期日，2025年，2月5日无序对与多重集合无序对:2个元素构成的集合,记作(a,b)无序积:A?B={(x,y)|x?A?y?B}例如A={a,b,c},B={1,2}A?B=B?A={(a,1),(b,1),(c,1),(a,2),(b,2),(c,2)}A?A={(a,a),(a,b),(a,c),(b,b),(b,c),(c,c)}B?B={(1,1),(1,2),(2,2)}多重集合:元素可以重复出现的集合重复度:元素在多重集合中出现的次数例如S={a,b,b,c,c,c},a,b,c的重复度依次为1,2,3*第4页，共28页，星期日，2025年，2月5日无向图定义6.1无向图G=V,E,其中V??称为顶点集,其元素称为顶点或结点;E是V?V的多重子集,称为边集,其元素称为无向边，简称边.有时用V(G)和E(G)分别表示V和E例如,G=V,E如图所示,其中V={v1,v2,…,v5}E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}e1e2e3e4e5e6e7v5v1v2v3v4*第5页，共28页，星期日，2025年，2月5日有向图定义6.2有向图D=V,E,其中V??称为顶点集,其元素称为顶点或结点;E是V?V的多重子集,称为边集,其元素称为有向边，简称边.有时用V(D)和E(D)分别表示V和E有限图:V,E都是有穷集合的图n阶图:n个顶点的图零图:E=?的图平凡图:1阶零图e1e2e3e4e5e6e7dabc*第6页，共28页，星期日，2025年，2月5日顶点和边的关联与相邻设无向图G=V,E,ek=(vi,vj)?E,称vi,vj为ek的端点,ek与vi(vj)关联.若vi=vj,则称ek为环.无边关联的顶点称作孤立点.若vi?vj,则称ek与vi(vj)的关联次数为1;若vi=vj,则称ek与vi的关联次数为2;若vi不是边e的端点,则称e与vi的关联次数为0.设vi,vj?V,ek,el?E,若(vi,vj)?E,则称vi,vj相邻;若ek,el有一个公共端点,则称ek,el相邻.对有向图有类似定义.设ek=?vi,vj?是有向图的一条边,又称vi是ek的始点,vj是ek的终点,vi邻接到vj,vj邻接于vi*第7页，共28页，星期日，2025年，2月5日顶点的度数设G=V,E为无向图,v?V,v的度数(度)d(v):v作为边的端点次数之和悬挂顶点:度数为1的顶点悬挂边:与悬挂顶点关联的边G的最大度?(G)=max{d(v)|v?V}G的最小度?(G)=min{d(v)|v?V}例如d(v5)=3,d(v2)=4,d(v1)=4,?(G)=4,?(G)=1,v4是悬挂顶点,e7是悬挂边,e1是环e1e2e3e4e5e6e7v5v1v2v3v4*第8页，共28页，星期日，2025年，2月5日顶点的度数(续)设D=V,E为有向图,v?V,v的出度d+(v):v作为边的始点次数之和v的入度d?(v):v作为边的终点次数之和v的度数(度)d(v):v作为边的端点次数之和d(v)=d+(v)+d-(v)?+(D),?+(D),??(D),??(D),?(D),?(D)悬挂顶点,悬挂边例如d+(a)=4,d-(a)=1,d(a)=5,d+(b)=0,d-(b)=3,d(b)=3,?+=4,?+=0,??=3,??=1,?=5,?=3e1e2e3e4e5e6e7dabc*第9页，共28页，星期