第8章 有向图.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,图论及其应用,*,图论及其应用,第,8,章,有向图,8.1,有向图,有向图,（,directed graph,；,digraph,）,D=,（,V,，,A,）,V(D),顶点集。,A(D),弧集。,弧,a=(,u,v,),：其,头,为,v,，其,尾,为,u,；,弧,a,从,u,连到,(join,to)v,。,有向子图,（,subdigraph,）,有向图,D,的,基础图,（,underlying graph,）,对应于,D,的无向图,G,（称,D,为,G,的一个,定向,（,orientation,）,图,）,u,v,a,2,图论及其应用,8.1,有向图,（无向）图的每个慨念在有向图中仍然有效例如，右图是,2-,连通图；有,Hamiton,圈；有完美匹配；,=,=3,；,vrswu,是它的一条,(,v,u,)-,路；,vyzwsrv,是它的一个圈，等等。,此外，有向图还有一些与方向有关的慨念，如,有向途径,（,directed walk,）、,有向迹,（,directed trail,）、,有向路,（,directed path,）、,有向,Euler,环游,（,direted,Euler tour,）、,有向圈,（,directed cycle,）等等。,例如右图中，,(v,e1,x,e2,y,e3,z,e4,w,e5,u),为一,有向,(,v,u,)-,路,，可简记为（,v,x,y,z,w,u,）；,又，,(,y,z,w,s,r,x,y,),为一 有向圈。,称 顶点,v,为,从,u,可达的,（,reachable from u,）,存在有向（,u,，,v,）,-,路。,称 顶点,u,与,v,为,双向连通的,（,diconnected,；,strongly connected,）,u,与,v,彼此可达的。,3,图论及其应用,8.1,有向图,易见，有向图,D=(V,A),中顶点间的双向连通性是,V,上的一个等价关系，它的等价类确定了,V,的一个划分 （,V1,，,，,Vm,），使顶点,u,与,v,双向连通,u,与,v,同属某等价类,Vi,。称每个导出子图,DV1,，,，,DVm,为有向图,D,的一个,双向分支,（,dicomponent,；,strong component,）。当,D,只有一个双向分支时，称,D,为,双向连通的。,易见，,D,的,任二双向分支之间的弧都是同一个方向的,。,例,4,图论及其应用,8.1,有向图,入度,（,indegree,）。,出度,（,outdegree,）。,记号,+,，,：最小出、入度；,+,最大出、入度。,称有向图,D,为,严格的,（,strict,）,无环、且不存在两弧其端点及方向相同。,5,图论及其应用,8.1,有向图,习题,10.1.1,.,一个简单图有多少个定向图？,10.1.2,.,证明：,=,=,。,10.1.3.,设有向图,D,中无有向圈，则,(a),=0,；,(b),存在一个顶点排序,v1,，,，,v,，使对,1,i,，每条以,vi,为 头的弧其尾都在,v1,，,，,vi-1,中。,10.1.4,.,证明：,D,是双向连通的,D,是连通的，且,D,的每个块是双向连通的。,10.1.5,.D,的,逆图,是把,D,中每弧的方向都改为其反向所得的有向图。试用逆图慨念及习题,10.1.3.(a),来证明：若有向图,D,中无有向圈，则,+=0,。,10.1.6,.,证明：严格有向图包含长,max,，,+,的有向路。,10.1.7.,证明：严格有向图中若,max,，,+=k,1,，则,D,包含长,k+1,的有向圈。,6,图论及其应用,8.1,有向图,习题（续）,10.1.8.,设,矩阵,A=,aij,为有向图,D,的邻接矩阵，其中,aij,是,D,中以,vi,为尾、以,vj,为头的弧数。证明：,Ak,的第,(,i,j,),元素是,D,中长为,k,的（,vi,vj,）,-,有向途径的数目。,10.1.9,.,设,D1,，,，,Dm,为,D,的双向分支。,D的,凝聚图,H,是一有,m,个顶点,w1,，,，,w,的有向图。,H,中存在以,wi,为尾、以,wj,为头的弧，当且仅当,D,中存在尾在,Di,、而头在,Dj,中的弧。证明：,H,中不包含有向圈。,10.1.10,.,证明：任一图,G,都有一个定向图,D,，使对每个顶点,v,都有,|,d+(v,)-,d-(v,)|,1,10.1.11,.,证明：,D,是双向连通的,对,10.1.12,在连通非空有向图,D,中，证明：,D,是双向连通的,D,中每弧在一有向圈上,10.1.13.,设,D,为一,以,（顶点）,u,为根的有向图,（,对,D,中任一顶点，,D,中都存在一有向,(,u,v,)-,路），证明：,D,中有一,以为根的有向树,，中每一（唯一）有向,(,u,v,)-,路是,D,中最短有向,(,u,v,)-,路。,10.1.1,4.,有向图中任一有向闭迹恒可划分为一些边不重的有向圈的併。,7,图论及其应用,8.1,有向图,习题（续）,10.1.15.,设,T=(V,A),为一,有向树,（,（无向）树的一个定向），,F,A(T),。证明：存在一顶点,x,，它恰只是,F,中弧的头（即不能是尾）。,8,图论及其应用,10.2,有向路,定理,10.1,(Roy,1967;Gallai,1968,),有向图,D,包含一长为,-1,的有向路,。,证明：令,D,为,D,的,极大,无有向圈,、有向,生成,子图（注：,D,可由空生成子图作为开始，在保持无有向圈的条件下，通过逐步加弧而得）。令,k,为,D,中最长有向路的长。今用色,1,，,2,，,，,k+1,对,D,进行顶点着色如下：将,v,着以色,i,D,中以,v,为起点的最长有向路的长为,i-1,。来证这是,D,的正常,(k+1)-,顶点着色：,先证，,D,中任一有向,(,u,v,)-,路,P,的起、终点,u,与,v,一定不同色：设,v,被着以色,i,。则由着色法知，在,D,中以,v,为起点的一最长有向路，设为，,Q,的长为,i-1,。由于,D,中无有向圈，,PQ,为一有向路，起点为,u,，长,i,。从而,u,上的色,j i,。,只要再证，,D,中任一弧,(,u,v,),的两端一定不同色：当,(,u,v,),为,D,中的弧时，它就是,D,中的一有向,(,u,v,)-,路，从而,u,与,v,不同色。,在有向图中，最长路的长和最长有向路的长之间并无任何密切的关系，例如右面的有向图最长路的长为,（可任意大），而最长有向路的长卻为,1,9,图论及其应用,10.2,有向路,当,(,u,v,),不是,D,中的弧时，由,D,之极大性知,D+(,u,v,),包含一有向圈,C,。于是，,C-(,u,v,),是,D,中的有向,(,v,u,)-,路，从而,u,与,v,也不同色。,由上述知，,D,为,(k+1)-,可着色的，因此,k+1,，得,k,1,，故,D,中有长为,-1,的有向路。,#,注,定理,10.1,在如下意义下是最佳的：,对每个（无向）图,G,，都存在,G,的一个定向图，其最长有向路的长恰为,-1,。,证明：令（,V1,，,，,V,-1,）为,G,的正常,-,顶点着色。今作,G,的定向图,D,如下：边,uv,（不妨设，,u,Vi,，,v,Vj,）定向为弧,(,u,v,),i,-1,的有向路。再由定理,10.1,得证。,#,称完全图的定向图为,竞赛图,（,tournament,，是简单图！）。,10,图论及其应用,10.2,有向路,推论,10.1,(Redei,1934),每个竞赛图都有一,Hamilton,路。,证明：注意到,=,即可。,#,设,(,u,v,),为有向图,D,中的一弧，则称,u,为,v,的,内邻点,（,in-,neighbour,）；称,v,为,u,的,外邻点,（,out-,neighbour,）。记 和 分别为有向图,D,中顶点,v,的,内邻集,和,外邻集,。,11,图论及其应用,10.2,有向路,定理,10.2,(,Chavtal,&Lavasz,1974),无环、有向图,D,中包含一独立集,S,，使,D,的每个不在,S,中的顶点，都是从,S,中某顶点通过长,2,的有向路可达的。,证明：对,进行归纳。当,=1,时，显然成立。假设定理对顶点数,mn,的有向图，而,f,是定义在,V,上的一个实函数。证明：,D,中或者存在一有向路,(u0,，,u1,，,，,um),满足,f(u0),f(u1),f(um,),；或者存在一有向路,(v0,，,v1,，,，,vn,),满足,f(v0)f(v1),f(vn,),。,(b),试证：任意,mn+1,个不同整数的序列中，或者包含一个,m,项的递增子序列；或者包含一个,n,项的递减子序列,13,图论及其应用,10.2,有向路,习题（续）,10.2.6,.,(a),利用定理,10.1,和推论,8.1.2,证明：,G,有一个定向图，它的最长有向路的长,。,(b),给出,(a),的构造性证明。,10.2.7,一竞赛图中至多有一的顶点，它是一有向哈密尔顿路的起点（或 终点）。,10.2.8,每一竞赛图中恒有 。,14,图论及其应用,10.3,圈,记号,（,S,，,T,）是,D,中尾在,S,内而头在,T,内的所有弧的集合。（,S,，,T,是,V,的子集）,定理,10.3,(Moon,1966),3,的双向连通竞赛图,D,中，每个顶点包含在一有向,k-,圈中，,3,k,。,证明：设,u,是,D,的任一顶点。用对,k,的归纳法来证明。当,k=3,时，令,S=,N+(u,),，,T=N-(u),。,由,D,的双向连通性知，,S,，,T,，（,S,，,T,）都是非空的。因此,D,中存在一弧,(v,w),使,v,S,，,w,T,。从而,u,在有向,3-,圈u,v,w,u,),中，结论成立。,假设对每一,k,，,3,k,n 1,，则,D,包含一有向,Hamilton,圈。,证明：反证，假设,D,不包含有向,Hamilton,圈。令,C=,（,v1,，,v2,，,，,vq,，,v1,）,D,中一最长有向圈，其长 为,q,。易见，,q ,/2,（习题,10.1.7,）。令,P,为,D-V(C),中的一条最长有向路，其长为,m,；其起、终点分别为,u,和,v,。显然，,q+m+1 (1)m 0,使,i,S,，,i+k,T,（,mod q,）,i+j,S,T,（,mod q,）,1,j,(,Gi,),，该序列一定终止于,G,的一生成子图,Gn,上。今对,Gn,定向如下：把,G1,定向为一有向圈；把,Pi,定向为一以,vi,为起点的有向路；把,Qi,定向为以,vi,为终点的有向路。显然，每个,Gi,有一双向连通定向。由于,Gn,是,G,的一生成子图，,G,也存在双向连通定向图。,22,图论及其应用,10.4,公路系统的单行线化,定理,（,Nash-Williams,，,1960,）,G,为,2k-,边连通的,G,有,k-,弧连通,定向图。,（证略）（即,|,（,S,，,S,）,|,k,S,V,）,上述定理的特殊情形为以下定理，其证明较容易，留给读者完成：,定理,10.6,G,为,2k-,边连通，且有一,Euler,迹,G,有一,k-,弧连通定向图。,习题,10.5.1*,通过,考察,Petersen,图证明以下结论不成立：每个图都有一定向图，使得对每个,S,V,，（,S,，）和（，,S,）的弧数相差最多为,1,。,10.5.2*.(a),证明,Nash-Williams,定理下述命题：若,G,的每个键至少有,2k-,条边，则存在,G,的一个定向图，其中每个键在每个方向上都至少有,k-,条弧。,(b),通过考察,Grotzsch,图证明以下结论不成立：若,G,的每个圈至少有,2k-,条边，则存在,G,的一个定向图，其中每个圈在每个方向上都至少有,k-,条弧。,23,图论及其应用,