CHAP12有向图.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,离散数学,*,第十二章,有向图,3/8/2026,1,离散数学,12.1,有向图的概念,3/8/2026,2,离散数学,有向图的定义,定义,12.1.1,：一个有向图,D,是一个有序三元,其中，,1),V(D),是非空顶点集合，简记为,V;,2)A(D),是弧的集合，简记为,A，AV=,;,3),D,是,A,到,VV=|u,v,V,的一个映射，称为关联函数，简记为,.,为方便，有时将,简记为,uv,.,易知，,uv,=vu,当且仅当,u=v.,3/8/2026,3,离散数学,一个有向图,设,V=u,v,w,x,A=,1,2,8,定义如下：,(,1,)=,uv,(,2,)=vv,(,3,)=,vw,(,4,)=,xw,(,5,)=,vx,(,6,)=xv,(,7,)=,xu,(,8,)=,ux,(,9,)=,xu,.,x,u,w,v,1,5,8,9,6,4,7,3,2,3/8/2026,4,离散数学,有向图与无向图,无向图与有向图的区别：,无向图中的,是将边映射为顶点的无序对偶，,uv,=vu。,而,有向图中的映射,D,是将边映射为顶点的有序对偶，,uv,vu，,故为有向；,有向图的基础图,：对应于有向图的无向图,.,无向图的定向图,：对应于无向图的有向图,.,3/8/2026,5,离散数学,有向图中的弧（边）,弧的头和尾,：如果,是有向图,D,的一条弧，且,(,)=,uv,则称,u,是,的尾，,v,是,的头。,环,：有向图中头尾相同的弧。,多重弧,：两条或两条以上的,头尾相同,的弧。,简单有向图,：无环，无多重弧的有向图。,3/8/2026,6,离散数学,有向图中的度,出度,：在有向图中，以顶点,u,为尾的弧的数目称为,u,的出度，记为,d,D,+,(u);,入度,：在有向图中，以顶点,u,为头的弧的数目称为,u,的入度，记为,d,D,(u);,度,：,入度与出度的和为,u,的度,记为,d,D,(u);,3/8/2026,7,离散数学,有向图中的途径,有向途径,:有向图中一个,头尾相接,的途径;,有向链,：弧不重复的有向途径；,有向通路,：顶点不重复的有向途径；,有向回路,：起点和终点重合的有向通路,.,3/8/2026,8,离散数学,有向图的连通性,定义,12.1.2,：设,D,是有向图，,若对,D,中任意顶点,u、v，,同时有,(,u,v),通路和,(,v,u),通路存在，称,D,是双向连通图，或强连通图；,若对,D,中任意顶点,u、v，,或有,(,u,v),通路，或有,(,v,u),通路，称,D,是单连通图,;,若,D,的基础图是连通图，则称,D,是弱连通图。,显然，强连通图,单连通图,弱连通图。,3/8/2026,9,离散数学,强连通分支,强连通分支,：有向图,D,的极大强连通子图,.,该图有三个,强连通分支,如图所示,。,3/8/2026,10,离散数学,12.2,有向通路与有向回路,3/8/2026,11,离散数学,有向通路不短于色数减一,有向图的有向通路之长与其基础图中的通路没有必然联系，却与图的色数有关,.,定理12.2.1：有向图,D,中包含长度至少为,(,G),1,的有向通路。其中，,G,为,D,的基础图。,证明：设,A,A(D)，,且令,A,=minA|,使得,D,A,中不含有向回路,即,A,是使,D,不含有向回路所需删去的最小边集。令,D=D,A，,设,D,中,最长有向通路的长度为,k。,对,D,进行,如下点着色,：若,D,中以,v,为起点的最长有向通路之长为,i,1,，令,(,v)=i。,这样就得到一个(,k+1),着色,。,下证,是,G,的正常(,k+1),着色。,3/8/2026,12,离散数学,有向通路不短于色数减一,证明：,下证,是,G,的正常,(,k+1),着色：,先证,D,中任何一条有向,(,u,v),通路(,uv)P,均满足,(,u),(v)。,设,(,v)=i，,由题设，,D,中存在一条有向通路,Q=(v,1,v,i,)，,其中,v,1,=v。D,中无有向回路，所以,PQ=(u,v,v,2,v,i,),必是一条以,u,为起点而长度大于,i1,的有向通路，,由,的,着色方法可知，,(,u),i。,由此可知,D,中的任何一条弧,(,u,v)，,即长度为1的有向通路，的首尾均不同色，即有,(,u),(v)。,3/8/2026,13,离散数学,有向通路不短于色数减一,证明：,D,中的任何弧,(,u,v),的首尾不同色,。,其次证明,D,的任意一条弧的头尾均有不同颜色。不妨设(,u,v),A(D),A(D)，,由,A,的极小性可知，,D+(u,v),中必然含一条有向回路,C，,于是,C,(u,v),是,D,中的有向通路。而,v，u,为该有向通路的首尾，故,(,u),(v)。,u,v,回路,C,通路,C,uv,总之，可以证明,G,的任何两个邻接的顶点在,下颜色均不同。,是,一个正常,k+1,着色，故,k+1 (,G)，,即有,k ,(G),1。,3/8/2026,14,离散数学,竞赛图,竞赛图,：完全图的定向图称为竞赛图。,n,阶竞赛图可用来表示,n,个选手之间进行循环赛的胜负状态。,有一人,全胜，其余各胜一场：,有一人,全输，其余各胜两场：,3/8/2026,15,离散数学,竞赛图都含有向,H,通路,有向图,D,的,有向,H,通路,是指一条包含,D,的所有顶点的有向通路。,推论,12.2.1,：每个竞赛图都含有向,H,通路。,证明,：设,D,是竞赛图，,D,的基础图,G,是完全图，,于是，,(,G)=|V(D)|=p,由定理,12.2.1,知，,D,中含长为,p,1,的有向通路，也就是说，该通路上包含了所有,的,p,个顶点，即为有向,H,通路。,3/8/2026,16,离散数学,有向图的独立集,独立集,:,有向图,D,的顶点子集,S，,如果其中任何两点在,D,中都不是某一条弧的头尾,(,即不邻接,),，则称,S,为,D,的一个独立集。,有向图的独立集与无向图的独立集的概念是相同，是由互不邻接的顶点构成的顶点子集。,3/8/2026,17,离散数学,独立集相距其它点不超过二,定理,12.2.2,：,无环有向图,D,中总存在这样一个独立集,S，,使得对,V S,中的任何一点,v,存在,uS,从,u,到,v,有长度不超过,2,的有向通路。,证明,：对,D,的顶点数,p,作归纳证明,.,归纳基础：,p=1,时，结论显然成立,。,归纳步骤：假设对于顶点数小于等于,p,的所有有向图结论成立。令,D,是有,p+1,个顶点的有向图,任取,vV(D),令,N,+,(v)=w|(v,w)A(D)，,并称,N,+,(v),为,v,的外邻接顶点集。,3/8/2026,18,离散数学,独立集相距其它点不超过,二,证明：,由归纳假设，在,D,=D (v N,+,(v),中，存在一个独立集,S,，,使得对,D,结论成立。,若,v,N,+,(u)，uS,，,则对,N,+,(v),中的任何点,w，,从,u,出发，经长度为2的有向通路可到达,w。,于是，只要令,S=S,，,即可使结论成立。,S,N,+,(,u,),u,v,w,N,+,(,v,),3/8/2026,19,离散数学,独立集相距其它点不超过二,证明：,若,v,N,+,(u)，uS,，,结论成立。,若对于任意的,uS,，,均有,v,N,+,(u)，,则,可,令,S=S,v。,显然,S,是独立集。,？,因为独立集,S,是在,D,=D(vN,+,(v),中，所以,D,中没有,v,到其他任何点,的,弧；而又由题设，,对任何,uS,，,均有,v,N,+,(u)，,所以,D,也中没有其他任何点到,v,的,弧；,因此,S=S,v,仍是独立集。又由归纳假设,D,中已经存在满足定理的,S,，,因此,S=S,v,并不影响,S,的性质。,若,从,S,到,N,+,(v),之外的顶点则就是到,D,中的顶点，有,S,可使结论成立。若从,S,到,N,+,(v),中的顶点有,v,可使结论成立。故,S,可使结论成立。,由归纳法原理,结论成立,3/8/2026,20,离散数学,竞赛图中有点距其它点不超过,2,推论,12.2.2,：竞赛图中总含有一个顶点，使得从它出发，到其它每个顶点都有一条长度不超过,2,的有向通路。,证明：竞赛图的基础图是完全图，所以竞赛图的独立集只含有一个顶点。由定理,12.2.2,可知结论成立。,3/8/2026,21,离散数学,强连通竞赛图的回路性质,定理,12.2.3(,Moon,1966)：,顶点数,p,3,的强连通竞赛图,D,的每个顶点都包含在一条有向,k,回路中，其中,3,k,p .,证明：设,D,是,p,3,的强连通竞赛图，设,u,是,D,中,任意一个顶点，,uV(D)。,令,S=N,+,(u)，,T=N,(u)=w|(w,u)A(D)。,我们,先证,u,在,D,的一条有向3,回路中。,3/8/2026,22,离散数学,强连通竞赛图的回路性质,证明：,先证,u,在,D,的一条有向3,回路中。,由于,D,是强连通，因此，,S,和,T,均非空，并且同理,(,S,T)=(x,y)A(D)|xS,yT,也是非空集,。,？,注意，,D,是一个强连通的竞赛图，它的基础图是完全图。所以,ST=V(D)u。,如果不存在一条从,S,到,T,的弧，则,D,不可能是一个强连通图。所以(,S,T),是非空集。,于是，在,D,中存在一条弧(,x,y)，,使,得,xS，yT。,u,S,T,x,y,从而，,u,在有向3,回路,(,u,x,y,u),中。,3/8/2026,23,离散数学,强连通竞赛图的回路性质,证明：,已,证,u,在,D,的一条有向3,回路中。,现在对,k,作归纳法。假设,u,在所有长度为3和,n,之间的有向回路中，其中,n 1,则,D,中含有,向,H,回路,.,(,推论,8.2.1,G,为简单图，若,(,G)p/2,则,G,为,H,图,.,),3/8/2026,28,离散数学,12.3,有向树及其应用,3/8/2026,29,离散数学,有向树,定义,12.3.1,：若有向图,T,的基础图是树，则称,T,是有向树。,下面是两棵有向树，请注意它们的不同：,3/8/2026,30,离散数学,根树,定义,12.3.2,：设,T,是一个有向树，如果,T,中,恰有一个顶点的入度为,0,，其它顶点的入度均为,1,，,则称,T,为,根树,。根树,T,中入度为,0,的顶点称为,T,的,根,，记为,v,r,或,v,0,；,根树中出度为,0,的顶点称为,叶；,根树中出度不为,0,的顶点称为,分枝点,。,注意：根树是一种特殊的有向树，并非所有的有向树都是根树。,图论,中“树”的概念要比,数据结构,中的“树”的概念广泛的多。,数据结构,中的“树”仅仅是这里的根树。,3/8/2026,31,离散数学,根树的表示,对根树，我们一般将根画在最上面，即根在第,0,层，其它顶点,u,按根到,u,的唯一有向通路的长度由上至下依次画出，即将长度为,i,的顶点画在第,i,层。并规定弧的方向一律朝下，于是箭头可以省略不画；,树的高度：从根出发最长的有向通路之长称为,T,的,高度,。,3/8/2026,32,离散数学,子树,T,是一个树，,v,是,T,的一个分枝结点，由以,v,以及,T,中从,v,出发可达到的所有顶点连同所经过的弧构成以,v,为根的,T,的一个子树,.,右边树中红色的部分是不是一个子树呢？,注意：右边树中红色的部分不是一个子树！,3/8/2026,33,离散数学,根树中的术语及其示例,T,的,高度,为,3;,v,0,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,9,v,10,T:,v,2,为,v,6,v,7,v,8,的,父结点,;,v,6,v,7,v,8,为,v,2,的,子结点,;,v,4,v,5,互,为,兄弟结点,;,v,9,v,10,为,v,0,v,2,的,后裔,;,v,0,v,2,为,v,9,v,10,的,祖先,;,T,中的蓝色结点及弧构成,T,的一个以,v,2,为根的,子树,.,3/8/2026,34,离散数学,有序树,定义,12.3.3,：若对一个树,T,的结点,(弧),从上至下，同一层结点,(弧),从左至右规定了一个次序，则称,T,为有序树。,有序树的编号：,v,0,v,1,v,2,v,3,v,21,v,22,v,31,v,211,v,212,v,213,3/8/2026,35,离散数学,m,元(,有序,)树,定义,12.3.4,：设,T,是(,有序,),树，,m,1。,若对,T,的每个结点,v，,均有,d,+,(v)m，,则称,T,为,m,元(,有序,),树,;,若对,T,的每个结点,v，,均有,d,+,(v)=m,或者,d,+,(v)=0，,则称,T,为完全,m,元(,有序,),树；,若完全,m,元(,有序,),树的所有叶结点都在同一层，则称,T,为正则,m,元(,有序,),树,;,当,m=2,时，称之为,(,完全、正则,),二叉树。,3/8/2026,36,离散数学,完全,m,元树上的数量关系,定理,12.3.1 设,T,是一个完全,m,元树，其中有,t,个叶结点，,i,个分枝结点，于是,(,m1),i=t1,证明：将,m,元树看成是每局有,m,位选手参加比赛的单淘汰赛计划表，树叶表示选手，分枝点表示每局,(,分组赛,),的冠军，根表示最后的冠军。因为每局要淘汰,(,m1),个人，因此，,i,局比赛共淘汰,(,m1),i,个人，最后剩下一位冠军。故有,(,m1),i+1=t，,整理得证,.,3/8/2026,37,离散数学,应用举例,某机房有,42台,PC，,公用一个电源插座，若每台,PC,只需一个插座，需要多少个,4,插座的接线板？,解：一个有,4,插座的接线板可以连接,4,个接线板因此就构成了一个,4,元树。即接线板看成分枝结点，,PC,看成树叶。于是根据定理,12.3.1,有：,i=(t 1)/(m 1)。,将,t=42，m=4，,代入上式可得,i=(42 1)/(4 1)=13.66,14,答：需要,14个4,插座的接线板？,3/8/2026,38,离散数学,二叉树的应用,远程通讯中的编码问题：用,01,序列作为英文字母的传送信息。,(1),序列与字母如何对应？,(2),如何译码？,编码应注意的事项：,(1),使用频率越高的字母对应的码序列越短,;,(2),避免某一个字母对应的码是另一个字母所对应的码的前缀,.,3/8/2026,39,离散数学,前缀码,定义,12.3.5,：设,=,b,1,b,2,b,n,，b,i,0,1,是一个,由,字母表,上的符号构成的序列,(,符号串,),。序列,=,b,1,b,2,b,i,(1,i,n),称为,的前缀。,例如,设,=010,则,0,01,010,都是,的前缀,.,前缀码,:设,Q=,1,2,m,是一个0,1序列集合.如果,Q,中没有一个序列是另一个序列的前缀,则称,Q,为前缀码.,3/8/2026,40,离散数学,二叉树对应前缀码,定理,12.3.2,：任何一个二叉树的叶子可以对应一个前缀码,.,证明:设,T,是一个二叉树，对,T,的每个分枝结点,v，,对以,v,为尾的弧(最多两条)，将以左子结点为头的弧上标0，以右子结点为头的弧上标 1。于是从根结点出发到每个叶子结点的唯一通路中各弧上的标记依次连接而组成一个,0,1序列,。它们就是一组前缀码。,0,1,0,0,1,1,0,3/8/2026,41,离散数学,前缀码对应二叉树,定理,12.3.3,：任何前缀码都对应一个二叉树。,证明,:设,Q=,1,2,m,是一个,前缀码,.,令,h,是,Q,中最长序列的长度。今构造一个高度尾,h,的正则二叉树,T，,按定理,12.3.2,的方法给,T,的每条弧上标记,0或1,。这样，每个非根结点,v,i,都对应唯一的,0,1序列,i,。,由,T,的构造易知，,Q,的每个序列,i,恰对应,T,中一个结点,v,i,使得,i,=,i,，i=1,m。,除保留这些,v,i,和根到,v,i,的通路上的结点和弧外，删去其它结点和弧，就得到对应于,Q,的二叉树,.,3/8/2026,42,离散数学,用二叉树编码举例,用二叉树构造字母集,b,d,e,g,o,y,的,前缀码。,6,个符号需要用三位二进制来编码，所以对应的二叉树高度至少为3。,构造高度为3的二叉树并用01标记弧。,0,1,0,1,0,1,0,1,0,1,0,1,0,1,形成有6个叶子的,二叉树，并将叶子分配给相应的字母。,b,d,e,g,o,y,请译码：011101000100011010,答案:,goodbye,3/8/2026,43,离散数学,