第三章 行遍性問題

第三章行遍性問題3.1中國郵路問題3.1.1歐拉圖定義:一個圖G=(V,E)中存在的一條通過各邊一次且僅一次的回路(起點和重點重合的通路),稱為歐拉回路;具有歐拉回路的圖稱為歐拉圖.(又稱為歐拉環(huán)游或歐拉巡回)

圖G=(V,E)中的一條通過各邊一次并且僅一次的道路稱為歐拉道路.具有歐拉道路的圖稱為半歐拉圖.注:歐拉圖一定是半歐拉圖,反之不一定.例如:Euler圖半Euler圖定理1:非空連通圖G是歐拉圖的充分必要條件是G中每個頂點的次數(shù)為偶數(shù).推論1:非空連通圖G是半歐拉圖的充分必要條件是G中至多兩個頂點的次數(shù)為奇數(shù).定理2:非空連通圖G是歐拉圖的充分必要條件是G可以表示成沒有公共邊的若干個圈的并.3.1.2中國郵遞員問題郵遞員的工作是在郵局里選出郵件然后再返回郵局.自然,他必須走過他投遞范圍內(nèi)的每一條街道至少一次.在這個前提下,希望選擇一條盡可能短的路線.這個問題名為中國郵遞員問題,因為它首先是中國數(shù)學家管梅谷(1962年)研究的.

在一個賦權圖中,環(huán)游v0e1v1en…v0的權定義為,顯然,中國郵遞員問題就是在具有非負權的賦權連通圖中找出一條最小權的環(huán)游.這種環(huán)游稱為最優(yōu)環(huán)游.1.若G是歐拉圖:則G的任何歐拉環(huán)游都是最優(yōu)環(huán)游,因為歐拉環(huán)游是一條通過G的每條邊恰好一次的環(huán)游.在這種情形下,中國郵遞員問題是容易解決的,因為在歐拉圖中,存在著確定歐拉環(huán)游的好算法.由弗勞瑞(Fleury)提出的算法,用依次描畫一條道路的方法來構作歐拉環(huán)游,而這種描畫服從一個條件:在每一步中,未描畫的子圖的割邊僅當沒有別的邊可選擇時才被描畫.Fleury算法:(1)任取v0

V(G)，令P0=v0.(2)設Pi=v0e1v1e2…eivi已經(jīng)選定，按下面方法來從E(G)

{e1,e2,…,ei}中選取ei+1：(a)ei+1與vi相關聯(lián)；(b)除非無別的邊可供選擇，否則ei+1不應該為Gi

=G

{e1,e2,…,ei}中的割邊.(3)當(2)不能再進行時，算法停止.可以證明，當算法停止時所得環(huán)路(圈與圈的邊不重并)Pm

=v0e1v1e2…emvm（vm=v0）為G中一條歐拉環(huán)游.2.G不是歐拉圖若G不是歐拉圖,則G的任何一個環(huán)游經(jīng)過某些邊必定多于一次.解決這類問題的一般方法是在一些點對之間引入重復邊(重復邊與它平行的邊具有相同的權),使原圖成為歐拉圖,但希望所有添加的重復邊的權的總和為最小.情形1:G正好有兩個奇次頂點.設G正好有兩個奇次頂點u和v,求G的最佳環(huán)游的算法如下:(1)用Dijkstra算法求出奇次頂點u與v之間的最短路徑P;(2)令G*=G∪P,則G*為歐拉圖.(3)用Fleury算法求出G*的歐拉環(huán)游,這就是G的最優(yōu)環(huán)游.

v1v2v3v4v5v6v7v814225116812101情形2:G有2n個奇次頂點(n≥2)Edmonds于1965年提出的最小對集算法,很好的解決了這類問題.Edmonds算法的基本思想:先將奇次頂點配對,要求最佳配對,即點對之間距離和最小,再沿點對之間的最短路徑添加重復邊得歐拉圖G*,G*的歐拉環(huán)游便是原圖的最佳環(huán)游.Edmonds最小對集算法:(1)用Floyd算法求出所有奇次頂點之間的最短路徑和距離;(2)以G的所有奇次頂點為頂點集(個數(shù)為偶數(shù)),作一完全圖,邊上的權為兩端點在原圖G中的最短距離,將此完全圖的加權圖記為G1.(3)用Edmonds算法求出最小權理想匹配M,得到奇次頂點的最佳配對.(4)在G中沿配對頂點之間的最短路徑添加重復邊得歐拉圖G*;(5)用Fleury算法求出G*的歐拉環(huán)游,這即為G的最優(yōu)環(huán)游.注:奇偶點圖上作業(yè)法:(1)把G中次數(shù)為奇數(shù)的頂點兩兩配對.任選G中連接每對頂點的一條道路,路上的邊都添加重復邊,從而得到G的賦權歐拉母圖G*;(2)如果G*中關于G的某一條邊添加上的重復邊不只一條,則成對地刪除重復邊,直至最多有一條重復邊為止;(3)檢查G的每一個圈,如果圈上的重復邊的權和大于圈的總和的一半,則進行圈校正.每校正一次得到的新的G*的圈都減少,對所有的圈進行檢查并校正后得到的就是權最小的G*.例如:v1v2v3v4v5v6v7v8142251168101933v9由于G中v4,v7,v8,v9是奇次頂點,v4與v7,v8與v9配對;v1v2v3v4v5v6v7v8142251168101933v9下面進行圈校正:v1v2v3v4v5v6v7v8142251168101933v9再次進行圈校正:v1v2v3v4v5v6v7v8142251168101933v9例如:uvwxyztlkm11557226684341.v與l配對,x與m配對,任選路徑加重邊:uvwxyztlkm11557226684342.成對去掉重邊對于一條的:uvwxyztlkm11557226684343.進行第一次圈校正:uvwxyztlkm11557226684344.進行第二次圈校正:uvwxyztlkm11557226684343.2推銷員問題3.2.1Hamilton圖定義1:設G=(V,E)是連通無向圖,G中的一條經(jīng)過每個頂點一次并且僅一次的圈稱為G的Hamilton圈,簡稱為H圈;具有H圈的圖稱為Hamilton圖,簡稱為H圖.

判定一個圖是H圖的充分必要條件至今沒有解決,是一個NP-完全問題.3.2.2推銷員問題流動推銷員需要訪問某地區(qū)的所有城鎮(zhèn),最后回到出發(fā)點.問如何安排旅行路線使總行程最少,這就是推銷員問題.推銷員問題也是NP-完全問題.

若用頂點表示城鎮(zhèn),邊表示連接兩城鎮(zhèn)的路,邊上的權表示距離(或時間,費用),于是推銷員問題就成為在加權圖中尋找一條經(jīng)過每個頂點至少一次的最短閉通路問題.定義2:在加權圖G=(V,E)中:(1)權最小的H圈稱為最佳H圈;(2)經(jīng)過每個頂點至少一次的權最小的閉通路稱為最佳推銷員回路.一般說來,最佳H圈不一定是最佳推銷員回路,同樣,最佳推銷員回路也不一定是最佳H圈.例如:下圖中:唯一的H回路(v1,v2,v3,v1),其權和等于1+20+1=22,而通過點v1兩次的最佳推銷員回路(v1v2v1v3v1)的權和為1+1+1+1=4v1v2v31120以下定理說明何時最佳H圈也是最佳推銷員回路:定理1:在加權圖G=(V,E)中,若對任意x,y,z∈V(G),z≠x,z≠y,都有w(x,y)≤w(x,z)+w(z,y),則圖G的最佳H圈也是最佳推銷員回路.

最佳推銷員回路問題可轉(zhuǎn)化為最佳H圈問題.方法是由給定的圖G=(V,E)構造一個以V為頂點集的完全圖G

=(V,E

),E

的每條邊(x,y)的權等于頂點x和y在圖G中的最短路的權,即:

任意(x,y)∈E

,w(x,y)=mindG(x,y)定理2:加權圖G的最佳推銷員回路的權與G

的最佳H圈的權相同.

因此,在加權圖中尋求最佳推銷員回路的問題就可轉(zhuǎn)化為在一個完全加權圖中尋求最佳H圈的問題,稱為:TSP問題.3.2.3TSP近似算法:TSP近似算法包括構造型算法和改進型算法.構造型算法是按一定規(guī)則一次性地構造出一個解.而改進型算法則是以某一解作為初始解,逐步迭代,改進解,是一種迭代法,一般以構造型算法得到一個初始解,然后再用改進型算法逐步改進.二邊逐次修正法:(1)任取初始H圈:C0=v1v2…vi…vj…vnv1(2)對所有的i,j,1<i+1<j<n,若:w(vi,vj)+w(vi+1,vj+1)<w(vi,vi+1)+w(vj,vj+1)則在C0中刪去邊(vi,vi+1)和(vj,vj+1),而加入邊(vi,vj)和(vi+1,vj+1),形成新的H圈,即:C=v1v2…vivjvj-1…vi+1vj+1…vnv1(3)對C重復步驟(2),直到條件不滿足為止,最后得到的C即為所求.例:用二邊逐次修正法求下圖的較優(yōu)H圈.v1v2v3v4v5v660562136511351612706878573568

v1v2v3v4v5v6605621365113278v2v1v4v3v5v6602362178135170

v1v5v6v2v3v4251137021365135v1v3v2v6v5v423521701351注:1.可以給出旅行推銷員問題的解的下界的一個估計式.任選加權完全圖Kp的一個頂點v,用克拉斯科(Kruskal)算法求出Kp-v的最優(yōu)樹T.設C是最優(yōu)的(即權最小的)H圈,顯然C-v也是Kp-v的一個支撐樹(一個連通圖G的一個連通無圈生成子圖),因此:w(T)≤w(C-v)

設邊a和邊b是Kp中與v關聯(lián)的各條邊之中權最小和權次小的兩條邊,顯然有:

w(T)+w(a)+w(b)≤w(C)上式給出w(C)的下界的一個估計式.2.關于最小生成樹的求法.定義:T是帶權圖G=(V,E)的生成樹（1）W(T)——T各邊權之和（2）最小生成樹——G的所有生成樹中權最小的求最小生成樹的一個算法避圈法：(Kruskal算法)設帶權圖G=(V,E)，(1)在G中任取一條邊e1,e1不是環(huán)，st:w(e1)盡可能地小;(2)若e1,e2,…,ek已經(jīng)選定,在E(G)-{e1,e2,…,ek}中選邊ek+1,滿足：①G[{e1,e2,…,ek

,ek+1}]不含圈;②滿足①的情況下，st:w(ek+1)盡可能地小(3)重復(2),直到無邊可取為止.注：這種只顧當前利益的算法稱為貪婪算法．例求圖6