离散数学图基本概念

会计学1离散数学图基本概念2第6章图6.1图的基本概念6.2图的连通性6.3图的矩阵表示6.4几种特殊的图第1页/共28页36.1图的基本概念6.1.1无向图与有向图6.1.2顶点的度数与握手定理6.1.3简单图、完全图、正则图、圈图、轮图、方体图6.1.4子图、补图6.1.5图的同构第2页/共28页4无序对与多重集合无序对: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第3页/共28页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第4页/共28页6有向图定义6.2有向图D=<V,E>,其中V称为顶点集,其元素称为顶点或结点;E是VV的多重子集,称为边集,其元素称为有向边，简称边.有时用V(D)和E(D)分别表示V和E有限图:V,E都是有穷集合的图n阶图:n个顶点的图零图:E=的图平凡图:1阶零图e1e2e3e4e5e6e7dabc第5页/共28页7顶点和边的关联与相邻设无向图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第6页/共28页8顶点的度数设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第7页/共28页9顶点的度数(续)设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第8页/共28页10握手定理定理6.1任何图(无向图和有向图)的所有顶点度数之和都等于边数的2倍.证图中每条边(包括环)均有两个端点,所以在计算各顶点度数之和时,每条边均提供2度,m条边共提供2m度.推论任何图(无向图和有向图)都有偶数个奇度顶点定理6.2有向图所有顶点的入度之和等于出度之和等于边数证每条边恰好提供1个入度和1个出度第9页/共28页11图的度数列设无向图G的顶点集V={v1,v2,…,vn}G的度数列:d(v1),d(v2),…,d(vn)如右图度数列:4,4,2,1,3设有向图D的顶点集V={v1,v2,…,vn}D的度数列:d(v1),d(v2),…,d(vn)D的出度列:d+(v1),d+(v2),…,d+(vn)D的入度列:d(v1),d(v2),…,d(vn)如右图度数列:5,3,3,3出度列:4,0,2,1入度列:1,3,1,2e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc第10页/共28页12实例(2)能例1下述2组数能成为无向图的度数列吗?(1)3,3,3,4;(2)1,2,2,3解(1)不可能.有奇数个奇数.第11页/共28页13实例例2已知图G有10条边,4个3度顶点,其余顶点的度数均小于等于2,问G至少有多少个顶点?解设G有n个顶点.由握手定理,43+2(n-4)210解得n8例3已知5阶有向图的度数列和出度列分别为3,3,2,3,3和1,2,1,2,1,求它的入度列解2,1,1,1,2第12页/共28页14实例例4证明不存在具有奇数个面且每个面都具有奇数条棱的多面体.证用反证法.假设存在这样的多面体,作无向图G=<V,E>,其中V={v|v为多面体的面},E={(u,v)|u,vVu与v有公共的棱uv}.根据假设,|V|为奇数且vV,d(v)为奇数.这与握手定理的推论矛盾.第13页/共28页15实例例5设9阶无向图的每个顶点的度数为5或6,证明它至少有5个6度顶点或者至少有6个5度顶点.证讨论所有可能的情况.设有a个5度顶点和b个6度顶点(1)a=0,b=9;(2)a=2,b=7;(3)a=4,b=5;(4)a=6,b=3;(5)a=8,b=1(1)~(3)至少5个6度顶点,(4)和(5)至少6个5度顶点方法二假设b<5,则a>9-5=4.由握手定理的推论,a6第14页/共28页16简单图定义6.4在无向图中,关联同一对顶点的2条或2条以上的边,称为平行边,平行边的条数称为重数在有向图中,具有相同始点和终点的2条或2条以上的边称为有向平行边,简称平行边,平行边的条数称为重数含平行边的图称为多重图既无平行边也无环的图称为简单图第15页/共28页17实例e5和e6是平行边重数为2不是简单图e2和e3是平行边,重数为2e6和e7不是平行边不是简单图e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc第16页/共28页18完全图与正则图无向完全图:每对顶点之间都有一条边的无向简单图.n阶无向完全图记作Kn,顶点数n,边数m=n(n-1)/2,==n-1有向完全图:每对顶点之间均有两条方向相反的边的有向简单图.顶点数n,边数m=n(n-1),+=+=-=-=n-1,==2(n-1)k-正则图:每个顶点的度数均为k的无向简单图顶点数n,边数m=kn/2第17页/共28页19实例K3K53阶有向完全图2正则图4正则图3正则图彼得松图第18页/共28页20圈图与轮图无向圈图Cn=<V,E>,其中V={v1,v2,…,vn},E={(v1,v2),(v2,v3),…,(vn-1,vn),(vn,v1)},n3有向圈图Cn=<V,E>,其中V={v1,v2,…,vn},E={<v1,v2>,<v2,v3>,…,<vn-1,vn>,<vn,v1>},n3轮图Wn:无向圈图Cn-1内放一个顶点,且与圈图的每个顶点之间恰有一条边,n4第19页/共28页21方体图n方体图Qn=<V,E>是2n阶无向简单图,其中V={v|v=a1a2…an,ai=0,1,i=1,2,…,n}E={(u,v)|u,vVu与v恰好有一位数字不同}.0100011011000001010011110100111101第20页/共28页22子图定义6.10设G=<V,E>,G=<V,E>是2个图(同为无向图,或同为有向图)若VV且EE,则称G为G的子图,G为G的母图,记作GG若GG且V=V,则称G为G的生成子图若VV或EE,称G为G的真子图设VV且V,以V为顶点集,以两端点都在V中的所有边为边集的G的子图称作V的导出子图,记作G[V]设EE且E,以E为边集,以E中边关联的所有顶点为顶点集的G的子图称作E的导出子图,记作G[E]第21页/共28页23实例(1),(2),(3)是(1)的子图,(2),(3)是真子图,(1)是母图.(1),(3)是(1)的生成子图.(2)是{d,e,f}的导出子图,也是{e5,e6,e7}导出子图.(3)是{e1,e3,e5,e7}的导出子图aabbccdddeeefffe1e1e2e3e3e4e5e5e5e6e6e7e7e7(1)(2)(3)第22页/共28页24补图定义6.11设G=<V,E>为n阶无向简单图,记=VV-E,称为G的补图第23页/共28页25图的同构定义6.12设G1=<V1,E1>,G2=<V2,E2>为两个无向图(有向图),若存在双射函数f:V1V2,使得对于任意的vi,vjV1,(vi,vj)E1(<vi,vj>E1)当且仅当(f(vi),f(vj))E2(<f(vi),f(vj)>E2)并且(vi,vj)(<vi,vj>)与(f(vi),f(vj))(<f(vi),f(vj)>)的重数相同，则称G1与G2是同构的，记作G1G2.第24页/共28页26实例第25页/共28页27实例例6画出4阶3条边的所有非同构的无向简单图解总度数为6,分配给4个顶点,最大度为3,且奇度顶点数为偶数,有下述3个度数列:(1)1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.1,1,1,31,1,2,20,2,2,2第26页/共28页28实例例7画出3个以1,1,1,2,2,3为度数列的非同构的无向简单图第27页/共28页