离散数学第十四章的课件.

1第五部分图论本部分主要内容图的基本概念欧拉图、哈密顿图树平面图支配集、覆盖集、独立集、匹配与着色2第十四章图的基本概念主要内容图通路与回路图的连通性图的矩阵表示图的运算3预备知识多重集合——元素可以重复出现的集合–某元素重复出现的次数称为该元素的重复度–例如，在多重集合{a,a,b,b,b,c,d}中，a,b,c,d的重复度分别为2,3,1,1.无序积——AB={(x,y)|xAyB}–设A，B为任意的两个集合，称{{a,b}|a∈A∧b∈B}为A与B的无序积，记作A&B.–通常，将无序积中的无序对{a,b},记为(a,b),并且允许a=b.且无论a,b是否相等均有(a,b)=(b,a),因而A&B=B&A.414.1图定义14.1一个无向图是一个有序的二元组=V,E,记作G,其中(1)V称为顶点集，其元素称为顶点或结点(2)E称为边集,它是无序积VV的多重子集，其元素称为无向边，简称边实例设V={v1,v2,…,v5},E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}则G=V,E为一无向图5有向图定义14.2一个有向图是一个有序的二元组V,E,记作D,其中（1）V同无向图。（2）E是笛卡儿积VV的多重子集，称为边集，其元素称为有向边，简称为边。图2表示的是一个有向图，试写出它的V和E注意：图的数学定义与图形表示，在同构（待叙）的意义下是一一对应的V={a,b,c,d},E={a,a,a,b,a,b,a,d,c,b,d,c,c,d}6相关概念1.图①可用G泛指图（无向的或有向的），D表示有向图②V(G),E(G),V(D),E(D)，|V(G)|，|E(G)|③n阶图2.n阶零图Nn与平凡图N1（1阶零图）3.空图——4.标定图与非标定图5.基图6.用ek表示无向边或有向边7.顶点与边的关联关系①关联、关联次数②环③孤立点8.顶点之间的相邻与边之间的相邻、邻接9.邻域与关联集71．n阶图在图的定义中，用G表示无向图，D表示有向图，但有时用G泛指图(无向的或有向的)，可是D只能表示有向图。另外，为方便起见，有时用V(G)，E(G)分别表示G的顶点集和边集，若|V(G)|=n,则称G为n阶图，对有向图可做类似规定。2．有限图若|V(G)|与|E(G)|均为有限数，则称G为有限图。3．n阶零图与平凡图在图G中，若边集E(G)=,则称G为零图，此时，又若G为n阶图，则称G为n阶零图，记作Nn，特别地，称N1为平凡图。4．空图在图的定义中规定顶点集V为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定顶点集为空集的图为空图，并将空图记为。相关概念8相关概念5．标定图与非标定图、基图称顶点或边用字母标定的图为标定图，否则称为非标定图。将有向图各有向边均改成无向边后的无向图称为原来图的基图。易知标定图与非标定图是可以相互转化的。6．关联与关联次数、环、孤立点设G=V，E为无向图，ek=(vi，vj)∈E，则称vi，vj为ek的端点，ek与vi或ek与vj是彼此相关联的。若vi≠vj，则称ek与vi或ek与vj的关联次数为1，若vi=vj，则称ek与vi的关联次数为2，并称ek为环。任意的vl∈V，若顶点vl不与边ek关联，则称ek与vl的关联次数为0。设D=V，E为有向图，ek=vi，vj∈E，称vi，vj为ek的端点，若vi=vj，则称ek为D中的环。无论在无向图中还是在有向图中，无边关联的顶点均称孤立点。7．相邻与邻接设无向图G=V，E，vi，vj∈V，ek，el∈E.若et∈E，使得et=（vi，vj），则称vi与vj是相邻的。若ek与el至少有一个公共端点，则称ek与el是相邻的。设有向图D=V，E，vi，vj∈V，ek，el∈E.若et∈E，使得et=vi，vj，则称vi为et的始点，vj为et的终点，并称vi邻接到vj，vj邻接于vi。若ek的终点为el的始点，则称ek与el相邻。9}{)()(})(),()(|{)(vvNvNvvuGEvuGVuuvNv的闭邻域的邻域})(|{)(关联与veGEeevI8.邻域与关联集①vV(G)(G为无向图)v的关联集相关概念}{)()(})(),()(|{)(vvNvNvvuGEvuGVuuvNv的闭邻域的邻域})(|{)(关联与veGEeevIv的关联集111111()()()GGGvNvvNvvIv的邻域的闭邻域的关联集10}{)()()()()(})(,)(|{)(})(,)(|{)(vvNvNvvvvNvvuDEvuDVuuvvvuDEuvDVuuvvDDDDDDD的闭邻域的邻域的先驱元集的后继元集8.邻域与关联集②vV(D)(D为有向图)相关概念()()()()DDDDdddddNddNd的后继元集的先驱元集的邻域的闭邻域11多重图与简单图定义14.3(1)无向图中的平行边及重数在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数(2)有向图中的平行边及重数（注意方向性）在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点和终点相同(也就是它们的方向相同)，则称这些边为平行边(3)多重图：含平行边的图(4)简单图：既不含平行边也不含环的图在定义14.3中定义的简单图是极其重要的概念12顶点的度数定义14.4(1)设G=V,E为无向图,vV,称v作为边的端点次数之和为v的度数，简记为d(v)——v的度数,简称度(2)设D=V,E为有向图,vV,d-(v)——称v作为边的始点次数之和为v的出度d+(v)——称v作为边的终点次数之和为v的入度d(v)——d+(v)+d(v)为v的度或度数(3)无向图G的最大度(G),最小度(G)(4)有向图D的最大度(D)、最大出度(D)、最大入度+(D)与最小度(D)、最小出度(D)、最小入度+(D)13(4)有向图D的最大度(D)、最大出度(D)、最大入度+(D)与最小度(D)、最小出度(D)、最小入度+(D)(5)奇度顶点与偶度顶点称度数为1的顶点为悬挂顶点，与它关联的边称为悬挂边。度为偶数(奇数)的顶点称为偶度(奇度)顶点。14无向图中，d(v1)（环提供2度），最大度、最小度，v4为悬挂顶点，e7为悬挂边。有向图中，d+(a)、d-(a)（环提供一个出度、一个入度）、d(a)、、、最大出度-、最小出度、最大入度+、最小入度+15mvdnii2)(1mvdvdmvdniiniinii111)()(,2)(且定理14.1设G=V,E为任意无向图，V={v1,v2,…,vn},|E|=m,则证G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，m条边共提供2m度.本定理的证明类似于定理14.1握手定理定理14.2设D=V,E为任意有向图，V={v1,v2,…,vn},|E|=m,则16握手定理推论推论任何图(无向或有向)中，奇度顶点的个数是偶数.证设G=V,E为任意图，令V1={v|vVd(v)为奇数}V2={v|vVd(v)为偶数}则V1V2=V,V1V2=，由握手定理可知由于2m,均为偶数，所以为偶数，但因为V1中顶点度数为奇数，所以|V1|必为偶数.21)()()(2VvVvVvvdvdvdm2)(Vvvd1)(Vvvd17例无向图G有16条边，3个4度顶点，4个3度顶点，其余顶点度数均小于3，问G的阶数n为几？解本题的关键是应用握手定理.设除3度与4度顶点外，还有x个顶点v1,v2,…,vx，则d(vi)2，i=1,2,…,x，于是得不等式3224+2x得x4,阶数n4+4+3=11.握手定理应用P292第8题18图的度数列1.V={v1,v2,…,vn}为无向图G的顶点集，称d(v1),d(v2),…,d(vn)为G的度数列注：对于顶点标定的无向图，它的度数列是唯一的。2.V={v1,v2,…,vn}为有向图D的顶点集，D的度数列：d(v1),d(v2),…,d(vn)D的出度列：d-(v1),d-(v2),…,d-(vn)D的入度列：d+(v1),d+(v2),…,d+(vn)例：在图14.1(a)中，按顶点的标定顺序，度数列为4,4,2,1,3.在图14.1(b)中，按字母顺序，度数列，出度列，入度列分别为5,3,3,3；4,0,2,1；1,3,1,2.3.对于给定的非负整数列d=(d1,d2,…,dn)，若存在以V={v1,v2,…,vn}为顶点集的n阶无向图G，使得d(vi)=di，则称d是可图化的。特别地，若所得图是简单图，则称d是可简单图化的。19图的度数列d=(d1,d2,…,dn)是否为可图化的，可由下面定理判别。定理14.3设非负整数列d=(d1,d2,…,dn)，则d是可图化的当且仅当为偶数.易知：(2,4,6,8,10)，(1,3,3,3,4)是可图化的，而(3,3,3,4)不是可图化的。定理14.4设G为任意n阶无向简单图，则△(G)≤n-1.证因为G既无平行边也无环，所以G中任何顶点v至多与其余的n-1个顶点均相邻，于是d(v)≤n-1，由于v的任意性，所以△(G)≤n-1.niid120例14.2判断下列各非负整数列哪些是可图化的？(1)(5,5,4,4,2,1)(2)(5,4,3,2,2)(3)(3,3,3,1)(4)(d1,d2,…dn)，d1d2…dn≥1且为偶数(5)(4,4,3,3,2,2)niid121图的同构定义14.5设G1=V1,E1,G2=V2,E2为两个无向图(两个有向图)，若存在双射函数f:V1V2,对于vi,vjV1,(vi,vj)E1当且仅当(f(vi),f(vj))E2（vi,vjE1当且仅当f(vi),f(vj)E2)并且,(vi,vj)（vi,vj）与(f(vi),f(vj))（f(vi),f(vj)）的重数相同，则称G1与G2是同构的，记作G1G2.图之间的同构关系具有自反性、对称性和传递性.能找到多条同构的必要条件，但它们全不是充分条件：①边数相同，顶点数相同;②度数列相同;③对应顶点的关联集及邻域的元素个数相同，等等若破坏必要条件，则两图不同构判断两个图同构是个难题22图同构的实例(1)(2)(3)(4)图中，(1)与(2)不同构（度数列不同），(3)与(4)也不同构.23n阶完全图与竞赛图定义14.6(1)n(n1)阶无向完全图——每个顶点与其余顶点均相邻的无向简单图，记作Kn.简单性质：边数(2)n(n1)阶有向完全图——每对顶点之间均有两条方向相反的有向边的有向简单图.简单性质：(3)n(n1)阶竞赛图——基图为Kn的有向简单图.简单性质：边数1,2)1(nnnm1121n),n(),n(nm1,2)1(nnnm24n阶k-正则图(1)为K5，(2)为3阶有向完全图，(3)为4阶竞赛图.(1)(2)(3)定义14.7n阶k-正则图——均有d(v)=k(==k)的无向简单图简单性质：边数（由握手定理得）Nn是0-正则图Kn是n1-正则图，彼得松图是3-正则图（见书上图14.3(a)所示，记住它）2nkm25子图定义14.8G=V,E,G=V,E(1)GG——G为G的子图，G为G的母图(2)若GG且V=V，则称G为G的生成子图(3)若VV或EE，称G为G的真子图(4)V（VV且V）的导出子图，记作G[V](5)E（EE且E