有向图 Euler路.ppt

提示：根据对定理4.3.2的证明，可以看到，只在证明G中所有的弧e都在L中时，才用到了“G是强连通的”。 从而，采用与定理4.3.2相同的证明方法，可以证明： fin (em)= init(e1)；对G中任意一点v，如果v在L中，则v发出的k条弧和发到v的k条弧都在L中。 这样，只需要证明任意e∈G，都有e∈L(G的每条弧在L中出现) 。 任取e?G。 对L中任意一点u，在G的漠视图G0中存在u到init(e)的一条简单路，设为(u, u1, u2, …, uk, init(e))，因为u 取自L，则u发出的所有弧和发到u的所有弧都在L中，从而无论G中是u指向u1，还是u1指向u,都有u1 ∈L , 依此类推, 有init(e) ∈L ,从而e∈L . …… L u init(e) e u1 u2 uk … fin(e) 三、Euler路与有向树的相互转化 定理4.3.3 设G是无孤立点的有限有向图，并且G有一条Euler路(e1 , … , em)。 （1）令r=fin(em)=init(e1)。 （2）对每个点v?r，令e[v]=ei，其中 i=max{j | init(ej)=v}。 于是，G的全部点和全部弧{e[v] | v?r}作成的有向图G’，是一个以r为根的有向树。 v0 v1 v2 e6 e8 e5 e1 e2 e9 e4 e3 e7 v0 v1 v2 e8 e9 证明： 由e[v]的定义知：(1) 对G中每个点v?r，恰有一弧e[v]发出， (2) r不发出任何弧。 下面我们证明：(3) r是根。 先证：有向图G’中无有向回路。 若不然，设有一个有向回路 (…,e[v],e[v’],…)。其中fin(e[v])=init(e[v’])=v’。令(在Euler路中的编号)e[v]=ej，e[v’]=ek。因为弧ej发到点v’。从而Euler路中的ej+1是由v’发出的弧，但ek是由v’发出的弧中下标最大者，所以j+1≤k，则jk。 证明： … v v’ e[v]=ej e[v’]=ek ej+1 定理4.3.1（转化定理） (1) 若r在此路中，不妨假设v0=r，则在G中对应G0的边v0v1的弧一定是从v1到v0的，又因G中除根外，其他点恰发一弧，所以G0中边v1v2必是G中从v2到v1的弧，…，G0中边vk-1 vk必是G中vk到vk-1的弧，…，G0中边vn-1vn必是G中vn到vn-1的弧，而vn= v0=r，矛盾。 … … vn = v0=r v1 v2 vk vk-1 vn-1 定理4.3.1（转化定理） (2)若r不在此回路中，由有向树定义知，v0或v1恰发一弧，不妨设G0中的边v0v1是G中从v1到v0的弧，则v1已发弧，则G0中的边v1v2必是G中从v2到v1的弧，…，则G0中边vn-1vn是G中从vn到vn-1的弧，又vn=v0, 于是，得G中一有向回路，矛盾. … … vn = v0 v1 v2 vk vk-1 vn-1 故假设不成立，连通图G0无回路，则G0是树。 定理4.3.1（转化定理） 2)再证第二个命题。 任选树中一点r作为根，规定：将G0中任意一边vv’改成从v到v’的弧当且仅当v?r且从v到r的简单路通过v’。即这条简单路形如：(v,v’,…,r) 。 (1)首先证明上述规定的无矛盾性：对树G0中任意一边vv’，若v’=r，则按规定，将边vv’改成从v到r的弧；若v’?r，则往证：按规定，其方向或者从v到v’，或者从v’到v，二者必居其一。 r 有向树G 树G0 命题2 V V’ V’ V 定理4.3.1（转化定理） 因为树G0中从v,v’各恰有一条到r的简单路，分别设为(v,v1,v2,…,r)、(v’,v1’,v2’,…,r)， 若v? v1’，v1?v’，则由于v?v’，所以可设 vi，vj’是这两条路中从左向右看第一对相同的点，亦即 vi= vj’，但是v,v1,…,vi,vj-1’,…,v1’,v’互不相同，所以(v,v1,…,vi,vj-1’,…,v1’,v’,v)是从v到自身的简单路，当i=j=1时，此路为(v,v1,v’,v)，长度为3，即此路是回路，与G0是树矛盾。 定理4.3.1（转化定理） 因为树G0中从v,v’各恰有一条到r的简单路，分别设为(v,v1,v2,…,r)、(v’,v1’,v2’,…,r)， 若v? v1’，v1?v’： v’ v1’ r vj-1’ v v1 v2 vi =vj’ v2’ vj’ 定理4.3.1（转化定理） 若v=v1’且v1=v’，则(v,v’,v2, …,r)， (v,v2’,…,r)是两条从v到r的简单路，由于v2’ ?v’，所以这是两