第4章 遍历问题.ppt

(travellingsalesmanprob.)(tour)通过图中每边至少一次的闭途径。Euler环游通过图中每边恰一次的闭途径。Euler迹通过图中每边的迹。通过图中每边恰一次的途径。(可“一笔画成”。)Euler图包含Euler环游的图包含Euler闭迹的图。本身为闭迹的图。,则G为Euler图G中无度为奇数的顶点。证明::令C=u0e1u1e2u2...eu(u=u0)为G的一Euler环游,起点为u0。则对任一顶点vu0,当v每次作为内部顶点出现于C时,C上有二边与v相关联。由于C上包含了G的所有边且不重复,因此d(v)=偶数。类似地,d(u0)=偶数。:反证,假设存在非空连通图,它的每个顶点的度都是偶数,但却不是Euler图。在这种图中选取G使其边数最少。由于(G)2,G包含圈。令C为G中的最长闭迹。由假设,C不会是Euler环游。因此G-E(C)中一定有一分支G’使(G’)>0。由于C本身为Euler图,(由定理的必要条件知)C中每个顶点的度都是偶数,因此G’中无度为奇数的顶点。但(G’)<(G)由G的选择知,G’中含一Euler环游C’。又,由于G连通,C与C’至少有一公共顶点,设为v,不妨设它同时为它们的起点。’是G的一闭迹,其长大于C的长,矛盾。:之新证法():对进行归纳。当=2时,显然成立。只要再考虑3情形。假设对<q成立,而(G)=q。选取顶点v,使v有二不同顶点u及w与它相邻。考虑图 H=(G-{uv,vw})+uw(uw为一新加边——不管G中是否有以u,w为两端点的边)馆惦尧戳逃娜哆食缸透度拜绎百淘挤骸草崭坦萌湾孕形霖脐丧秧刃闸把杀第4章遍历问题第4章遍历问题显然, (H)2, (H)=q-1, dH(x)=偶数xV。(i)当(H)=1时,由归纳假设,H中有Euler环游C’。把C’中一边uw代之以路uvw,即得G的Euler环游。(ii)当(H)=2时,由归纳假设,H的二分支各有其Euler环游C1及C2。不妨设uw在C2中。将C2中的边uw代之以迹uvC1vw,即得G的Euler环游。,则G有一Euler迹G中至多有二度为奇数顶点。证明:::的证明。 :若G中无度为奇数顶点,,G中有Euler迹。否则,G中恰有二度为奇数顶点,设为u,v。考虑图G+e,其中e为连接u与v的新边。显然,G+e中无度为奇数顶点,从而包含一Euler环游 C=v0e1v1e2v2...ev,其中,v=v0=u,v1=v 。易见 v1e2v2...ev就是G的Euler迹。,画出一个为偶数,而为奇数的Euler图。否则说明理由。:若G无奇点,则G的每个块也是Euler图。,则存在边不重的圈C1,C2,...,Cm使得 E(G)=E(C1)E(C2)...E(Cm)。 >0个奇点,则G中存在k条边不重的迹Q1,Q2,...,Qk使得 E(G)=E(Q1)E(Q2)...E(Qk),且vV。证明:G中任一条以v为起点的迹都能延伸成一Euler环游当且仅当G-v为林。(),则G是一Euler图。(如图中虚线所示),穿过每一线段恰好一次?若能,画出之;不然,证明之。让返谐和扮甥缀理胁牡各骑妄镊朴落磐没概伙佯闹俐黑纂靳严玲新灭肆犹第4章遍历问