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

该【离散数学第十四章课件 】是由【1557281760】上传分享，文档一共【58】页，该文档可以免费在线阅读，需要了解更多关于【离散数学第十四章课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第五部分图论本部分主要内容图的基本概念欧拉图、哈密顿图树平面图支配集、覆盖集、独立集、匹配与着色1第十四章图的基本概念主要内容图通路与回路图的连通性图的矩阵表示图的运算2预备知识多重集合——元素可以重复出现的集合某元素重复出现的次数称为该元素的重复度例如,在多重集合{a,a,b,b,b,c,d}中,a,b,c,d的重复度分别为2,3,1,——A?B={(x,y)|x?A?y?B}设A,B为任意的两个集合,称{{a,b}|a∈A∧b∈B}为A与B的无序积,记作A&,将无序积中的无序对{a,b},记为(a,b),并且允许a=,b是否相等均有(a,b)=(b,a),因而A&B=B&=<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>为一无向图4有向图定义一个有向图是一个有序的二元组<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>}①可用G泛指图(无向的或有向的),D表示有向图②V(G),E(G),V(D),E(D),|V(G)|,|E(G)|③(1阶零图)——?①关联、关联次数②环③、 在图的定义中,用G表示无向图,D表示有向图,但有时用G泛指图(无向的或有向的),可是D只能表示有向图。另外,为方便起见,有时用V(G),E(G)分别表示G的顶点集和边集,若|V(G)|=n,则称G为n阶图,对有向图可做类似规定。 若|V(G)|与|E(G)|均为有限数,则称G为有限图。 在图G中,若边集E(G)=?,则称G为零图,此时,又若G为n阶图,则称G为n阶零图,记作Nn,特别地,称N1为平凡图。 在图的定义中规定顶点集V为非空集,但在图的运算中可能产生顶点集为空集的运算结果,为此规定顶点集为空集的图为空图,并将空图记为?。、基图 称顶点或边用字母标定的图为标定图,否则称为非标定图。将有向图各有向边均改成无向边后的无向图称为原来图的基图。易知标定图与非标定图是可以相互转化的。、环、孤立点 设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中的环。无论在无向图中还是在有向图中,无边关联的顶点均称孤立点。 设无向图G=<V,E>,vi,vj∈V,ek,el∈∈E,使得et=(vi,vj),则称vi与vj是相邻的。若ek与el至少有一个公共端点,则称ek与el是相邻的。 设有向图D=<V,E>,vi,vj∈V,ek,el∈∈E,使得et=<vi,vj>,则称vi为et的始点,vj为et的终点,并称vi邻接到vj,vj邻接于vi。若ek的终点为el的始点,则称ek与el相邻。①v?V(G)(G为无向图)②v?V(D)(D为有向图)相关概念10