离散数学61图的基本概念.ppt
第6章 图1第6章 图 6.1 图的基本概念 6.2 图的连通性 6.3 图的矩阵表示 6.4 几种特殊的图26.1 图的基本概念 6.1.1 无向图与有向图 6.1.2 顶点的度数与握手定理 6.1.3 简单图、完全图、正则图、圈图、轮图、方体图 6.1.4 子图、补图 6.1.5 图的同构3无序对与多重集合无序对:2个元素构成的集合,记作(a,b)无序积:A B=(x,y)|xA 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,34无向图定义6.1 无向图G=,其中V 称为顶点集,其元素称为顶点或结点;E是V V的多重子集,称为边集,其元素称为无向边，简称边.有时用V(G)和E(G)分别表示V和E例如,G=如图所示,其中V=v1,v2,v5 E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)e1e2e3e4e5e6e7v5v1v2v3v45有向图定义6.2 有向图D=,其中V 称为顶点集,其元素称为顶点或结点;E是V V的多重子集,称为边集,其元素称为有向边，简称边.有时用V(D)和E(D)分别表示V和E 有限图:V,E都是有穷集合的图n 阶图:n个顶点的图零图:E=的图平凡图:1 阶零图e1e2e3e4e5e6e7dabc6顶点和边的关联与相邻设无向图G=,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,vjV,ek,elE,若(vi,vj)E,则称vi,vj相邻;若ek,el有一个公共端点,则称ek,el相邻.对有向图有类似定义.设ek=vi,vj是有向图的一条边,又称vi是ek的始点,vj是ek的终点,vi邻接到vj,vj邻接于vi7顶点的度数设G=为无向图,v V,v的度数(度)d(v):v作为边的端点次数之和 悬挂顶点:度数为1的顶点悬挂边:与悬挂顶点关联的边G的最大度(G)=maxd(v)|v VG的最小度(G)=mind(v)|v V例如 d(v5)=3,d(v2)=4,d(v1)=4,(G)=4,(G)=1,v4是悬挂顶点,e7是悬挂边,e1是环e1e2e3e4e5e6e7v5v1v2v3v48顶点的度数(续)设D=为有向图,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,=3e1e2e3e4e5e6e7dabc9握手定理定理6.1 任何图(无向图和有向图)的所有顶点度数之和都等于边数的2倍.证 图中每条边(包括环)均有两个端点,所以在计算各顶点度数之和时,每条边均提供2度,m条边共提供2m度.推论 任何图(无向图和有向图)都有偶数个奇度顶点定理6.2 有向图所有顶点的入度之和等于出度之和等于边数证 每条边恰好提供1个入度和1个出度10图的度数列设无向图G的顶点集V=v1,v2,vnG的度数列:d(v1),d(v2),d(vn)如右图度数列:4,4,2,1,3设有向图D的顶点集V=v1,v2,vnD的度数列: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,2e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc1 1实例(2)能例1 下述2组数能成为无向图的度数列吗?(1)3,3,3,4;(2)1,2,2,3解(1)不可能.有奇数个奇数.12实例例2 已知图G有10条边,4个3度顶点,其余顶点的度数均小于等于2,问G至少有多少个顶点?解 设G有n个顶点.由握手定理,43+2(n-4)210解得 n 8例3 已知5阶有向图的度数列和出度列分别为3,3,2,3,3和1,2,1,2,1,求它的入度列解 2,1,1,1,213实例例4 证明不存在具有奇数个面且每个面都具有奇数条棱的多面体.证 用反证法.假设存在这样的多面体,作无向图G=,其中 V=v|v为多面体的面,E=(u,v)|u,vV u与v有公共的棱 u v.根据假设,|V|为奇数且v V,d(v)为奇数.这与握手定理的推论矛盾.14实例例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度顶点方法二 假设b9-5=4.由握手定理的推论,a 615简单图定义6.4 在无向图中,关联同一对顶点的2条或2条以上的边,称为平行边,平行边的条数称为重数在有向图中,具有相同始点和终点的2条或2条以上的边称为有向平行边,简称平行边,平行边的条数称为重数含平行边的图称为多重图既无平行边也无环的图称为简单图16实例e5和e6 是平行边重数为2不是简单图e2和e3 是平行边,重数为2e6和e7 不是平行边不是简单图e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc17完全图与正则图无向完全图:每对顶点之间都有一条边的无向简单图.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/218实例K3K5 3阶有向完全图2正则图4正则图 3正则图彼得松图19圈图与轮图无向圈图Cn=,其中V=v1,v2,vn,E=(v1,v2),(v2,v3),(vn-1,vn),(vn,v1),n 3有向圈图Cn=,其中V=v1,v2,vn,E=,n 3轮图Wn:无向圈图Cn-1内放一个顶点,且与圈图的每个顶点之间恰有一条边,n 420方体图n方体图Qn=是2n阶无向简单图,其中 V=v|v=a1a2an,ai=0,1,i=1,2,n E=(u,v)|u,vV u与v恰好有一位数字不同.0 100 0110 11000 001010 01111010011110121子图定义6.10 设G=,G=是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 的导出子图,记作GV 设E E且E,以E 为边集,以E 中边关联的所有顶点为顶点集的G的子图称作E 的导出子图,记作GE 22实例(1),(2),(3)是(1)的子图,(2),(3)是真子图,(1)是母图.(1),(3)是(1)的生成子图.(2)是d,e,f 的导出子图,也是e5,e6,e7导出子图.(3)是e1,e3,e5,e7的导出子图a ab bc c d d de e e f f f e1 e1 e2 e3 e3 e4 e5 e5 e5 e6 e6 e7 e7 e7(1)(2)(3)23补图定义6.11 设G=为n阶无向简单图,记=V V-E,称 为G的补图24图的同构定义6.12 设G1=,G2=为两个无向图(有向图),若存在双射函数 f:V1V2,使得对于任意的vi,vjV1,(vi,vj)E1(E1)当且仅当(f(vi),f(vj)E2(E2)并且(vi,vj)()与(f(vi),f(vj)()的重数相同，则称G1与G2是同构的，记作G1G2.25实例26实例例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,3 1,1,2,2 0,2,2,227实例例7 画出3个以1,1,1,2,2,3为度数列的非同构的无向简单图28
