《歐拉圖及哈密頓》ppt課件-全文預(yù)覽
【正文】 成立 ,反之 ,繼續(xù)尋找 ,總可以找到符合條件的回 . 第二章 歐拉圖與哈密頓圖 (2) 定理 2 連通圖 G具有歐拉路而無歐拉回路 ,當(dāng)且僅當(dāng) G恰有兩個奇數(shù)度頂點 . 證 :必要性 :設(shè)連通圖 G從頂點 a到頂點 b有歐拉路 C,但不是歐拉回路 .在歐拉路 C中 ,除第一邊和最后一邊外 ,每經(jīng)過 G中頂點xi(包括 a和 b),都為頂點 xi貢獻 2度 ,而 C的第一邊為 a貢獻 1度 ,C的最后一條邊為 b貢獻 1度 .因此 ,a和 b的度數(shù)均為奇數(shù) ,其余結(jié)點度數(shù)均為偶數(shù) . 充分性 :設(shè)連通圖 G恰有兩個奇數(shù)度結(jié)點 , 不妨設(shè)為 a和 b,在圖 G中添加一條邊 e={a,b} 得 G’,則 G’的每個結(jié)點的度數(shù)均為偶數(shù) ,因 而 G’中存在歐拉回路 ,故 G中必存在歐拉路 . 定義 2 給定有向圖 D,經(jīng)過 D中每邊 一次且僅 一次 的 有向跡 稱為 D的 有向歐拉路 .經(jīng)過 D中 每邊一次且僅一次的 有向閉跡 (回 ),稱為有 向歐拉回路 . 第二章 歐拉圖與哈密頓圖 (3) 定理 3 具有弱連通性的有向圖 G具有有向歐拉 回路 ,當(dāng)且僅當(dāng) G的每個結(jié)點的入度等于出度 . 具有弱連通性的有向圖 G具有有向歐拉路 ,當(dāng)且僅當(dāng)在 G中 ,一個結(jié)點的入度比出度大 1,另一個結(jié)點的入度比出度小 1,而其余每個結(jié)點的入度等于出度 . 定義 3 含有 歐拉回路的無向連通圖 與 含有向歐 拉回路的弱連通有向圖 ,統(tǒng)稱為歐拉圖 . 求 Euler圖的 Euler回路的 Fleury算法 . (1)任意選取一個頂點 v0,置 W0=v0。 (2)歐拉路是跡 (邊互不重復(fù) ),但不是嚴(yán)格意 義上的路 . 定理 1連通圖 G具有歐拉回路 當(dāng)且僅當(dāng) 其每個 頂點的度數(shù)為偶數(shù) . 歐拉路 (2) 證明 :必要性 :不妨設(shè) C是從頂點 x1開始的無向圖 G 的一條歐拉回路 .對該回路中的任何一個內(nèi)部點 xi 而言 ,每出現(xiàn)一次 ,其度數(shù)必增加 2,對 x1來講 ,回路 最后在該點結(jié)束 ,當(dāng)然其度數(shù)也為偶數(shù) . 充分性 :若 G是連通無向圖 ,作 G的一條最長回 C,并 假設(shè) C不是歐拉回路 .這樣 ,在 C中必存在 xk∈V(C)及關(guān)聯(lián) xk的邊 e={xk,x1’} ? C。 定義 1 給定無向圖 G,若存在一條路經(jīng)過圖 G的每個結(jié)點一次且僅一次 ,這條路稱為哈密頓路 .若存在一條閉路經(jīng)過圖 G的每個結(jié)點一次且僅一次 ,這條閉路稱為哈密頓回路 . 定義 2給定有向圖 D,若存在一條路經(jīng)過圖 G的每個結(jié)點一次且僅一次 ,這條路稱為哈密頓有向路 .若存在一條閉路經(jīng)過圖 G的每個結(jié)點一次且僅一次 ,這條有向閉路稱為哈密頓有向回路 . 第二節(jié) 哈密頓圖 (1) 第二節(jié) 哈密頓圖 (1) 定義 3 具有哈密頓回路的無向圖與具有哈密頓有向回路的有向圖 ,統(tǒng)稱為哈密頓圖 . 例 1對于完全圖 Kn(n?3),由于 Kn中任意兩個頂點之間都有邊 ,從 Kn的某一頂點開始 ,總可以遍歷其余節(jié)點后 ,再回到該結(jié)點 ,因而 Kn(n?3)是哈密頓圖 . 說明 :判斷一個給定的圖是否為哈密頓圖 ,是圖論 中尚未解決的難題之一 ,下面介紹若干必要條件 和充分條件 . 第二節(jié) 哈密頓圖 (2) 定理 1設(shè)任意 n(n?3)階圖 G,對所有不同非鄰接頂 點 x和 y,若 deg(x)+deg(y) ?n,則 G是哈密頓圖 . 證明 :僅就 G是無向圖加以證明 .假設(shè)定理不成立 . 則存在一個階為 n(n?3),滿足定理條件且邊數(shù)最 多的非哈密頓圖 ,即 G是一個非哈密頓圖且對 G 的任何兩個非鄰接點 x1和 x2,圖 G+邊 {x1,x2}是哈 密頓圖 . 因為 n?3,所以 G不是完全圖 .設(shè) u和 v是 G的兩 個頂點 .因此 G+邊 {u,v}是哈密頓圖 .且 G+邊 {u,v} 是哈密頓回路一定包含邊 {u,v}.故在 G中存在一 條 uv路 T=u1u2…u n(u=u1,v=un)包含 G中每個頂點 . 若 {u1,ui}?E(G)(2?i?n),則 {ui1,un}?E(G).否則 u1uiui+1…u nui1ui2…u 1是 G的一個哈密頓回路 ,故 對 {u2,u3,…,u n1}中每一個鄰接到 u1的頂點存在一 個 {u1,u3,…,u n1}中與 un不鄰接的頂點 ,故 deg(un) ?n1deg(u1),所以 deg(u)+deg(v) ?n1 矛盾 . 第二節(jié) (3) 定理 2 設(shè) u和 v是 n階圖 G的不同非鄰接點 ,且 deg(u) +deg(v)?n, 則 G+邊 {u,v}是哈密頓圖當(dāng)且僅當(dāng)哈密頓圖 . 定義 4 給定 n階圖 G,若將圖 G度數(shù)之和至少是 n的非 鄰接點用一條邊連接起來得圖 G’,對圖 G’重復(fù)上述 過程 ,直到不再有這樣的結(jié)點對存在為止 ,所得到的 圖 ,稱為是原圖 G的閉包 ,記作 C(G). 定理 3 一個圖是哈密頓圖當(dāng)且僅當(dāng)它的閉包是哈密 頓圖 . 定理 4 設(shè) G是階至少為 3的圖 ,如果 G的閉包是完全圖 , 則 G是哈密頓圖 . 定理 5如果 G是一個 n階 (n?3)任意圖 ,且對 G的每個頂 點 x,都有 deg(x) ?n/2,則 G是哈密頓圖 . 說明 :由哈密頓圖的定義可知 ,哈密頓圖有向圖必是 強連通的 ,哈密頓無向圖必?zé)o割點 . (4) 定理 5 若 G是一個哈密頓圖 ,則對于 V(G)的每個非空真子集 S, 其中 W(GS)為 GS的分支數(shù) . 證明 :設(shè) C是 G的一個哈密頓回路 ,則對于 V(G)的任意一個非空真子集 S,均成立 由于 CS為 GS的一個生成子圖 ,因而 W(GS)?W(CS),故 .)( SSGW ??W( C S ) S .??.)( SSGW ?? (5) 說明 :定理 6只是一個必要條件 ,如下的皮特森圖 ,盡 管有 但它不是哈密頓圖 . SSGW ?? )( (6) 應(yīng)用 定理 G是一個 n(n?3)階任意圖 ,且對 G的每個頂點 x,都有 deg(x) ?n/2,則 G是哈密頓圖 . 例 ,他
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1