【文章內(nèi)容簡介】 意一對頂點 vi、 vj，恒有 d(vi)+d(vj)≥n1，則圖 G中至少有一條 Hamilton道路。 ?推論 (充分條件 ) ：若任意一對頂點 vi、 vj，恒有d(vi)+d(vj)≥n，則圖 G中至少有一條 Hamilton回路。 下面證明 Hamilton道路的存在。 證明： (1)先證明 G是連通的。 假設 G不連通，則 G至少有兩個連通分量。設其中一部分有 n1個頂點，另一部分有 n2個頂點。分別在兩部分各選一個頂點 v v2， ∵ G是簡單圖，所以： d(v1)≤ n1－ 1 ， d(v2)≤ n2－ 1， d(v1)+d(v2) ≤ n1＋ n2－ 2＜ n－ 1。 與假設 d(vi)+d(vj)≥n1矛盾，所以 G連通。 (2)再證明存在 Hamilton道路： 假設 G中有一條從 v1到 vL道路 T=(v1,v2,…,v L)是圖中的最長道路，即起點 v1和終點 vL不和 T之外的頂點相鄰。 (a)如果 L＝ n，即 T是包含所有頂點的道路，即 T是 Hamilton道路，得證。 (b)若 L＜ n且 v1和 vL相鄰，則存在包含 T的回路； v1 v2 vp vL vL1 若 L＜ n且 v1和 vL不相鄰，則根據(jù)條件 d(vi)+d(vj)≥n1，有如下圖示： v1 v2 vp1 vL vp 所以存在包含 T的回路。 Hamilton定理證明－ 3 (c)證明存在比 T更長的道路： 與假設矛盾， 重復（ a）～（ c），在有限步內(nèi)一定得到 包含所有頂點的 Hamilon道路。 v1 v2 vp1 vL vp vk 則根據(jù)條件 d(vi)+d(vj)≥n1，有如下圖示： 37 2022/2/13 〖 Example 5〗 There are seven people denoted by A, B, C, D, E, F, G. Suppose that the following facts are known. AEnglish (A can speak English.) BEnglish, Chinese CEnglish, Italian, Russian DJapanese, Chinese EGerman, Italia FFrench, Japanese, Russian GFrench, German How to arrange seat for the round desk such that the seven people can talk each other? 38 2022/2/13 (1) Construct graph V={A,B,C,D,E,F,G}, E={(u,v)|u,v can speak at least one mon language.} Solution: AEnglish (A can speak English.) BEnglish, Chinese CEnglish, Italian, Russian DJapanese, Chinese EGerman, Italia FFrench, Japanese, Russian GFrench, German A B C D E F G (2) If there is a H circuit, then we can arrange seat for the round desk such that the seven people can talk each other. H circuit: A,B,D,F,G,E,C,A A B D F G E C 中國郵路問題 中國郵路問題 (Chinese postman problem)， 是我國數(shù)學家管梅谷于 1960年首次提出的。 問題描述： 設郵遞員從郵局出發(fā)，遍歷他所管轄的每一條街道，將信件送到后返回郵局，求所走的路徑最短。 ? 中國郵路問題的圖論模型為： 設 G=(V,E)是連通圖，而且對于所有的 e∈ E都賦以 權c(e)≥0，求從點 v0∈ V出發(fā)，通過所有邊至少一次最后返回v0的回路 C，使得 達到最小。 ??Ceec )(郵局 v1 v2 v3 v4 v5 v6 3 4 5 2 1 4 2 6 3 5 1 v0 ? 問題分析： （ 1）如果道路正好是一個 Euler圖，則容易求解，用 Fleury算法求出一個 Euler回路即可； （ 2）如果不是 Euler圖，則加上如干重復邊，使之變成 Euler圖，然后求 Euler回路。 現(xiàn)在問題的 關鍵： 如何加重復邊！ 中國郵路問題是 Euler回路的近似求解。 ?定理：設 E* E是使 W(E*)= 達到最小 的重復邊集合，當且僅當對于 Ga圖的 任一回 路 ，恒有 W( ∩E*)≤W(E( )E*) ? ?? *)(EeecC C CE*是重復邊集合 Ga是加重復邊以后的 Euler圖 E*={(v2,v3)} E(C)={(v1,v2),(v1,v3)(v2,v3 )(v2,v4 )(v3,v4)} v1 v3 v2 3 2 3 4 v4 2 中國郵路構造算法 設已經(jīng)知道度為奇數(shù)的頂點為 v1,v2,…,v 2h ?第一步 ： 添加重復邊 ： i從 1到 h，引從 v2i1到 v2i的鏈 Pi，并對 Pi的每條邊附加 1條重復邊； ?第二步 ： 檢查重復邊 ：檢查圖 G的每條邊，使得每條邊最多有 1條重復邊，得到圖 G’， G’中重復邊集記為E(0)； ?第三步 ：設初值 k＝ 0； C ???????)()( )()()()(kk ECEeCEEeecec? C(a)若 E(k)對于回路 有 ，則 E(k＋ 1)=E(k) E( )， k＝ k＋ 1，轉(zhuǎn) (a)； (b)輸出 E(k)， E(k)便是最優(yōu)集。 ? 第四步 ：用 Fleury算法求出 Eluer回路。 例 求出下圖中以 v1為起點的一條中國郵路。 v1 v2 v3 v4 v6 v5 v7 5 1 3 2 2 3 2 5 4 3 3 解：其中 v2， v3， v4， v5， v6， v7頂點的度都是奇數(shù)，引入重復邊。 第一步 ： 添加重復邊： i從 1到 h，引從 v2i1到 v2i的鏈 Pi，并對 Pi的每條邊附加 1條重復邊； v1 v2 v3 v4 v6 v5 v7 5 1 3 2 2 3 2 5 4 3 3 E(0)={(v2,v3),(v4,v5),(v6,v7)} 第二步 ：檢查重復邊：檢查圖 G的每條邊，使得每 條邊最多有 1條重復邊，得到圖 G’， G’中重復邊集 記為 E(0)； 下面看回路 ： v2v3v7v2 其中 E( )={(v2,v3),(v2,v7),(v3,v7)} CE(0)={(v2,v3),(v4,v5),(v6,v7)} ??? )()0()(CEEeec ??? )0()()(ECEeecC?∵ ＝ 5 ＞ ＝ 2＋ 2＝ 4 ∴ E(1)＝ E(0) E( )＝ {(v2,v7),(v3,v7),(v4,v5),(v6,v7)} Cv1 v2 v3 v4 v6 v5 v7 5 1 3 2 2 3 2 5 4 3 3 C