离散数学PPT教学图论.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,欢 迎 进 入,第,11,章,图,论,本章重难点,:,重点了解图的各种概念，理解并掌握握手定理的应用以及各种矩阵的表示。,难点是图的最短路径和关键路径的求法。,第,11,章 图 论,第一节,图的基本概念,第二节 图的矩阵表示,第三节 生成树、最短路径和关键路径,第四节 特殊图（欧拉图和哈密顿图等）,第五节 树、二叉树和哈夫曼树,一、图的基本概念,图的定义：,图,（,graph,）,G,由三个部分所组成：,（,1,）非空集合,V(G),称为图,G,的,结点集,，其成员称为节点或顶点（,nodes,or,vertices,）,（,2,）集合,E(G),，称为图,G,的,边集,，其成员称为边,(,edges,),。,（,3,）函数,G,：,E(G),(V(G),，,V(G),，,称为边,与顶点的,关联映射。,度的相关定义,：,在任何图中，结点,v,的,度,（,degree,）,d(v),是,v,所关联边的数目。,而在有向图中，结点,v,的,出度,（,out-degree,）,d+(v),是,v,作为有向边起点的数目，,v,的,入度,（,in-degree,）,d-(v),是,v,作为有向边终点的数目，这时结点,v,的度是它的出度与入度的和；结点,v,的环使其度增加,2,。,一、图的基本概念,连通图、强连通图、弱连通图,若无向图中的任意两个顶点都相互可达，则称无向图,G,是,连通,的（,connecte,d,）；,若有向图,G,的任何两个顶点都是相互可达的，则称有向图,G,是,强连通,的；,如果,G,的任何两个顶点都是相互可达的，称有向图,G,是,单向连通,的；,如果,G,的任何两个顶点中，至少从一个顶点到另一个顶点是可达的，称有向图,G,是,弱连通,的。,一、图的基本概念,邻接和关联,无向图和有向图,零图和平凡图,简单图,完全图（无向完全图和有向完全图）,有环图,一、图的基本概念,有限图和无限图,设图,G,为,（,l,）当,V,和,E,为有限集时，称,G,为,有限图,，否则称,G,为,无限图,。,（,2,）当,G,为单射时，称,G,为,单图,；当,G,为非单射时，称,G,为,重图,，又称满足,(e1)=(e2),的不同边,e1,，,e2,，为,重边,或,平行边。,正则图,各顶点的度均相同的图称为,正则图,（,regular graph,）。,各顶点度均为,k,的正则图称为,k-,正则图,。,同构图,一、图的基本概念,子图、真子图、生成子图,设图,G1,，,G2,，,称,G1,为,G2,的,子图,（,subgraph,）；,如果,V1,V2,，,E1,E2,，,1,2,，称,G1,为,G2,的,真子图,；,如果,G1,是,G2,的子图，且,G1,G2,，称,G1,为,G2,的,生成子图,（,spanning subgraph,）；如果,G1,是,G2,的子图，且,V1=V2,。,握手定理的证明,每个图中，节点度数的总和等于边的,2,倍。,证明：,因为每条边必关联两个节点，而一 条边给予关联的每个节点的度数为,1,，因此在一个图中，节点度数的总和等于边数的,2,倍。,握手定理的运用,定理,1,：,在任何图中，度数为奇数的节点个数必定是偶数个。,证明,：,（自己思考！）,定理,2,：,在任何有向图中，所有节点入度之和等于所有节点的出度之和。,证明：,因为每一条有向边必对应一个入度及一个出度，所以有向图中各节点入度之和等于边数，各节点的出度之和也等于边数。,例：设图,G,为下列情况：,(1)16,条边，每个顶点都是,2,度；,(2)21,条边，,3,个,4,度顶点，其余均为度顶点；,(3)24,条边，各节点的度数均相同；,试求每个图有几个节点？,握手定理的应用,解答：利用握手定理，设图有,x,个节点，则,x=16*2,x=16,21*2=12+3*x x=10,故图中有个节点,(3),x*m=24*2,二、图的矩阵表示,关联矩阵,2.,邻接矩阵,3.,可达矩阵,4.,布尔矩阵,5.,代价矩阵,二、图的矩阵表示,关联矩阵,无向图的关联矩阵,-,以节点数为行,边数为列,.,若有环,则关联数为,2,无关联则为,0.,每行之和为该顶点的度,列之和一定为,2.,有向图的关联矩阵,-,以节点数为行,边数为列,.,节点与边无关系,为,0,有关系,则起点为,1,终点为,-1;,列之和一定为,0,每行绝对值之和等于该节点的度数,;,其中,1,的个数为该节点的出度,-1,的个数为对应节点的入度,;,所有元素的和为,0,1,的个数等于,-1,的个数,都等于边数,m.,二、图的矩阵表示,2.,邻接矩阵,无向图的邻接矩阵,-,行和列均为节点的数目,;,是个对称距阵,行之和等于列之和,均等于该顶点的度,;,主对角线都为,0,除非有环才为,1;,边的数目,m,为,1,的数目总和的一半,.,有向图的邻接矩阵,-,行和列均为节点的数目,;,不是对称距阵,行之和等于该顶点的出度,列之和等于该顶点的入度,;,主对角线都为,0,除非有环才为,1;,边的数目,m,为非,0,的数目的总和,.,二、图的矩阵表示,可达矩阵,-,行和列均为节点的数目;节点和节点之间若至少存在一条路则为1,不存在路则为0.,4.布尔矩阵,-,由可达距阵转变,把非0的数值均改为1即可,.,代价矩阵,-,若邻接距阵元素为1的以权值表示,距阵元素为0的则以,表示.,三、生成树、最短路径和关键路径,生成树定义,1,、深度优先遍历,2,、广度优先遍历,最小生成树,构造最小生成树的三种方法：,1,、,Kruskal,算法,2,、管梅谷算法,3,、,Prim,算法,第四节 欧拉图和哈密顿图,欧拉图的由来：,哥尼斯堡七桥问题,哥尼斯堡城市有一条横贯全城的普雷格尔河，河中有两个小岛，城的各部分用七座桥连接，每逢假日，城中居民进行环城逛游，这样就产生了一个问题，能不能设计一次遍游，使得从某地出发对每座跨河桥只走一次，而在遍历了七桥之后却又能回到原地。,第四节 欧拉图和哈密顿图,通过图中所有边一次且仅一次行遍所有顶点的通路称为,欧拉通路（欧拉路）,。通过图中所有边一次且仅一次行遍所有顶点的回路称为,欧拉回路,。,只有具有欧拉回路的图才能称为欧拉图。,具有欧拉通路而无欧拉回路的图称为半欧拉图。,第四节 欧拉图和哈密顿图,欧拉在,1736,年的论文中提出了一条简单准则，确定了哥尼斯堡七桥问题是不能解的。,定理,1,：无向图是欧拉图当且仅当,G,是连通图且没有奇度顶点。,定理,2,：,无向图是半欧拉图当且仅当,G,是连通的且恰有两个奇度顶点。,第四节 欧拉图和哈密顿图,定理,3,：,有向图,D,是欧拉图当且仅当,D,是强连通的且每个顶点的 入度等于出度。,定理,4,：有向图,D,是半欧拉图当且仅当,D,是单向连通的且恰有两个奇度顶点，其中一个顶点的入度比出度大,1,，另一个顶点出度比入度大,1,，而其余顶点的 入度等于出度。,第四节 欧拉图和哈密顿图,欧拉图的应用：,一笔画问题：,一个图能一笔画出是指从图某一点出发，不间断地画完整个图，最后回到起点。,第四节 欧拉图和哈密顿图,哈密顿图的由来,周游世界问题：,一个数学游戏，能不能在一个十二面体中找到一条回路，使它含有这个图的所有结点？把每个结点看成一个城市，连接两个结点的边看成是交通线，也即能否找到旅游线路，沿着交通线经过每个城市恰好一次再回到原来的出发地？,第四节 欧拉图和哈密顿图,经过图中所有顶点一次且仅一次的通路称为,哈密顿通路（哈密顿路）,。通过图中所有顶点一次且仅一次的回路称为,哈密顿回路,。,只有具有哈密顿回路的图才能称为哈密顿图。,具有哈密顿通路而无哈密顿回路的图称为半哈密顿图。,第四节 欧拉图和哈密顿图,定理,1,（必要条件）：设无向图,G=,是哈密顿图，则对于任意,V1 V,且,V1,空集,，均有,P,（,G-V1,）,V1,定理2,（,充分条件）：设,G,是,n,阶无向简单图，若对于,G,中任意不相邻的顶点,u,，,v,，均有,d,（,u,）,+d,（,v,）,n-1,，则,G,中存在哈密顿通路。,推论：,设,G,为,n,（,n,3,）阶无向简单图，若对于,G,中任意两个不相邻的顶点,u,，,v,均有,d,（,u,）,+d,（,v,）,n,，则,G,中存在哈密顿回路。,第四节 欧拉图和哈密顿图,哈密顿图的应用,在某次国际会议的预备会中，共有,8,人参加，他们来自不同的国家，已知他们中任何两个无共同语言的人，与其余有共同语言的人数之和大于或等于,8,，试证明能将这,8,个人排在圆桌旁，使其任何人都能与两边的人交谈。,一、无向树,1.,定义：,无回路的连通无向图称为无向树，简称树。,树中度数为,1,的顶点称为树叶，度数大于,1,的顶点称为内部结点或分枝点。,若图,G,的每个连通分图都是树,G,称为森林,。,第五节 树、二叉树和哈夫曼树,2,、树的五个等价定义,Th1.,无向图,T,是树，当且仅当下列条件之一成立：,1.,无回路且,m=n-1,的图,2.,连通且,m=n-1,的图,3.,无回路，但增加任一新边，得到且仅得到 一个基本回路,4.,连通但删去任一边，图便不连通。,(n=2),5.,每一对顶点间有唯一的一条通路。,(n=2),证明：证明思路,(1),树,=1,(2)1=2,(3)2=3,(4)3=45)4=5,(6)5=6,(1),树,=1,即,无回路的连通无向图,=,无回路且,m=n-1,证明：对顶点数作归纳证明。,n=1,时，,m=0,，,m=n-1,成立,设,n=k,命题成立，当,n=k+1,时，因树连通而无回路，所以至少有一个度数为,1,的顶点,v,，在,T,中删去,v,，及其关联边，得,k,个顶点的树,T,由归纳假设，它有,k-1,条边。,原图,T,边数为,k-1+1,顶点数为,k+1,m=n-1,成立。,树是无回路且,m=n-1,的图。,(2),无回路且,m=n-1,的图,=,连通且,m=n-1,的图,反证法,.,证明：设,T,不连通，有,k,个连通分图,T,1,.T,kk2),，顶点数及边数分别为,n,1,.n,k,m,1,.m,k,因每个连通分图是无回路连通图，故符合树的定义，所以,n,i,=m,i-1,成立,n=m-k k1,这与,m=n-1,前提矛盾,T,连通且具有,m=n-1,的图,(,3)2=3,即连通且,m=n-1,的图,=,无回路，但增加任一新边，得到且仅得到一个基本回路。,证明：,(a)T,无回路，因,T,是连通,并且,m=n-1,的图，,故当,n=1,时，,m=n-1=0,无回路,设顶点数为,n-1,时无回路。,当顶点数为,n,时，,m=n-1,，故至少有一个顶点,v,，,使,d(v)=1,，删去,v,及其关连边得图,T,则由归纳假设,T,无回路，再加回,v,及关联边得,图,T,，则,T,也无回路。,(b),在连通图,T,中,任意取两点,v,i,，,v,j,因为,T,连通所以,v,i,，,v,j,存在一路经，,若增加新边,(v,i,v,j,),，则得一回路，,且该回路是唯一的。,(,否则，删去新边，路经中必有回路。,),(4),3=4.,即无回路，但增加任一新边，得到且仅得到一个基本回路,=,连通，但删去任一边，图便不连通。,(n=2),证明：若图不连通，则存在,v,i,v,j,，,使,v,i,v,j,之间没有路，增加边,不产生回路，与前提矛盾。,因,T,无回路，故删去任一边，图便不连通。,(5)4=5.,即,连通，但删去任一边，图便不连通。,(n=2),=,每一对顶点间有唯一的一条通路。,证明：因图连通，故任二顶点间有一条通路，若二顶点间路径不唯一，则,T,中有回路，删去回路上任一条边，图仍连通，与假设矛盾，所以，,每一对顶点间必有唯一的一条通路,(6)5=,树定义（无回路的连通无向图）,因每一对顶点有唯一的一条通路，故图连通，若图有回路，则任二顶点有两条不同通路，与题设矛盾。,证：若,T,中只有一片树叶，,则,d,（,v,i,）,2,（,n-1,）,+1=2n-1,若,T,中没有树叶，则,d,（,v,i,）,2n,均与,d,（,v,i,）,=2m=2,（,n-1,）矛盾。,3,、,Th2,：结点数大于等于,2的任意树，至少有两片树叶。,二、生成树,1,、生成树定义：,若无向图的一个生成子图,T,是树，则称,T,为,G,的生成树，,T,中的边称为树枝，,E,（,G,）,-E,（,T,）称为树,T,的补，其中的每一边称为树,T,的弦。,注：,(1),由定义知，只有连通图才有生成树。,(2),连通图的生成树不唯一，至少有一棵，因通过不断地删去图,G,中的回路中的边，总能得到一棵生成树。,e1 e2,e6 e7 e3,e5,e4,e8,基本回路：生成树,e1,e7,e5,e6,，,e1,，,e7,，,e5,，,e2,，,e4,e7,e2,e3,e4,，,e1,，,e6,，,e5,，,e2,，,e4,e5e4,e8,，,e7,，,e6,，,e5,，,e2,，,e4,(3),设连通图,G,有,n,个顶点，,m,条边，则,G,的任一生成树有,n-1,条边，,m-(n-1),条弦，,m-n+1,称为连通图的秩。,2.,图,G,中任一条回路和任何一棵生成 树的补至少有一条公共边。,证明：若,G,中一条回路和一生成 树的补无公共边，则表示该回路在该生成树中。这与生成树定义矛盾。,3.,图,G,中任何一个边割集和任何一棵生成树至少有一条公共边。,证明：若,G,中一个边割集和一生成 树无公共边，则表示该边割集所分离的结点不在生成树中，这导致与生成树的定义矛盾。,三、最小生成树,1,、最小生成树定义：,设图G=,是赋权连通简单图，其中每一边的权,W(i,，,j),是非负实数。生成树,T,的权定义为,W(T)=,W,（,i,，,j,），（,i,，,j,）,T,，使,W(T,）具有最小值的生成树称为,G,的最小生成树。,2,、最小生成树求法,-kruskal,算法,。,设图,G,有,n,个顶点，,m,条边，,w(e,1,)w(e,m,),k1,，,A,若,A,e,k,导出子图不包,含回路，则,A,A,e,k,k,k+1,N0,A,=n-1 Yes,结束,证明：因,T,是有,n-1,条边，且无回路的图。,由树的等价定义可知，它是树。,又,T,包含了,n,个顶点，,故包含了,G,的全部顶点。,T,是,G,的生成树。,算法的正确性证明,证明边集,A,最后所得子图,T,是,G,的生成树。,、,T,是最小生成树,注：当,G,中的权相等时，仍可用本算法，只是所得之最小生成树不唯一。,证明,T,是最小生成树（证明方法：,T,逐步转化,T,证明：设,T,是最小生成树，,T,是由,krusal,算法生成的树，若,T,与,T,不同，但有公共边,e,1,.e,i,(i=0),则,e,i+1,T,e,i+1,T,则在,T,ei+1,中有一回路,r,而,T,是树，因任一回路与生成树的补必有一公共边，所以在,r,中必存在一条边,f,T,对于树,T(,边集至少为,e,1,.e,i,f),，若用,e,i+1,代换,f得一棵新树,T1(,边集至少为,e,1,.e,i,e,i+1,),则,T1,的权,W(T1)=W(T1)+W(e,i+1,)-W(f),因为,T,为最小生成树,W(T)W(T1)W(e,i+1,)W(f),又根据,T,生成法,自,e,1,.e,i,之后将取,f,而不是,e,i+1,而现在,T,取,e,i+1,W(e,i+1,)W(f)W(ei+1)=W(f),T1,也是,G,的最小生成树。而,T1,与,T,的公共边比,T,与,T,的公共边多,1,，用,T1,置换,T,，重复上面论证直至,T,与,T,有,n-1,条公共边，从而证得,T,也是,G,的最小生成树。,一、有向树,定义,:,1.,若一个有向图,T,的底图是无向树，且恰有一个结点的入度为,0,，其余所有结点入度为,1,，称,T,为有向树。入度为,0,的结点称为根，出度不为,0,的结点称为分枝点或内部结点，出度为,0,的结点称为数叶或外部结点。,注意：有向树通常采用根在顶点上，所有边方向向下的图表示,.(,箭头也可省略,),有 向 树 及 应 用,2.,基本概念,:,设,a,和,b,是树,T,的结点，若从,a,到,b,有一条边称,a,是,b,的,父亲,，,b,是,a,的,儿子,，同一个分枝点的儿子，称为“,兄弟,”。,若从,a,到,c,有一有向路径，称,a,是,c,的,祖先,，,c,是,a,的,子孙,.,由结点,a,和它所有的后代导的子图，称为,T,的,子树,.,从树根,r,到一结点,a,的路径所含的边数称为,a,的,路径长度,。,树,T,中最长的路径称为树,T,的,高度,。,例题,:,a,b,c,由有向树的结构可知，它还可以递归定义如下,:,3.,有向树有一个根，其余的结点划分为,m0,个不相交的集合,T,1,.T,m,，且每个集合是子有向树。,4.,有向树的括号表示,若,T,中只有一个结点，则此结点就是它的括号表示。,若,T,由根,v,和子树,T,1,T,2,.T,n,组成，则,T,的括号表示为,v(T,1,T,2,.T,n,）,.,5.m,元完全树，正则树的定义,定义,:,在树,T,中若每一结点的儿子个数小于或等于,m,称,T,为,m,元树,;,在树,T,中若每一结点的儿子个数等于,m,或者等于,0,，称,T,为完全,m,元树。若完全,m,元树所有树叶层次相同，称为正则,m,元树。,5.,有向森林定义,一个有向图,G,，若它的每个连通分量是有向树，称,G,为,(,有向,),森林，在森林中，若所有树是有序树，且给每棵树指定次序，称此森林为有序森林,.,b,c,b,c,a,b,c,完全,3,元树,完全,2,元树,正则,2,元树,6,、有序树，有序森林与二元树相互转换,有序树转换为二元树，转换过程为：,a),在各兄弟结点之间加一连线。,b),对任何结点，除最左的儿子之外，擦掉该结点与其余儿子的联线。,c),对新图向下旋转,45,度。,b,c,b,c,-,2.,有序森林转换为二元树转换过程,a),设置一个总根，联结各树的根，得,T,b),把,T,转换为二元树,c),删除总根,二,.,完全,m,元树性质,1.,设完全,m,元树，叶数为,t,，分枝数为,i,，则,t=(m-1)i+1,解,:i=(t-1)/(m-1)=(10-1)/(3-1)=5,答,:,至少执行,5,次加法指令,.,例：若,t=i(m-1)+1,计算机有一计算三数之和的加法器,现求十个数之和,问至少执行多少次加法指令,?,证明,:,若把完全,m,元树视为,m,个选手参加淘汰赛,则,t,表示选手总数,i,表示比赛场数,每场比赛淘汰,m-1,人,共淘汰,i(m-1),人,剩下一个冠军,所以,t=(m-1)i+1,2,、内部通数长度,I,定义：各分枝点路径长度之和。,内部通数长度,E,定义：各 叶子路径长度之和,.,性质：完全二叉树,T,有,E=I+2n,其中,:n,为分枝点数,证：对,n,用数学归纳法,:,当,n=1,则叶数为,2,，,I=0,，,E=2,，,E=I+2n,成立,;,当,n=2,则叶数为,3,，,I=1,，,E=5,，,E=I+2n,成立,;,设,n=k-1,时，结论成立,;,则,n=k,时，若删去长度为,e+l,其关系为兄弟的叶子，得,T,，,T,与原树比较，减少一个长度为,e,的分枝点、二个长度为,e+1,的叶子，增加一长度为,e,的叶子，,E=I+2,（,k-1,）而,I=I-e.,所以,E=E-2,（,e+1)+e,即,E-2(e+1)+e=,I-e,+2(k-1),所以,E=I+2k.,三、前缀码和最优树,1,、问题的引出：,传递信息中，可用,5,位,01,序列表示一个英文字母，因每个字母的使用频率不一样，人们希望用较短的序列表示常用字母，但产生问题：,e,：,00,，,t,：,01,，,q,：,0001,，则,0001,为,q,还是为,et,。,2,、前缀码定义：,若,01,序列集合中，任何序列都不是另一个序列的前缀，则这个序列集合称为前缀码。,注,1,：任意前缀码均可用完全二元树的叶子表示。,注：,1,、任意前缀码均可用完全二元树的叶子表示。,2,、由任一棵完全二元树可得前缀码。,3,、使用前缀码可分辨出长短不一的序列。,方法：从根出发，接收到,0,朝左走，接收到,1,右走，,直到树叶。,4,、如何设计，使字母编码根据使用频率平均最短。,0,0,0,1,1,1,00,01,10,11,例如：,5,个字母,a,，,b,，,c,，,d,，,e,，,f,的使用频率分别,为,3,，,4,，,5,，,6,，,12,，试求出最优树及对应的前缀,码。,3 4,5 6 12,5,，,6,，,7,，,12,7,，,11,，,12,12,，,18,30,0,0,1,1,1,3,5,4,6,12,前缀码为,a,：,000,，,b,：,001,，,c,：,010,，,d,：,011,最优树的权为,W,（,T,）,=3,（,3+4+5+6,）,+12=40,所以，一篇,30,个字母的电文，若用前缀码，平均只需发送,40,位，若每个字母用,3,位表示，须发送,90,位。,本 章 小 结,课后练习和作业,课后练习：,P304：1，2，3,P307：17，18，19,P308：26，29,课后作业：,P305：7,P306：12,P307：20，22,谢谢！,